Go排序
术语说明：
- n: 数据规模
- k: “桶”的个数
- In-place: 占用常数内存，不占用额外内存
- Out-place: 占用额外内存
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
- 内排序：所有排序操作都在内存中完成
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
仓库地址：https://github.com/qingbo1011/go-sort
冒泡排序
冒泡排序（Bubble Sort）：
- 比较相邻元素，如果前者比后者大，则进行位置交换
- 从第一个开始比较到未确定位置的最后一个，每经过一轮，则代表当前最大的数到达本次最后的位置
代码如下：
1 | package main |
时间复杂度：
- 最坏：如果是倒序，则需要比较 n-1 + n-2 + n-3 +…+1=n(n-1)/2次，为O(n^2)
- 平均：O(n^2)
- 最好：如果数组本来就是有序的，则经过一轮比较即可，共需要比较n-1次，时间复杂度是 O(n)
空间复杂度：使用常数个辅助单元O(1)
稳定性：稳定，因为 i>j时，A[i]=A[j]，不会进行交换
选择排序
选择排序(Selection sort)：每一次选出最小者直接交换到左侧，省出了多余的元素交换。
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(n^2)
- 平均：O(n^2)
- 最好：O(n^2)
空间复杂度：O(1)
稳定性：不稳定。当数列包含多个值相等的元素时，选择排序有可能打乱它们的原有顺序。
插入排序
插入排序（Insertion Sort）：维护一个有序区，把元素一个一个插入到有序区的适当位置，直到所有元素有序为止。
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(n^2)：切片是逆序的
- 平均：O(n^2)
- 最好：O(n)： 切片本身就已经是有序了
空间复杂度：O(1)
稳定性：稳定
希尔排序
希尔排序（Shell Sort）：设置希尔增量每次折半，逐步分组进行粗调，最后进行插入排序。
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(n^2)（最坏就等于插入排序了）
- 平均：O(nlogn)
- 最好：O(n^1.3)
空间复杂度：O(1)
稳定性：不稳定
归并排序
归并排序（Merge Sort）：最小分组比较，依次合并
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(nlogn)
- 平均：O(nlogn)
- 最好：O(nlogn)
空间复杂度： O(n)
稳定性：稳定
快速排序
快速排序（Quick Sort）：快排是面试时经常会要写的排序算法。
分治思想：快速排序是从冒泡元素演变而来。在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，速度较快。
- 在待排序的元素任取一个元素作为基准（通常选第一个元素，但最好的方法是从待排序元素中随机选取一个为基准），称为基准元素（pivot）
- 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比基准元素小的放在它的左边
- 对左右两个分区重复以上步骤，直到所有的元素都是有序的
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(n^2) ：选取的pivot，最终只能确定1个元素位置（如
s := []int{1,2,3,4,5,6}，每次都选第一个元素作为pivot，那么第一次只能确定1的位置，第二次只能确定2的位置。。。）- 平均：O(nlogn)
- 最好：O(nlogn)：每次选择的pivot正好是中位数
空间复杂度：
- 平均：O(logn)
- 最坏：O(n)
稳定性：不稳定，因为基准元素的比较和交换是跳跃进行的
堆排序
堆排序（Heap Sort）：利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。（本质是完全二叉树，根节点为最大值或者最小值）
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(nlogn)
- 平均：O(nlogn)
- 最好：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定
计数排序
计数排序（Counting Sort）：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求数据必须是有确定范围的整数。
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
说的直白一点，就是把把最小值和最大值范围内的所有可能数列举出来，然后原数组中的数字出现的个数进行计数。（思路非常简单）
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(n+k)
- 平均：O(n+k)
- 最好：O(n+k)
空间复杂度：O(k)
稳定性：稳定
桶排序
桶排序（Bucket Sort）：桶排序就是把数值按照范围进行划分，把数值依次放入一个个划分的范围内，称之为 桶，然后在桶内进行排序，然后依次输出每个桶的值。（桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。）
- 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；（注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。）
- 从不是空的桶里把排好序的数据拼接起来。
、
代码如下：
1 | package main |
时间复杂度：
- 最坏： O(n^2)
- 平均： O(n+k)
- 最好： O(n+k)
空间复杂度： O(n+k)
稳定性：稳定
基数排序
基数排序（Radix Sort）：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
代码如下：
1 | package main |
时间复杂度：
- 最坏：O(n*k)
- 平均：O(n*k)
- 最好：O(n*k)
空间复杂度：O(n+k)
稳定性：稳定
不同情况下排序选择
总结来看：快速排序和希尔排序在排序速度上表现是比较优秀的，而归并排序次之。
On average, quicksort performs better than shell sort; but shell sort is more efficient than quicksort when the given data is already/almost sorted.
Shell sort does not require stack calls, whereas quicksort does.
平均而言，快速排序比希尔排序性能更好; 但是，当给定数据已经或几乎排序时，希尔排序比快速排序更有效。希尔排序不需要堆栈调用（递归），而快速排序需要。
我们用Go来实际benchmark一下。（选择插入排序、快速排序和堆排序，因为Go sort包中主要用到了这几种排序）
根据序列元素排序情况划分：
- 完全随机的情况（random）
- 有序/逆序的情况（sorted/reverse）
- 元素重复度较高的情况（mod8）
在此基础上，还需要根据序列长度的划分（16/128/1024）
| 序列元素排序情况 | 序列长度 | 排序算法比较结果 |
|---|---|---|
| random | 短序列 | 插入>堆排>快排 |
| sorted | 短序列 | 插入>堆排>快排 |
| reverse | 短序列 | >> |
| mod8 | 短序列 | >> |
| random | 中序列 | 快排>堆排>插入 |
| sorted | 中序列 | 插入>堆排>快排 |
| reverse | 中序列 | >> |
| mod8 | 中序列 | >> |
| random | 长序列 | 快排>堆排>插入 |
| sorted | 长序列 | 插入>堆排>快排 |
| reverse | 长序列 | >> |
| mod8 | 长序列 | >> |
总结：
- 在random情况下：
- 插入排序在短序列中速度最快
- 快速排序在其他情况下速度最快
- 堆排序相较于快速排序差距不大
- 在sorted情况下：
- 插入排序最快
- 所有短序列和元素有序情况下，插入排序性能最好
- 在大部分情况下，快速排序有较好的综合性能
- 几乎在任何情况下，堆排序的表现都比较稳定
形象比喻：
- 插入排序 —> 单车
- 快速排序 —> 汽车
- 堆排序 —> 地铁
Go sort包
go sort 包实现了四种基本排序算法：插入排序、归并排序、堆排序和快速排序。但是这四种排序方法是不公开的，它们只被用于sort包内部使用。所以在对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了sort.Interface定义的三个方法：
- 获取数据集合长度的
Len()方法 - 比较两个元素大小的
Less()方法 - 交换两个元素位置的
Swap()方法
就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。 除此之外，为了方便对常用数据类型的操作，sort包提供了对[]int切片、[]float64切片和[]string切片完整支持，主要包括：
- 对基本数据类型切片的排序支持
- 基本数据元素查找
- 判断基本数据类型切片是否已经排好序
- 对排好序的数据集合逆序
对切片进行排序
这里主要介绍sort包对[]int切片、[]float64切片和[]string切片完整支持。
前面已经提到，sort包原生支持
[]int、[]float64和[]string三种内建数据类型切片的排序操作，即不必我们自己实现相关的Len()、Less()和Swap()方法。
对于[]int切片、[]float64切片和[]string切片，直接调sort包排序即可。
[]int排序和查找
对[]int切片排序常使用sort.Ints()。
代码如下：
1 | package main |
查找：
1 | package main |
注意，SearchInts()的使用条件为：切片s已经升序排序 。以下是一个错误使用的例子：
1 | s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据 |
sort包定义了一个IntSlice类型，并且实现了sort.Interface接口：
2
3
4
5
6
7
8
9
func (p IntSlice) Len() int { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
//IntSlice 类型定义了 Sort() 方法，包装了 sort.Sort() 函数
func (p IntSlice) Sort() { Sort(p) }
//IntSlice 类型定义了 SearchInts() 方法，包装了 SearchInts() 函数
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }并且提供的
sort.Ints()方法使用了该IntSlice类型：
所以，对[]int切片排序更常使用
sort.Ints()，而不是直接使用IntSlice类型。如果要查找整数 x 在切片 a 中的位置，相对于前面提到的 Search() 方法，sort包提供了 SearchInts():
[]float64排序和查找
排序：
1 | package main |
查找：（注意同样是要求已经升序排序的切片）
1 | package main |
Float64Slice内部实现：
2
3
4
5
6
7
func (p Float64Slice) Len() int { return len(p) }
func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || isNaN(p[i]) && !isNaN(p[j]) }
func (p Float64Slice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p Float64Slice) Sort() { Sort(p) }
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }与 Sort()、IsSorted()、Search() 相对应的三个方法：
2
3
func Float64sAreSorted(a []float64) bool
func SearchFloat64s(a []float64, x float64) int要说明一下的是，在上面 Float64Slice 类型定义的 Less 方法中，有一个内部函数
isNaN()。 isNaN() 与math包中IsNaN()实现完全相同，sort包之所以不使用 math.IsNaN()，完全是基于包依赖性的考虑，应当看到，sort包的实现不依赖与其他任何包。
[]string排序和查找
两个string对象之间的大小比较是基于字典序的。
排序：
1 | package main |
查找：（注意同样是要求已经升序排序的切片）
1 | package main |
数据集合排序
参考 go sort包用法
下面是一个使用 sort 包对学生成绩排序的示例：
1 | package main |
[]interface排序和查找
参考 go sort包用法
在gin-IM项目中，我们对从MangoDB查询出来的数据放到了slice中，并使用
sort.Slice对其中的StartTime进行了升序排序（自然排序）。先看个例子：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import (
"fmt"
"sort"
)
type Student struct {
name string
age int
}
func main() {
s1 := Student{"张三", 18}
s2 := Student{"tom", 28}
s3 := Student{"王五", 14}
s4 := Student{"jack", 21}
students := make([]Student, 0)
students = append(students, s1, s2, s3, s4)
fmt.Println(students) // [{张三 18} {tom 28} {王五 14} {jack 21}]
sort.Slice(students, func(i, j int) bool {
return students[i].age < students[j].age
})
fmt.Println(students) // [{王五 14} {张三 18} {jack 21} {tom 28}]
}
通过前面的内容我们可以知道，只要实现了 sort.Interface 接口，即可通过 sort 包内的函数完成排序，查找等操作。并且 sort 包已经帮我们把[]int，[]float64，[]string 三种类型都实现了该接口，我们可以方便的调用。但是这种用法对于其它数据类型的 slice 不友好，可能我们需要为大量的 struct 定义一个单独的 []struct 类型，再为其实现 sort.Interface 接口，类似这样：
1 | type Person struct { |
sort 包提供了以下函数：
1 | func Slice(x any, less func(i, j int) bool) |
通过函数签名可以看到，排序相关的三个函数都接收 any，并且需要传入一个比较函数，用于为程序比较两个变量的大小，因为函数签名和作用域的原因，这个函数只能是匿名函数。
文字说那么多反而看起来复杂，直接看代码就能看懂。
sort.Slice
排序稳定性：不稳定。
Slice sorts the slice x given the provided less function.It panics if x is not a slice.
The sort is not guaranteed to be stable: equal elements may be reversed from their original order.For a stable sort, use SliceStable.
The less function must satisfy the same requirements as the Interface type’s Less method.
例子：
1 | package main |
sort.SliceStable
排序稳定性：稳定。
SliceStable sorts the slice x using the provided less function, keeping equal elements in their original order.
It panics if x is not a slice.
The less function must satisfy the same requirements as the Interface type’s Less method.
例子：
1 | package main |
sort.SliceIsSorted
判断给定slice是否为有序。
SliceIsSorted reports whether the slice x is sorted according to the provided less function.
It panics if x is not a slice.
例子：
1 | package main |
sort.Search
判断 []interface 是否存在指定元素。
sort 中包为 []int，[]float64，[]string 提供的 Search 函数其实也是调用的该函数，因为该函数是使用的二分查找法，所以要求 slice 为升序排序状态。并且判断条件必须为 >=，这也是官方库提供的三个查找相关函数的的写法。
例子：
1 | package main |
如果 slice 是降序状态，而我们又不想将其变为升序，只需将判断条件由
>=变更为<=即可。推荐采用升序排列及相应的判断条件，与官方函数保持风格一致。
进阶：pdqsort
之前在字节青训营的学习中，学习了从零开始打造目前业界性能一流的排序算法pdqsort（Pattern-Defeating-QuickSort）。这里简单记录一下。（将来会是Go1.19的默认排序算法）
我们都知道Go的sort包里已经给我们设计好了排序算法。那么Go的排序算法有提升空间吗？
什么是最快的排序算法？
- Python中使用timsort
- C++中使用introsort
- Rust中使用pdqsort
- Go(<=1.18)使用introsort
字节团队内部在21年10月的时候将自己的想法提供给了官方。sort: use pdqsort #50154
pdqsort重新实现了Go的排序算法，在某些常见场景中比之前算法快了~10倍，成为Go1.19的默认排序算法。
| Best | Avg | Worst | |
|---|---|---|---|
| InsertionSort | O(n) | O(n^2) | O(n^2) |
| QuickSort | O(n*logn) | O(n*logn) | O(n^2) |
| HeapSort | O(n*logn) | O(n*logn) | O(n*logn) |
| pdqsort | O(n) | O(n*logn) | O(n*logn) |
pdqsort（pattern-defeating-quicksort）是一种不稳定的混合排序算法，它的不同版本被应用在C++ BOOST、Rust以及Go1.19中。它对常见的序列类型做了特殊的优化，是的在不同条件下都能拥有不错的性能。
pdqsort - version1
结合三种排序方法的优点：
- 对于短序列（小于一定长度）我们使用插入排序
- 其他情况，使用快速排序来保证整体性能（选择首个元素作为pivot）
- 当快速排序表现不佳时，使用堆排序来保证最坏情况下时间复杂度仍然为O(n*logn)
Q&A：
- 短序列的具体长度是多少呢？
- 12~32，在不同语言和场景下会有不同，在泛型版本根据测试选定24
- 如何得知快速排序表现不佳，以及如何及时切换到堆排序？
- 当最终pivot的位置离序列两端很近时（距离小于length/8），判定其表现不佳，当这种情况的次数达到limit（即bits.Len(length)）时，切换到堆排序
pdqsort - version2
如何让pdqsort速度更快？
- 尽量使得QuickSort的pivot为序列的中位数（改进pivot）
关于pivot的选择：
- 使用首个元素作为pivot（最简单的方案）
- 实现简单，但是效果往往不好，例如在sorted情况下性能很差
- 遍历数组，寻找真正的中位数
- 遍历比对代价很高，性能不好
我们要在平衡
寻找pivot所需要的开销和pivot带来的性能优化。
最终的解决方案是：寻找近似中位数！
优化pivot选择：根据序列长度的不同，来决定选择策略
短序列（<=8），选择固定元素（忽略，短序列直接采用插入排序了）- 中序列（<=50），采样三个元素，取中位数
- 长序列（>50），采样九个元素，去中位数
这里顺带引出：pivot的采样方式使得我们有探知序列当前状态的能力。
- 采样的元素都是逆序排序 —> 序列可能已经逆序 —> 翻转整个序列
- 采样的元素都是顺序排序 —> 序列可能已经有序 —> 使用插入排序
（注意：插入排序实际使用partiallnsertionSort，即有限制次数的插入排序。为了防止因为误判而all in插入排序从而影响性能。）
version1升级到version2优化总结：
- 升级pivot选择策略（近似中位数）
- 发现序列可能逆序，则反转序列（应对reverse场景）
- 发现序列可能有序，使用有限制插入排序（应对sorted场景）
pdqsort - final version
最后，还有什么场景我们没有优化？
- 短序列情况
- 使用插入插入（version1）
- 极端情况
- 使用堆排序保证算法可行性（verison1）
- 完全随机的情况（random）
- 更好的pivot选择策略（version2）
- 有序/逆序的情况（sorted/reverse）
- 根据序列状态翻转或者插入排序（version2）
最后还需要优化的场景：如何优化重复元素很多的情况？
采用pivot的时候检测重复度？
- 不是很好，因为采样数量有限，不一定能采样到相同元素
解决方案：如果两次partition生成的pivot相同，即partition进行了无效分割，此时认为pivot的值为重复元素。
优化重复元素较多的情况：
- 当检测此时pivot和上次相同时（发生在leftSubArray），使用partitionEqual将重复元素排列在一起，减少重复元素对于pivot选择的干扰
当pivot选择策略表现不佳时：随机交换元素。（避免一些极端情况使得QuickSort总是表现不佳，以及黑客攻击情况）
标黄可能发生也可能不发生。
