京公网安备11010502063487号Go 的 sort 和 slices 包用的是 pdqsort,它会识别已排序、逆序、全相等这些模式。这篇用七种输入形状、四种排序函数各排 100 万个整数,看速度差别,再验证“不稳定”到底有多不稳定,并读源码里的 12 个元素阈值与堆排序兜底。
输入形状(100 万个 int) slices.Sort sort.Ints sort.Slice SliceStable 随机 60.8 ms 61.1 ms 102.5 ms 334.0 ms 已排序 0.6 ms 0.6 ms 2.1 ms 2.9 ms 逆序 0.9 ms 0.9 ms 3.2 ms 58.9 ms 全部相等 0.6 ms 0.6 ms 2.0 ms 2.9 ms 只有 10 种取值 9.8 ms 9.8 ms 18.9 ms 129.0 ms 管风琴形(先升后降) 17.9 ms 17.8 ms 48.7 ms 47.8 ms 已排序但末尾 1% 乱序 37.9 ms 37.8 ms 89.7 ms 17.5 ms
已排序、逆序、全部相等的输入,slices.Sort 只要 0.6–0.9 ms,接近线性扫描一遍;只有 10 种取值也只要 9.8 ms,约为随机的六分之一。这就是 pdqsort 的“模式击败”。同样排随机数据:slices.Sort 60.8 ms 与 sort.Ints 61.1 ms 一样快,sort.Slice 要 102.5 ms(比较函数通过闭包调用),sort.SliceStable 要 334.0 ms。能用 slices.Sort 就用它。
10 万条记录,100 种键:sort.Slice(不稳定)之后,键相等的相邻记录里原始顺序颠倒的有 49962 对 sort.SliceStable 之后:0 对 slices.SortFunc(不稳定)之后:49962 对 slices.SortStableFunc 之后:0 对
不稳定排序之后,相等键的相邻记录有 49962 对(接近一半)顺序被颠倒;稳定排序是 0 对。需要“同键按原顺序”就必须明确用稳定版本。有意思的是几乎有序的输入(末尾 1% 乱序)稳定排序只要 17.5 ms,比不稳定的 37.9 ms 还快。
// limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
func pdqsort_func(data lessSwap, a, b, limit int) {
const maxInsertion = 12
if length <= maxInsertion {
heapSort_func(data, a, b)
slices/zsortordered.go:The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.
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.pdqsort 的短片段阈值是 12 个元素(用插入排序),“坏枢轴”用完 limit 就回退到堆排序,保证最坏情况不会退化成平方级。slices 的注释说明它没有 BlockQuicksort 的优化。我没有构造专门击败枢轴选择的输入来验证堆排序回退。