【算法】pdqsort

pdqsort介绍

pdqsort（Pattern-defeating quicksort）是一种融合插入排序,堆排序和优化后的快排的新型排序算法，rust和go1.19中采用；

时间复杂度

Best	Avg	Worst
O(n)	O(n*logn)	O(n*logn)

整体流程图

image.png

为了理解上图，我们先回顾一下三个基本的排序算法

插入排序

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))时，切换到堆排序

[图片上传失败...(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)]