在前边的文章里，我们分析了最简单的merge sort。这篇文章我们继续来看看针对primitive类型排序的quick sort(即快排)是如何实现的。
虽然现行的JDK中采用的是优化过的DualQuickSort，但是相对复杂了很多。如果直接去看，会比较吃力，所以我们可以先去分析一下普通的单轴快排，然后回过头再来看DualQuickSort，会更容易一些。
单轴快排 - quick sort 调用流程在JDK 1.7中，DualQuickSort被首次引入。所以我们这里采用JDK 1.6的源码，来看看之前版本的单轴快排是怎么实现的。
先简单分析一下它的调用流程
代码实现入口函数是+Arrays.sort(int[] a)，涉及到的函数有
- -Arrays.sort1(int x[], int off, int len)
- -Arrays.swap((int x[], int a, int b)
- -Arrays.med3(int x[], int a, int b, int c)
- -Arrays.vecswap(int x[], int a, int b, int n)
从上面的执行流程里边，我们可以比较直观地了解到快排的一个基本思想 - 分治思想。看起来与前边我们分析的merge sort很像，那他们两个主要的区别在哪里呢？
这里有一个简单的对比：
- merge sort - 由下到上 - 先处理子问题，然后再合并(重点 - 合并函数)
- quick sort - 由上到下 - 先对父问题分区，然后处理子问题(重点 - 分区函数)
同样的，我从上述流程中标记了几个关键的点，依次来进行分析。
C针对小数组的优化，直接使用insertion sort。具体的实现和前边分析的merge sort一样。这里不再赘述。
D针对选取pivot的优化，使用三数或者九数取中获取一个尽量接近与中位数的轴心点。从代码实现可以看到九数取中就是执行3次三数取中。实现的代码如下所示
private static int med3(int x[], int a, int b, int c) {
return (x[a] < x[b] ?
(x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
(x[b] > x[c] ? b : x[a] > x[c] ? c : a));
}
三目运算符虽然紧凑，但是阅读性稍微差了一点。如果改写成普通的if-else，会直观一些，如下
private static int med3(int x[], int a, int b, int c) {
if (x[a] < x[b]) {
if (x[b] < x[c]) return b; // x[a] < x[b] < x[c]
else if (x[a] < x[c]) return c; // x[a] < x[c] < x[b]
else return a; // x[c] < x[a] < x[b]
} else {
if (x[b] > x[c]) return b; // x[a] > x[b] > x[c]
else if (x[a] > x[c]) return c; // x[a] > x[c] > x[b]
else return a; // x[c] > x[a] > x[b]
}
}
即这里是手动将输入的三个下标对应的元素进行比较，穷举了所有的6种情况。
I这部分逻辑是非常重要的一环 - 分区，根据pivot的值，将原来的数组划分为以下4个区域
我们看一下代码
int v = x[m]; // The pivot
// Establish Invariant: v* (v)* v*
int a = off, b = a, c = off + len - 1, d = c;
while(true) {
while (b <= c && x[b] <= v) { // (1)
if (x[b] == v)// (2)
swap(x, a++, b);
b++;
}
while (c >= b && x[c] >= v) { // (3)
if (x[c] == v)// (4)
swap(x, c, d--);
c--;
}
if (b > c)
break;
swap(x, b++, c--);// (5)
}
关于注释中的invariant，可以简单地理解为一种约束条件(更多相关资料可以阅读参考资料里的链接)。如果我们把上边分区的示意图看成一种约束条件，那其实这部分代码就是建立分区的过程。
这部分的关键是理解a, b, c, d四个变量的含义。他们是两类游标
- a/d - 从左右两端分别向中间移动。其中a之前, d之后都是等于pivot的值的元素
- b/c - 从左右两端分别向中间移动。b之前的元素都是小于等于pivot的值的元素，c之后的元素都是大于等于pivot的值的元素
然后我们再来看上面的代码，其中
- (1)/(3)是分别移动游标b/c，以找到符合b/c条件的区间，如果不满足条件，就停下来。通过(5)来进行交换，然后继续循环，直到b/c相遇，结束循环。
- (2)/(4)则是在进行(1)/(3)的同时，将等于pivot的值的元素分别通过交换移动到数组的两端。
这个阶段就是将两端等于pivot的值移动到中间，完成整个分区动作。完成之后的效果如下
这一部分的代码比较少，如下
// Swap partition elements back to middle
int s, n = off + len;
s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
直接看对s的计算比较抽象。同样可以借助画图，来理解作者的意图。经过上个阶段的分区之后，各个游标大概是这个样子
这个图其实与I里边的插图是一致的，即
| 区域 | 含义 |
|---|---|
| a-off | =pivot |
| b-a | |
| d-c | >pivot |
| n-d-1 | =pivot |
以a-off与b-a为例，只需要找出两者中较小的值s，然后将两个区间交换s次就可以将=pivot部分的元素移动到 而d-c与n-d-1也是同样的道理。 具体的区间交换代码较为简单，如下 有了前边的分析，这部分代码看起来就简单多了。此处就是将左右两个子区间进行递归调用，最终完成整个排序。 即将 代码如下 总结一下，我们从JDK里早期版本的快排 - 单轴快排入手，详细分析了整个代码运行的过程。并且在绘制了辅助的图形，方便理解对应的代码。 接下来我们可以据此为基础，学习双轴快排是如何实现的。
private static void vecswap(int x[], int a, int b, int n) {
for (int i=0; i
小结
// Recursively sort non-partition-elements
if ((s = b-a) > 1)
sort1(x, off, s);
if ((s = d-c) > 1)
sort1(x, n-s, s);
