概述
我们在写代码时常常使用Arrays.sort()方法给数组排序，但是背后的实现算法是怎么样的呢，深入到这个方法内部，我们会发现一个叫做DualPivotQuicksort的类，这个类诞生于jdk1.7版本，从字面上就可以看出是快速排序的改进版。
传统快排
对于传统的快速排序来说，我们并不陌生，数据结构课程上就学过。这个算法早在1960年被提出，在实际应用中使用比较广泛。核心思想是：选择一个基准元素(pivot)，通过一趟排序，把小于基准元素的数据移动到左边，大于基准元素的数据移动到右边，这样就把数据分割成左右两部分，然后再通过递归的方式分别进行排序，直到完全有序。
这种算法之所以被称为快速排序，说明算法的效率相比之下已经很好，时间复杂度平均在O(nlogn)级别。那么双轴快排是如何对传统快排做改进的呢。
双轴快排
从名字上基本可以看出这个算法的大体思想，传统快排中pivot的概念，是用来分割数据的，那么Dual-Pivot其实就是用两个Pivot, 把整个数组分成三份。伪代码如下：
dualPivotQuicksort(A,left,right) // 对数组A[left...right]进行排序
if right−left ≥ 1
// 选取两端的值作为轴
p = min {A[left],A[right]}
q = max{A[left],A[right]}
r = left +1; g = right −1; k = r
while k ≤ g
if A[k] < p
swap A[k] and A[r]; r = r+1
else if A[k] ≥ q
while A[g] > q and k < g
g = g-1
end while
swap A[k] and A[g]; g = g −1
if A[k] < p
swap A[k] and A[r]; r = r+1
end if
end if
k = k +1
end while
r = r−1; g = g +1
A[left] = A[r]; A[r] = p // p到最终的位置
A[right] = A[g]; A[g] = q // q到最终的位置
dualPivotQuicksort(A, left , r−1)
dualPivotQuicksort(A, r+1, g −1)
dualPivotQuicksort(A, g+1, right)
end if
下面的示意图可以比较直观的看出双轴快速排序的思想
image.png
1、选择两个值P1、P2作为轴，P1<P2
2、将整个数组分为四部分
part1：比P1小的元素
part2：比P1大但是比P2小的元素
part3：待比较区域
part4：比P2大的元素
3、从第四部分选出一个元素a[K]，与两个轴心比较，然后放到第一二三部分中的一个
4、移动L，K，G指向
5、重复 3和4 步，直到第四部分为空
6、将P1与第一部分的最后一个元素交换，将P2与第三部分的第一个元素交换
7、递归第一二三部分的数组
JDK源码
jdk中是怎样实现的双轴快速排序算法的呢。Arrays.sort()对不同类型的数组都做了支持，这里以int类型数组为例，首先看一下sort方法。
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
方法里直接调用了DualPivotQuicksort类的sort方法，方法注释上可以看到，这种算法的性能表现要好于传统的单轴快排。
进到方法内部，可以看到这个方法的实现还是比较复杂的。简单扫一眼代码，发现这个方法并没有直接对数组进行排序，而是进行各种判断和对数组的初步估算，根据不同的情况选择最适合的算法。所以虽然说这个类叫做DualPivotQuicksort，但是里面做的事情不仅仅只是算法的实现。
// 指部分数组有序的次数
private static final int MAX_RUN_COUNT = 67;
// 相同元素的最大数量，如果相同元素多，就使用快排
private static final int MAX_RUN_LENGTH = 33;
// 如果数组长度小于这个值，使用快排代替归并排序
private static final int QUICKSORT_THRESHOLD = 286;
static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
// 如果数组长度小于286，那么优先使用快速排序，而不是归并排序（Timsort）
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
// 下面这一大段代码主要用于判断数组是否适合使用归并排序，也就是Timsort
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) {
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) {
while (++k <= right && a[k - 1] >= a[k]);
for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
}
} else {
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
// 使用快排算法
sort(a, left, right, true);
return;
}
}
}
// 不适合使用归并排序，使用快排
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
...... // 省略后面的归并排序逻辑
}
首先这个方法进行了一个判断，当数组长度小于常量QUICKSORT_THRESHOLD的时候，那么直接使用快速排序。
如果数组长度大于286的时候，先对数组进行一个初步判断，看看是否适合使用归并排序。如果数组每个区块都近似有序，并且递增变递减的次数没有超过MAX_RUN_COUNT次数，那就使用归并排序（Timsort算法）进行排序，反之，就使用快速排序。到这里，还没有真正进入到双轴快速排序的核心逻辑，再深入一层看看。
接下来的代码依然比较复杂，大概有300多行代码，而且变量名称也是算法类代码中比较常见的a、i、j、k之类的，所以这里只贴出部分核心逻辑。
// 如果数组长度小于这个值，就直接使用插入排序代替快速排序
private static final int INSERTION_SORT_THRESHOLD = 47;
private static void sort(int[] a, int left, int right, boolean leftmost) {
int length = right - left + 1;
// 对于小数组来说直接用插入排序
if (length < INSERTION_SORT_THRESHOLD) {
// 使用插入排序（传统插入排序或者优化过的双插入排序）
...... //省略
}
// 下面是选取轴的过程
// 先算出数组1/7的近似值
int seventh = (length >> 3) + (length >> 6) + 1;
// 找到数组的中间位置e3，然后再向左向右找出4个等间距的位置，加上中点一共有5个位置
int e3 = (left + right) >>> 1;
int e2 = e3 - seventh; // 往左
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
// 使用简单的插入排序对这5个点进行排序
if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }
...... //省略5个点的排序过程
// 定义指针
int less = left; // 中间部分的起始位置
int great = right; // 最右边部分的起始位置
// 对于5个元素全都不相等的情况
if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
// 取e2和e4作为两个轴（刚刚已经排过序了，所以pivot1 < pivot2）
int pivot1 = a[e2];
int pivot2 = a[e4];
// 把首尾两个元素填到两个轴移出来的坑里
a[e2] = a[left];
a[e4] = a[right];
// 这些元素不需要移动，直接往后找
while (a[++less] < pivot1);
while (a[--great] > pivot2);
// 下面的循环就是移动元素的过程
outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak < pivot1) { // 把a[k]移动到pivot1的左边
a[k] = a[less];
a[less] = ak;
++less;
} else if (ak > pivot2) { // 把a[k]移动到pivot2的右边
while (a[great] > pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] < pivot1) {
a[k] = a[less];
a[less] = a[great];
++less;
} else {
a[k] = a[great];
}
a[great] = ak;
--great;
}
}
// 把指针落到最终的位置
a[left] = a[less - 1]; a[less - 1] = pivot1;
a[right] = a[great + 1]; a[great + 1] = pivot2;
// 递归对左右两部分进行排序
sort(a, left, less - 2, leftmost);
sort(a, great + 2, right, false);
// 经过上面的处理，左右两边已经排好了，下面开始处理中间的部分。
// 如果中间的部分比从e1到e5的距离还要大，也就是大于4/7
if (less < e1 && e5 < great) {
// 跳过相等的元素
while (a[less] == pivot1) {
++less;
}
while (a[great] == pivot2) {
--great;
}
// 重复上面的过程
outer:
for (int k = less - 1; ++k <= great; ) {
int ak = a[k];
if (ak == pivot1) {
a[k] = a[less];
a[less] = ak;
++less;
} else if (ak == pivot2) {
while (a[great] == pivot2) {
if (great-- == k) {
break outer;
}
}
if (a[great] == pivot1) {
a[k] = a[less];
a[less] = pivot1;
++less;
} else {
a[k] = a[great];
}
a[great] = ak;
--great;
}
}
}
// 对中间进行递归
sort(a, less, great, false);
} else { // Partitioning with one pivot
// 否则选取中点e3指向的元素作为轴，进行传统单轴快速排序
...... //省略传统快排实现
}
}
从上面的代码可以看出，虽然这个方法的整体思想还是将数组分为三个部分，但是实现过程中考虑的更加细致，首先是轴的选取，这里选出5个间距相等的元素，然后进行从小到大排序。
在5个值都不相等的情况下，使用第2和第4个元素作为轴进行排序。一趟排完以后，如果中间的元素大于数组的4/7，再重复上面的过程，然后对中间部分进行递归。
如果5个值中有相等的情况，直接使用中间元素作为轴，进行传统快排逻辑。
下面的图展示了sort方法的主要流程
image.png
参考
https://learnforeverlearn.com/yaro_web/
https://rerun.me/2013/06/13/quicksorting-3-way-and-dual-pivot/
https://www.jianshu.com/p/2c6f79e8ce6e
https://www.jianshu.com/p/6d26d525bb96?nomobile
网友评论