pdqsort介绍
pdqsort（Pattern-defeating quicksort）是一种融合插入排序,堆排序和优化后的快排的新型排序算法，rust和go1.19中采用；
时间复杂度
| Best | Avg | Worst |
|---|---|---|
| O(n) | O(n*logn) | O(n*logn) |
整体流程图
为了理解上图，我们先回顾一下三个基本的排序算法
插入排序
| Best | Avg | Worst |
|---|---|---|
| O(n) | O(n^2) | O(n^2) |
如果原始数组接近有序的情况下，最好O(n)，逆序时最坏O(n^2)
堆排序
| Best | Avg | Worst |
|---|---|---|
| O(n*logn) | O(n*logn) | O(n*logn) |
堆排序无论何种情况，都要建堆再依次出堆，都是O(n*logn)
快速排序
| Best | Avg | Worst |
|---|---|---|
| O(n*logn) | O(n*logn) | O(n^2) |
快排的性能跟pivot的选取相关
如果每次pivot都能将数组均分为两个部分，达到最好O(nlogn)，可以看作一棵完全二叉树，pivot是每一层的结点，每层都要比较n次，树的高度是logn，所以是nlogn；
而如果每次pivot都是数组最值（最大或者最小），最差O(n^2)；
benchmark
根据序列元素排列情况划分
完全随机的情况
有序|逆序的情况
元素重复度较高的情况（mod 8）
在此基础上，还需要根据序列长度划分（16/128/1024）
短序列时插入排序最快
[图片上传失败...(image-6b51d6-1680024129373)]
有序时插入排序最快
[图片上传失败...(image-8de03d-1680024129373)]
结论
短序列和有序情况下，插入排序最优；大部分情况（无序，中长序列）快速排序略优于堆排序
pdqsort实现思路
version1
-
短序列时采用采用
插入排序- 具体长度12~32，不同语言和场景会有不同，在泛型版本根据测试选定24
其他情况，使用
快排来保证整体性能-
当
快排表现不佳时，使用堆排序来保证最坏情况下时间复杂度仍然是O(n*logn)- 当pivot的位置离序列两端很接近时（距离小于length/8）判定其表现不佳，当这种情况的次数达到limit（bits.Len(length))时，切换到
堆排序
- 当pivot的位置离序列两端很接近时（距离小于length/8）判定其表现不佳，当这种情况的次数达到limit（bits.Len(length))时，切换到
[图片上传失败...(image-aad420-1680024129373)]
version2
pivot选择
-
使用首个元素作为pivot（最简单方案）
实现简单，但是往往效果不好，例如在有序的情况下表现很差
-
遍历数组，寻找真正的中位数
遍历代价很高，性能不好
寻找近似中位数
短序列（<=8），选择固定元素（此时会使用
插入排序）中序列（<=50），采样三个元素，median of three
长序列（>50），采样九个元素，median of medians
pivot采样方式探知序列当前状态的能力
采样元素都是逆序=>序列可能已经逆序=>翻转整个序列
采样元素都是正序=>序列可能已经有序=>使用
插入排序
注：插入排序实际使用的是partialInsertionSort，即有限次数的插入排序
[图片上传失败...(image-9ac8c-1680024129373)]
final version
-
重复元素较多的情况（partitionEqual）
当检测到pivot和上次相同时（发生在leftSubArray），使用partitionEqual将重复的元素排列在一起，减少重复元素对于pivot选择的干扰
-
当pivot选择策略表现不佳时，随机交换元素（break patterns）
避免一些极端情况使得
快排总是表现不佳，以及一些黑客攻击情况
[图片上传失败...(image-82cc08-1680024129373)]
