概述
1. 简单排序
1.1. 直接插入排序——插入排序
空间复杂度O(1) 时间复杂度O(n2)
直接插入排序并不是那种一趟就能锁定一个数字所在位置的排序算法。这个算法每一趟都会多加一个数，来组成前 i 个的临时有序的排序。
（由小到大）：
从第一趟开始，对比第二个数与第一个数的大小，若第二个数小于第一个数就将第二个数移至第一位。
第二趟就会对比第三个数字与第二个数字的大小，若是小于第二个数字，就跟第二个数字进行换位，再跟第一位数字进行对比。以此类推......
package main
import "fmt"
func insertSort(nums []int) []int {
numsLen := len(nums)//获取切片的长度
if numsLen < 2 {
return nums
}//当所需排的的数不到两个的时候，直接返回当前数就行
for i := 1; i < numsLen; i++ {
preIndex := i - 1// 当前值的前一个元素的下标
nowNums := nums[i]// 当前值
//前一个值大于当前值的时候，进入该循环
for nums[preIndex] > nowNums {
//因为当前值小于前一个值，当前值的位置就给予了前一个值
nums[preIndex+1] = nums[preIndex]
//当前指针归零，说明这一趟所有数都已经走完了，那么直接退出此次循环
if preIndex == 0 {
preIndex--
break
}
//将前指针再次前移，确保前面的数也比当前值小
preIndex--
}
//确保了前指针已经没有值比当前值还大，所以前指针的后一位就是当前数所应存在的位置
nums[preIndex+1] = nowNums
}
return nums
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = insertSort(a)
fmt.Println(a)
}
1.2. 冒泡排序——交换排序
空间复杂度O(1)、时间复杂度O(n2)、比较次数：n(n-1)/2、移动次数：3n(n-1)/2
每走一趟都会确定一位数的最终位置。从后往前对比，也可以从前往后对比。每走一趟就剩余 n-i 个数需要排序。
package main
import "fmt"
func bubbleSort(nums []int) []int {
numsLen := len(nums)
if numsLen <= 1 {
return nums
}
for i := 0; i < numsLen; i++ {
for j := 0; j < numsLen-i-1; j++ {
//如果当前位大于后一位，则置换两位数
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
return nums
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = bubbleSort(a)
fmt.Println(a)
}1.3. 简单选择排序——选择排序
空间复杂度O(1)、时间复杂度O(n2)不稳定
由小到大：每次都从剩余未排序的数中比较出一个最小值，将最小值与未排序的数中最靠前的数进行置换。每一趟都能排好一个数，每次都剩余 n-i 个数需要排序。
package main
import "fmt"
func selectSort(nums []int) []int {
numsLen := len(nums)
if numsLen < 2 {
return nums
}
for i := 0; i < numsLen; i++ {
min := i
for j := i + 1; j < numsLen; j++ {
if nums[j] < nums[min] {
min = j
}
}
nums[min], nums[i] = nums[i], nums[min]
}
return nums
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = selectSort(a)
fmt.Println(a)
}
2. 进阶排序
2.1. 希尔排序——插入排序
空间复杂度O(1)、最好的情况下时间复杂度为O(nlogn)、 最坏情况时间复杂度O(n2) 、普遍时候时间复杂度为O(n1.3)
人为设定一个gap值。为了适应普遍情况，gap值初值一般设定为序列长度的1/2，每次gap值缩小一半。
由小到大：每一趟排序中，第 i 个数都要与第 i + gap 个数进行比较。如果第 i 个数大于第 i + gap 个数。就要进行位置互换。走完一趟之后，gap进行缩量操作。
走完一趟之后，每一个间隔组都是有序的。
希尔排序的基本思想是：先将整个待排序列分割成若干个子序列，对若个子序列分别进行插入排序，待整个待排序列基本有序时，对整体进行插入排序。
package main
import "fmt"
// 希尔排序
func ShellSort(arr []int) []int {
n := len(arr)
for gap := n / 2; gap >= 1; gap = gap / 2 { // 缩小增量序列，希尔建议每次缩小一半
for i := gap; i < n; i++ { // 子序列
tmp := arr[i]
j := i - gap
for ; j >= 0 && tmp < arr[j]; j = j - gap {
arr[j+gap] = arr[j]
}
arr[j+gap] = tmp
}
}
return arr
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = ShellSort(a)
fmt.Println(a)
}2.2. 快速排序——交换排序
空间复杂度O(logn)，时间复杂度O(nlogn)
算法思想：基于分治法，任取其中一个数作为枢轴，分为小于枢轴区域和大于枢轴区域，然后递归重复。
快速排序要求我们选择一个基准，根据这个基准为原数组分组，比基准大的一组，比基准小的一组，再重复递归地进行快速排序，重新合并每组排序后的序列，即为排好序的序列。
算法步骤：
选择一个基准
将比基准小的数放到基准左边，比基准大的数放到基准右边（相同的数可以放在任意一边）在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
这段代码实现了快速排序算法，但采用的是单路快速排序的方式，与传统的双路或三路快速排序有一些区别。
单路快速排序：单路快速排序只使用一个指针（索引）来分区，也就是
Partition1Way函数。这个函数以最左边的元素作为基准值（pivot），然后从左到右遍历数组，将小于基准值的元素移到基准值的左边，最后将基准值放在合适的位置上。这个方法只进行一次遍历来分区，因此是单路的。
总结来说，这段代码采用了单路快速排序方法，与传统的双路或三路快速排序相比，可能在某些情况下效率稍低，特别是当数组包含大量相同的元素时。但它依然是一个有效的快速排序实现，可以对大多数输入数据进行高效排序。如果需要更好的性能，你可以考虑实现双路或三路快速排序算法。
主函数 (
main):
创建一个整数数组
a。调用
QuickSort函数对数组进行排序。打印排序后的数组。
QuickSort 函数:
这是快速排序的入口点。它接受一个整数数组作为参数。
它调用
_QuickSort函数并传递数组、0（左边界）和数组的长度减1（右边界）。
_QuickSort 函数:
这是一个递归函数，它接受一个整数数组、左边界和右边界作为参数。
如果左边界小于右边界，它将继续执行。
它首先调用
Partition1Way函数来获取基准值的索引。然后，它对基准值左边和右边的部分递归地调用自身。
Partition1Way 函数:
这是快速排序中的分区函数。它接受一个整数数组、左边界和右边界作为参数。
它使用最左边的元素作为基准值。
通过遍历，它将所有小于基准值的元素移到基准值的左边，所有大于基准值的元素移到基准值的右边。
最后，它将基准值移到正确的位置。
它返回基准值的索引。
整个程序的工作流程是：在 main 函数中创建一个待排序的数组，然后调用 QuickSort 函数进行排序，最后打印排序后的结果。在 QuickSort 函数中，首先通过 _QuickSort 函数进行递归排序，然后在 _QuickSort 函数中通过 Partition1Way 函数进行分区，并对每个分区递归地调用 _QuickSort 函数，直到所有的元素都被正确排序。
在快速排序中，每一趟排序都会选择一个基准值（pivot），并将数组分为两部分：小于基准值的元素和大于基准值的元素。这个基准值的选择可以有多种策略，最常见的是选择数组的第一个元素、最后一个元素、中间的元素或者随机选择一个元素。在上面的代码中，基准值的选择是数组的第一个元素，也就是最左边的元素。
在分区函数 Partition1Way 中，通过一个指针 index 来记录当前小于基准值的元素的边界。初始时，index 指向基准值的右边一位。然后，从 index 开始遍历数组，如果当前元素小于基准值，就将 index 指向的元素和当前元素交换，并将 index 加1。这样，遍历完成后，index-1 就是基准值应该放置的位置。最后，将基准值和 index-1 位置的元素交换，这样就完成了分区操作。
在每次递归调用 _QuickSort 函数时，都会传递新的左边界和右边界。左边界是上次分区的边界，右边界是数组的长度减1。这样，每次递归都会对一个更小的子数组进行排序，直到所有的元素都被正确排序。
package main
import "fmt"
func QuickSort(arr []int) []int {
//主递归函数，通过调用这个函数来进行
//这个算法里的第一个基准数就是最左边的数
return _QuickSort(arr, 0, len(arr)-1)
}
func _QuickSort(arr []int, left int, right int) []int {
if left < right {
//当目前数组中最左边的数小于最右边的数时，说明该数组还未排列完成
//通过Partition1Way函数，获得基准值
partitionIndex := Partition1Way(arr, left, right)
//当获得第一个基准值之后，数组已经被分为左串和右串来进行处理。
//第一个用来处理左串
_QuickSort(arr, left, partitionIndex-1)
//第二个用来处理右串
_QuickSort(arr, partitionIndex+1, right)
}
return arr
}
// 快速排序--单路
func Partition1Way(arr []int, left int, right int) int {
// 先分区，最后把基准换到边界上
privot := left
//索引值为最左边的右边一位
index := privot + 1
//将该区域数组内最左边到最右边全部对比一遍
for i := index; i <= right; i++ {
// 当前值小于基准就交换，大于的不用管
if arr[privot] > arr[i] {
//交换后
arr[index], arr[i] = arr[i], arr[index]
// 交换后就将索引值右移
index++
}
}
// arr[index]是大于基准的
arr[privot], arr[index-1] = arr[index-1], arr[privot]
return index - 1
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = QuickSort(a)
fmt.Println(a)
}双路快速排序：传统的双路快速排序使用两个指针，一个从左边开始，一个从右边开始，它们分别向中间移动，交换不满足排序条件的元素，直到两个指针相遇。这种方法能够更均衡地分割数组，提高了对有大量重复元素的数组的性能。
双路快排（标准快排）：双指针从首尾向中间移动
package main
import "fmt"
func QuickSort(arr []int) []int {
return _QuickSort(arr, 0, len(arr)-1)
}
func _QuickSort(arr []int, left int, right int) []int {
if left < right {
partitionIndex := Partition2Way(arr, left, right)
_QuickSort(arr, left, partitionIndex-1)
_QuickSort(arr, partitionIndex+1, right)
}
return arr
}
// 快速排序--双路版
func Partition2Way(arr []int, low int, high int) int {
tmp := arr[low] // 基准
for low < high {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
for low < high && arr[high] >= tmp {
high--
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high]
// 当队首元素小于等于tmp时,向前挪动low指针
for low < high && arr[low] <= tmp {
low++
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low]
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
arr[low] = tmp
return low
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = QuickSort(a)
fmt.Println(a)
}
三路快速排序：三路快速排序进一步改进了双路快速排序，将数组分为小于、等于和大于基准值的三个部分，这对处理有大量重复元素的数组尤其有用。
三路快排：分成小于区、等于区、大于区，不对等于区进行递归操作
这段代码实现了一个三路快速排序算法（Three-Way Quick Sort），与传统的单路快速排序相比，它对处理包含大量重复元素的数组有更好的性能。
下面是对这个算法的解释：
函数定义：主函数
QuickSort3Way调用了辅助函数_QuickSort3Way来进行排序，而_QuickSort3Way函数则递归地进行三路快速排序。Partition3Way 函数：这是算法的关键部分。它接受一个数组
arr和左右边界left和right作为输入。首先，它选择数组的第一个元素arr[left]作为基准值key。三路分区：接下来，使用三个指针
lo、cur和gt来进行三路分区。这里的目标是将数组分成三个区域：小于key的部分、等于key的部分和大于key的部分。
lo是指向小于key区域的右边界，初始时与left相等。cur是当前处理的元素的指针，从left+1开始遍历数组。gt是指向大于key区域的左边界，初始时与right+1相等。
遍历数组：遍历数组中的元素，根据元素与基准值
key的大小关系，将元素放入相应的区域。
如果
arr[cur]小于key，则将它与arr[lo+1]交换，然后增加lo和cur指针。如果
arr[cur]大于key，则将它与arr[gt-1]交换，然后减小gt指针。如果
arr[cur]等于key，则将cur指针增加。
最后交换基准值：最后，将基准值
key移动到它的最终位置，即arr[lo]处。递归排序：现在数组被分为三个区域：小于
key的部分在左侧，等于key的部分在中间，大于key的部分在右侧。然后，递归调用_QuickSort3Way来分别对左侧和右侧的部分进行排序。主函数调用：在
main函数中，创建了一个包含一些整数的切片a，然后调用QuickSort3Way函数对这个切片进行三路快速排序，并最后打印排序后的结果。
这个算法相对于传统的单路快速排序，更适合处理包含大量重复元素的数组，因为它能够更均衡地分割这些元素，提高了性能。
package main
import "fmt"
// 快速排序--三路
func QuickSort3Way(arr []int) []int {
// 确定分区位置
return _QuickSort3Way(arr, 0, len(arr)-1)
}
func _QuickSort3Way(arr []int, left int, right int) []int {
if left < right {
lo, gt := Partition3Way(arr, left, right)
_QuickSort3Way(arr, left, lo-1)
_QuickSort3Way(arr, gt, right)
}
return arr
}
func Partition3Way(arr []int, left, right int) (int, int) {
key := arr[left]
lo, gt, cur := left, right+1, left+1 // lo和gt是相等区左右边界
for cur < gt {
if arr[cur] < key { // 小于key，移到前面
arr[cur], arr[lo+1] = arr[lo+1], arr[cur] // lo+1,保证最后arr[lo]小于key
lo++ // 左边界右移
cur++ // 能够确定换完之后该位置值小于key,
} else if arr[cur] > key {
arr[cur], arr[gt-1] = arr[gt-1], arr[cur]
gt-- // 从后面换到前面，不知道是否比key的大，还要再比一下，所以cur不移动
} else {
cur++
}
}
arr[left], arr[lo] = arr[lo], arr[left] // 最后移动基准，arr[lo]一定比key小
return lo, gt
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = QuickSort3Way(a)
fmt.Println(a)
}
2.3. 堆排序——选择排序
空间复杂度O(1)，时间复杂度O(nlogn)
堆排序可以抽象为完全二叉树，而非排序二叉树
堆排序有大顶堆（堆顶元素最大）和小顶堆（堆顶元素最小）。
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
创建一个堆 H[0……n-1]
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤 2，直到堆的尺寸为 1。
package main
import "fmt"
// 堆排序
func HeapSort(arr []int) []int {
//获取数组长度
arrLen := len(arr)
// 初始化大顶堆，运行建造大顶堆函数
BuildMaxHeap(arr, arrLen)
for i := arrLen - 1; i >= 0; i-- {
// 交换根节点和最后一个节点
swap(arr, 0, i)
//数组长度减一
arrLen--
//进入调整二叉树的递归函数中
heapify(arr, 0, arrLen)
}
//返回已经排序成为大顶堆的数组
return arr
}
func BuildMaxHeap(arr []int, arrLen int) {
for i := arrLen / 2; i >= 0; i-- {
heapify(arr, i, arrLen)
}
}
func heapify(arr []int, i, arrLen int) {
//根堆顶左子
left := 2*i + 1
//根堆顶右子
right := 2*i + 2
// 当前最大值位置
largest := i
//当根堆顶左子的位置不超过数组长度，并且根堆顶左子大于根堆顶点元素时，根堆顶位置被左子取代
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
//当根堆顶右子的位置不超过数组长度，并且根堆顶右子大于根堆顶点元素时，根堆顶位置被右子取代
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
//当根堆顶不再是最初进入函数时的数组中间位时
if largest != i {
// 交换数组中间位与当前最大值的元素
swap(arr, i, largest)
// 并继续调整二叉树，直至根堆顶确认为最大元素
heapify(arr, largest, arrLen)
}
}
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = HeapSort(a)
fmt.Println(a)
}首先定义了一个
HeapSort函数，它接受一个整型切片arr作为参数，并返回一个排序后的整型切片。在
HeapSort函数中，首先获取切片的长度arrLen，然后调用BuildMaxHeap函数来初始化大顶堆。接下来使用一个循环，从最后一个元素开始往前遍历，每次将根节点（最大值）与最后一个节点交换，并将数组长度减1，然后再次调用
heapify函数来调整堆。BuildMaxHeap函数用于构建大顶堆，它从数组中间位置开始向前遍历，每次调用heapify函数来调整堆。heapify函数用于调整堆，它接受三个参数：待调整的数组arr、当前节点的索引i和数组长度arrLen。在
heapify函数中，首先计算左子节点和右子节点的索引，然后找到当前节点的最大值位置largest。如果左子节点的值大于当前最大值，则更新最大值位置为左子节点的索引；如果右子节点的值大于当前最大值，则更新最大值位置为右子节点的索引。
如果最大值位置不等于当前节点的索引，说明需要交换节点，调用
swap函数进行交换，并递归调用heapify函数来调整二叉树。swap函数用于交换切片中的两个元素，它接受三个参数：待交换的元素所在的切片arr、第一个元素的索引i和第二个元素的索引j。在
main函数中，创建一个长度为10的整型切片a，并初始化为给定的值。调用
HeapSort函数对切片a进行排序，并将排序后的结果打印输出。
通过构建大顶堆，每次将根节点与最后一个节点交换，并调整堆的结构，最终得到一个升序排列的整型切片。
3. 特殊排序
3.1. 归并排序——比较类
空间复杂度O(n)，时间复杂度O(nlogn)
归并排序是采用分治法的一个典型的排序算法，将已有序的子序列合并为一个完全有序的序列。
归并排序的过程是：首先将序列拆分成子序列，然后对子序列进行排序，最后将排序好的子序列合并，就得到了一个有序的序列。
package main
import "fmt"
// 归并排序--递归版
func MergeSort(arr []int) []int {
//获取数组长度
n := len(arr)
if n < 2 {
return arr
}
//数组中间位置
mid := n / 2
//从数组开头到数组中间位置前一位。为左串
left := arr[:mid]
//从数组中间位置到数组末尾。为右串
right := arr[mid:]
//分好初始的左串右串之后，再分开处理这两串
//但是处理这两串之前需要再将这两串分别继续分化
return merge(MergeSort(left), MergeSort(right))
}
//合并函数的传入值为左串、右串，并返回一个切片数组
func merge(left, right []int) []int {
//先声明一个返回值切片
res := []int{}
//只有当左串与右串都不为零时，进入该循环
for len(left) != 0 && len(right) != 0 {
//当左串首位小于右串首位
if left[0] <= right[0] {
//返回值切片添加左串首位值
res = append(res, left[0])
// 左串将头一个直接切出去
left = left[1:]
} else {
//不然返回值切片添加右串首位
res = append(res, right[0])
// 右串将头一个直接切出去
right = right[1:]
}
}
if len(left) == 0 {
// left结束，right剩下的直接拖下来
res = append(res, right...)
}
if len(right) == 0 {
// right结束，left剩下的直接拖下来
res = append(res, left...)
}
return res
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = MergeSort(a)
fmt.Println(a)
}package main
import "fmt"
// 归并排序--迭代版
func MergeSort(arr []int) []int {
n := len(arr)
//设定一个匿名函数min，用来比较两数之间的大小，最后返回较小的那个数。
min := func(a, b int) int {
if a < b {
return a
}
return b
}
//step <<= 1中的<<是左移位运算符，相当于将二进制的step左移一位，并将结果值再转换为十进制赋予step。相当于step*2
// 外层控制步长
for step := 1; step <= n; step <<= 1 {
//offset用来表示每个分组在原数组中的初始位置
offset := 2 * step
// 内层控制分组
for i := 0; i < n; i += offset {
// 第二段头部，防止超过数组长度
h2 := min(i+step, n-1)
// 第二段尾部
tail2 := min(i+offset-1, n-1)
merge2(arr, i, h2, tail2)
}
}
return arr
}
func merge2(arr []int, h1 int, h2 int, tail2 int) {
start := h1
tail1 := h2 - 1 // 第一段尾部
length := tail2 - h1 + 1 // 两段长度和
tmp := []int{}
for h1 <= tail1 || h2 <= tail2 { // 其中一段未结束
if h1 > tail1 { // 第一段结束，处理第二段
tmp = append(tmp, arr[h2])
h2++
} else if h2 > tail2 { // 第二段结束，处理第一段
tmp = append(tmp, arr[h1])
h1++
} else { // 两段都未结束
if arr[h1] <= arr[h2] {
tmp = append(tmp, arr[h1])
h1++
} else {
tmp = append(tmp, arr[h2])
h2++
}
}
}
for i := 0; i < length; i++ { // 将排序好两段合并写入arr
arr[start+i] = tmp[i]
}
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = MergeSort(a)
fmt.Println(a)
}
这段代码定义了一个MergeSort函数，接受一个整数切片作为参数，并返回排序后的切片。在函数内部，首先获取切片的长度n，然后定义了一个辅助函数min用于比较两个整数的大小。接下来，通过一个循环来控制归并排序的迭代过程。外层循环使用变量step来控制步长，每次将步长翻倍。内层循环使用变量offset来计算每个分组的长度，并通过i += offset来控制分组的数量。在每个分组内，使用双指针法来合并两个有序的子数组。最后，将排序好的切片返回。
在main函数中，创建了一个包含一些整数的切片a，然后调用MergeSort函数对其进行排序，并将排序后的结果打印输出。
3.2. 计数排序——非比较类
空间复杂度O(k)、时间复杂度O(n+k)
计数排序的思想是将输入的数据值转化为键存储在额外开辟的数组空间中，然后按顺序把值收集起来。计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
实现步骤如下：
找出待排序的数组中最大和最小的元素。
统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
重新遍历原数组A，如果A[j]等于i，则在新数组B中放入count[i]个1，否则放入count[i]个0。
最后根据count[i]生成输出数组O。
package main
import (
"fmt"
)
// 计数排序
func CountingSort(arr []int) []int {
//获取数组长度
length := len(arr)
//直接返回长度小于2的数组
if length <= 1 {
return arr
}
//获取数组最大值
maxValue := getMaxValue(arr)
//获取最大值加一
bucketLen := maxValue + 1
//创建容量为最大值加一大小的数组切片
bucket := make([]int, bucketLen)
//声明一个索引值
sortedIndex := 0
// 统计每个元素出现的个数
for i := 0; i < length; i++ {
bucket[arr[i]] += 1
}
// 按照统计结果写入arr
for j := 0; j < bucketLen; j++ {
//只要该统计项不为零，就会一直添加到排序数组中
for bucket[j] > 0 {
// bucket[j]的值是统计结果，后面会变化，j是真正值
arr[sortedIndex] = j
sortedIndex++
bucket[j]--
}
}
return arr
}
// 获得数组的最大值
func getMaxValue(arr []int) int {
//获取数组首值
maxValue := arr[0]
//对比整个数组的值，找出最大值
for i := 1; i < len(arr); i++ {
if arr[i] > maxValue {
maxValue = arr[i]
}
}
//返回最大值
return maxValue
}
func main() {
a := []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = CountingSort(a)
fmt.Println(a)
}
CountingSort函数接受一个整数切片arr作为输入，并返回排序后的整数切片。首先，函数检查输入数组的长度，如果长度小于等于1，就直接返回原数组，因为不需要排序。
然后，函数调用
getMaxValue函数来找到数组中的最大值，以确定需要创建多大的桶（bucket）来进行计数。接下来，函数创建一个长度为
maxValue + 1的bucket切片，用于存储每个元素的计数。初始时，所有桶都被初始化为 0。随后，函数遍历输入数组
arr，对每个元素的值作为索引，将相应的桶的计数加一，以统计每个元素的出现次数。接下来，函数通过遍历桶数组，按照计数的顺序，将元素的值写回原始数组
arr中，从而完成排序。这是计数排序的核心步骤。最后，函数返回排序后的数组。
3.3. 桶排序——非比较类
空间复杂度O(n+k)、最坏时间复杂度O(n2)、最好时间复杂度O(n+k)
这段代码实现了桶排序（Bucket Sort）算法，是一种基于将元素分布到多个桶中，然后分别对每个桶中的元素进行排序，最后合并桶中的元素以完成整体排序的排序算法。
桶排序的思想是将输入数据分布到多个桶中，使得每个桶内的元素范围更小，然后对每个桶内的元素进行排序。这允许处理大量数据时更加高效，因为每个桶的大小相对较小，排序的时间复杂度通常较低。最后，将所有的桶按顺序合并，得到排序后的完整数组。桶排序在某些情况下可以非常高效，尤其是当输入数据均匀分布时。但要注意，桶排序的性能依赖于桶的数量的选择，不同的桶数量可能会导致不同的性能表现。
BucketSort函数接受一个整数切片nums和一个整数bucketNum作为输入，并返回排序后的整数切片。首先，函数计算输入数组的长度
numsLen，并找到数组中的最小值min和最大值max。这些值用于确定元素的范围，以便将元素分配到正确的桶中。接下来，函数创建一个包含
bucketNum个空桶的切片bucket，每个桶本质上是一个整数切片，用于存储元素。遍历输入数组
nums，对每个元素进行以下操作：
计算元素应该属于哪个桶，这是通过将元素归一化到合适的区间来完成的。具体计算是使用地板除法来实现的，确保元素分布在不同的桶中。
将元素插入到计算出的桶中的正确位置，以保持桶内元素的升序排序。这是通过将元素与桶中的元素逐个比较，然后将元素插入到正确的位置来实现的。
最后，函数遍历所有的桶，并将每个桶中的元素按顺序复制回原始数组
nums中，以完成整体排序。
package main
import (
"fmt"
"math"
)
// 桶排序
func BucketSort(nums []int, bucketNum int) []int {
// bucketNum：桶数量
numsLen := len(nums)
// 确定数组元素范围
min, max := nums[0], nums[0]
//找出最大值与最小值
for i := 0; i < numsLen; i++ {
if min > nums[i] {
min = nums[i]
}
if max < nums[i] {
max = nums[i]
}
}
//创建桶切片
bucket := make([][]int, bucketNum)
for j := 0; j < numsLen; j++ {
// 分桶：这里比较复杂，重点是地板除
//math.Floor 函数的作用是将浮点数向下舍入到最接近的小于或等于它的整数。这可以用于将浮点数转换为整数，或者用于获取浮点数的整数部分。
n := int(math.Floor(float64(nums[j]-min) / (float64(max-min+1) / float64(bucketNum))))
bucket[n] = append(bucket[n], nums[j])
k := len(bucket[n]) - 2
for k >= 0 && nums[j] < bucket[n][k] {
bucket[n][k+1] = bucket[n][k]
k--
}
bucket[n][k+1] = nums[j]
}
i := 0
for p, q := range bucket {
for t := 0; t < len(q); t++ {
nums[i] = bucket[p][t]
i++
}
}
return nums
}
func main() {
a := []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = BucketSort(a, 10)
fmt.Println(a)
}
分桶操作是桶排序算法的关键步骤之一，它用于将输入数组的元素分布到不同的桶中，以便对每个桶内的元素进行局部排序。以下是代码中的分桶操作的解释：
计算当前元素
nums[j]应该属于哪个桶。这是通过以下步骤完成的：
计算
nums[j]与最小值min之差，以确定元素在整个范围内的位置。将这个差值除以每个桶的宽度（
float64(max-min+1) / float64(bucketNum)），以确定元素应该在哪个桶中。地板除法 (math.Floor) 确保了结果是一个整数，表示元素属于哪个桶。n表示元素nums[j]应该属于的桶的索引。
将元素
nums[j]添加到相应的桶bucket[n]中。这是通过bucket[n] = append(bucket[n], nums[j])完成的，将元素追加到桶的末尾。执行插入排序，将新添加的元素
nums[j]插入到桶bucket[n]中的正确位置，以保持桶内元素的升序排序。这是通过以下步骤完成的：
初始化变量
k为当前桶bucket[n]中倒数第二个元素的索引，即len(bucket[n]) - 2。在循环中，从桶的倒数第二个元素向前遍历，将大于
nums[j]的元素向后移动一个位置，直到找到合适的位置将nums[j]插入。最后，将
nums[j]插入到找到的位置，确保桶内元素的升序排序。
这个分桶操作的目标是将输入数组的元素分布到不同的桶中，以便在每个桶内使用插入排序来排序局部数据。这是桶排序的核心思想之一，允许对大规模数据进行高效的排序。在排序完成后，需要将各个桶的元素按顺序合并，从而得到整体排序的结果。
3.4. 基数排序——非比较类
空间复杂度O(kn)、时间复杂度O(kn)
基数排序的限制：
基数排序的时间复杂度为O(nk)，其中n为待排序数组的长度，k为数字的位数。因此，当数字的位数很大时，基数排序的时间复杂度会很高。
基数排序是一种非比较型整数排序算法，因此不能用于浮点数或字符串等非整数类型的排序。
基数排序的稳定性取决于计数排序的稳定性。如果计数排序不稳定，则基数排序也不稳定。
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列 。
实现步骤如下：
找到待排序数组中最大数的位数n。
建立一个长度为n+1的桶，将每个元素放入对应的桶中。
对每个桶中的元素进行排序。
从桶中依次取出元素，得到有序序列。
package main
import "fmt"
// 基数排序
func RadixSort(arr []int) []int {
// 获取arr最大位数
maxn := maxBitNum(arr)
// 除数，保证商最后一位是我们想要的
dev := 1
// 需要被模的数
mod := 10
// 进行maxn次排序
for i := 0; i < maxn; i++ {
// 定义10个空桶
bucket := make([][]int, 10)
// 声明一个切片数组用于存储中间结果
result := make([]int, 0)
for _, v := range arr {
// n会取得该数的个位数
n := v / dev % mod
//根据每个数的个位数来将每个数放入相应的“桶”中
bucket[n] = append(bucket[n], v)
}
//将除数乘以10，以便于下次循环多除一位，获取下次循环所需的个位数
dev *= 10
// 按顺序存入临时数组
for j := 0; j < 10; j++ {
result = append(result, bucket[j]...)
}
// 转存到原数组（结果）
for k := range arr {
arr[k] = result[k]
}
}
return arr
}
// 获取数组的最大位数
func maxBitNum(arr []int) int {
ret := 1
count := 10
for i := 0; i < len(arr); i++ {
for arr[i] > count { // 对arr变化会修改内存里的值
count *= 10 // 所以这里对count进行放大
ret++
}
}
return ret
}
func main() {
a := make([]int, 10)
a = []int{3, 6, 8, 1, 22, 65, 77, 35, 12, 87}
a = RadixSort(a)
fmt.Println(a)
}
评论区