【go】pdqsort

1.排序算法

1. 插入排序

将元素不断插入已排序的序列中。即不断交换，直到找到第一个比其小的元素。

2. 堆排序

利用堆的性质,构造一个大顶堆,将最大元素交换到最后一个位置，调整整个堆，如此反复

3. 快速排序

递归，不断分割序列直到序列整体有序。选定一个pivot,使用pivot分割序列，分成元素比pivot大和元素比pivot小的两个序列。
当pivot为中点，快排表现最好；当pivot选择为最大/最小元素时，快排表现最差。

实际场景下，根据序列长度划分后进行benchmark(16/128/1024)

• 完全随机情况下，短序列时插入排序最快，中、长序列时快排最快，但堆排序和快排的区别不大
• 完全有序情况下，插入排序最快
• 任何情况下，堆排序的表现比较稳定

2. pattern-defeating-quicksort

该算法结合三种排序算法的优点：

• 短序列，使用插入排序
• 其他情况用快排保证整体性能
• 当快排表现不佳时，使用堆排序保证最坏情况下的时间复杂度

短序列的长度为多少？12-32，在go语言的实现版本中，将短序列的长度选定为12。
何时从快排切换到堆排序？最终pivot距离序列两端距离小于length/8判定为快排表现不佳，这种情况次数达到bits.Len(length)时，切换为堆排序。bits.Len(length)表达的是一种阈值。

1. 关键点

• pivot的选择：需要平衡寻找pivot的成本和pivot带来的性能
  • 首个元素
    • 实现简单，但完全有序情况效果不好
  • 中位数
    • 需遍历数组，性能不好,当array 的长度太长的话，寻找真正的 median 是一个非常昂贵的操作，需要存储所有的 items
  • 近似中位数，根据序列长度不同决定选择策略
    • 短序列(<=8),选择固定元素
    • 中序列(<=50),采样三个元素
    • 长序列(>50),采样九个元素
• pivot的采样方式可以让我们探知当前的序列状态
  • 采样元素逆序–>序列可能逆序–>翻转序列
  • 采样元素顺序–>序列可能顺序–>使用插入排序，有限制次数的插入排序
• 优化重复度较高的情况
  • 如果两次partition生成的pivot相同，即partition进行了无效分割，此时任务pivot的值为重复元素，limit-1，随机交换元素

2. 函数解析

1. choosePivot：选择pivot

支持三种选择方法：静态选择、三数取中、Tukey’s ninther
当数组长度大于等于 8 时，选择1/4、2/4、3/4处，在这三个位置中再找一个中位数作为最终的枢轴 如果长度大于等于 50 时，选择1/4、2/4、3/4处及其每处的相邻元素(共9个元素)的中位数作为最终的枢轴

swaps：寻找中位数的过程中的交换次数

• 当swaps值为12(4*3)时，说明选择的pivot为降序，需要翻转序列(reverseRange)
• 当swaps值为9，数据可能顺序排列

2. partialInsertionSort：局部插入排序

当选择的pivot递增时，原始序列可能也递增，此时需要对序列进行局部插入排序。 该插入排序最多处理5对乱序元素，遍历序列发现乱序元素后，同时向两边移动乱序元素。 返回值含义：

• true：数组已经完全有序
• false：
  1. 数组太小（<50）
  2. 处理了5次仍未完全有序
  3. 数组可能需要更多的排序操作

3. partitionEqual: 处理大量重复元素的情况

a > 0 && !data.Less(a-1, pivot)的条件保证了此次数组中不存在小于枢轴值的元素，首次执行时a==0，不会执行该逻辑。
将枢轴移动到数组开头，找到第一个大于和等于枢轴的元素，交换位置。
如[3, 3, 3, 3, 5, 5, 3, 6, 3]，pivot = 3，运行后变为：[3 | 3, 3, 3, 3, 3, 3 | 5, 5, 6]，返回值 i 指向第一个大于3的位置

4. partition：根据pivot进行排序

将数组分成两部分：小于枢轴值的元素和大于等于枢轴值的元素，和一般的快排中partition本质一致。
在分区前会进行一个提前检查，若扫描发现原始数组已分区，则无需再次分区，alreadyPartitioned返回true。

5. breakPatterns：当分区不平衡时，打乱数据

通过随机交换中间位置的元素来打破数组中可能导致快速排序分区不平衡的模式 只处理中间位置附近的三个元素，使用xorshift 随机数生成器

• idx := a + (length/4)*2 - 1 为什么不直接写成a+length/2-1？
  更清晰的语义表达，(length/4)*2 表示将数组分成四等份，取中间位置（第二个和第三个四分位之间），更直观地表达了"我们要处理的是数组中间部分"的意图

3. 变量解析

4. 总结

本质上pdqsort是结合三种常用排序的优缺点的混合排序方式，基于benchmark编码，根据场景判断后选择合适的排序方式。

5.参考

https://talkgo.org/t/topic/4342
https://mp.weixin.qq.com/s/5HqfRGqPyAhFt0krPgMHOQ

This is a page about »PdqSort«.