pattern-defeating-quicksort简介
pdqsort是一种不稳定的混合排序算法，采用了快速排序和插入排序的结合，以避免快速排序在小数组上的性能下降。
pdqsort还使用了一些模式避免技术，以减少分支预测错误和缓存行不命中的次数。这些优化使得pdqsort在各种情况下都表现良好，尤其是对于大型、随机分布的数据集。
pdqsort已经被广泛应用于各种编程语言和库中，如Go1.19 Rust、C 等。
复杂度
- 最好的情况：O(n)
- 平均情况：O(n*logn)
- 最坏的情况：O(n*logn)
pdqsort的不同版本
第一个版本
- 应对短序列时，算法会使用插入排序，中序列或长序列则使用快速排序；
- 如果快速排序效果表现不佳时，则切换成堆排序
何时会认为快速排序的效果表现不佳？
当计算累计mmm 轮（这里的 m=f(n)m=f(n)m=f(n) ， f(n)f(n)f(n) 是一个关于序列长度的函数）选取的 pivot 在本轮结束后的位置离数组两端距离小于 n/8n/8n/8 时，即判定快速排序效果表现不好。
总结：结合插入排序、快速排序和堆排序三种排序优势。
第二个版本
在第一个版本中，由于快速排序的速度制约着pdqsort的整体排序效率。
第二个版本主要优化快速排序，具体是优化快速排序中的选取基数pivot的代码。
关于pivot的选择
- 使用首个元素作为
pivot：业务简单，但往往表现不佳，特别是在数组有序的情况。 - 遍历数组，寻找数组中位数：遍历迭代的代价高，综合表现得性能不好，尽管能带来很不错的效果。
- 平衡寻找
pivot所需要的开销及pivot带来的性能优化：寻找近似中位数。
前两个属于比较极端的选法，而算法需要权衡pivot选取的有效性，也要考虑选取pivot的代价，第三种就是这样做的。
近似中位数选取方法如下：
- n⩽8n⩽8n⩽8 时在纯快排里
pivot会直接选固定元素，但在pdqsort里这种规模的序列会直接用插入排序。 - n⩽50n⩽50n⩽50 时，采样三个元素，选择三个元素中的中位数。
- n>50n>50n>50 时，采样九个元素，选择九个元素中的中位数。
第三个版本
主要解决如何优化重复元素很多的情况
- 重复元素较多的情况(partitionEqual)
- 当检测到此时的 pivot 和上次相同时(发生在 leftSubArray)，即partition进行了无效分割，此时认为pivot的值为重复元素，使用 partitionEqual 将重复元素排列在一起，减少重复元素对于 pivot 选择的干扰
- 当 pivot 选择策略表现不佳时，随机交换元素
- 避免一些极端情况使得 QuickSort 总是表现不佳，以及一些黑客攻击情况
