面试 13：基于排序算法的总结
浑浑噩噩，我们前面已经讲解了冒泡、插入、选择、归并、快排 5 种排序算法，其他的由于时间关系，我们就不一一例举了。
说到排序，不得不想到我们 JDK 中自带的 Arrays.sort() 和 Collections.sort() 方法。这两个方法基本算是 Java 中排序王牌了。在我们常用的方式中，Arrays.sort() 接受一个数组型参数，而 Collections.sort() 接受一个 List 集合参数。抛开它们可以接受多种类型的参数，我们且看看平时排序用的较多的 Arrays.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);
}
可以看到，在 JDK 里面把排序交给 DualPivotQuicksort 类进行全全处理，该类使用的是一种叫做 「双轴快速排序」的算法。从注释中我们可以看出，该排序方法默认是升序排序的，并且同样提供 O(nlogn) 的时间复杂度。
我们不妨进到 DualPivotQuicksort.sort() 查看代码。
/**
* Sorts the specified range of the array using the given
* workspace array slice if possible for merging
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
* @param work a workspace array (slice)
* @param workBase origin of usable space in work array
* @param workLen usable size of work array
*/
static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
/*
* Index run[i] is the start of i-th run
* (ascending or descending sequence).
*/
int[] run = new int[MAX_RUN_COUNT + 1];
int count = 0; run[0] = left;
// Check if the array is nearly sorted
for (int k = left; k < right; run[count] = k) {
if (a[k] < a[k + 1]) { // ascending
while (++k <= right && a[k - 1] <= a[k]);
} else if (a[k] > a[k + 1]) { // descending
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 { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
/*
* The array is not highly structured,
* use Quicksort instead of merge sort.
*/
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
}
// Check special cases
// Implementation note: variable "right" is increased by 1.
if (run[count] == right++) { // The last run contains one element
run[++count] = right;
} else if (count == 1) { // The array is already sorted
return;
}
// Determine alternation base for merge
byte odd = 0;
for (int n = 1; (n <<= 1) < count; odd ^= 1);
// Use or create temporary array b for merging
int[] b; // temp array; alternates with a
int ao, bo; // array offsets from 'left'
int blen = right - left; // space needed for b
if (work == null || workLen < blen || workBase + blen > work.length) {
work = new int[blen];
workBase = 0;
}
if (odd == 0) {
System.arraycopy(a, left, work, workBase, blen);
b = a;
bo = 0;
a = work;
ao = workBase - left;
} else {
b = work;
ao = 0;
bo = workBase - left;
}
// Merging
for (int last; count > 1; count = last) {
for (int k = (last = 0) + 2; k <= count; k += 2) {
int hi = run[k], mi = run[k - 1];
for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
b[i + bo] = a[p++ + ao];
} else {
b[i + bo] = a[q++ + ao];
}
}
run[++last] = hi;
}
if ((count & 1) != 0) {
for (int i = right, lo = run[count - 1]; --i >= lo;
b[i + bo] = a[i + ao]
);
run[++last] = right;
}
int[] t = a; a = b; b = t;
int o = ao; ao = bo; bo = o;
}
}
注意上面的代码，可以看到当我们传入的数组长度小于常量 QUICKSORT_THRESHOLD 时，我们直接采用双轴快速排序。从定义中我们可以看到这个常量值为 286。
/**
* If the length of an array to be sorted is less than this
* constant, Quicksort is used in preference to merge sort.
*/
private static final int QUICKSORT_THRESHOLD = 286;
对于「双轴快速排序」，受于篇幅关系，这里就不细讲了，感兴趣的可以 Google 一下。
在 JDK 的 sort() 方法中，实际上还做了一次判断。当传入的数组长度小于常量 INSERTION_SORT_THRESHOLD 值时，将直接采用插入排序。
/**
* Sorts the specified range of the array by Dual-Pivot Quicksort.
*
* @param a the array to be sorted
* @param left the index of the first element, inclusive, to be sorted
* @param right the index of the last element, inclusive, to be sorted
* @param leftmost indicates if this part is the leftmost in the range
*/
private static void sort(int[] a, int left, int right, boolean leftmost) {
int length = right - left + 1;
// Use insertion sort on tiny arrays
if (length < INSERTION_SORT_THRESHOLD) {
if (leftmost) {
/*
* Traditional (without sentinel) insertion sort,
* optimized for server VM, is used in case of
* the leftmost part.
*/
for (int i = left, j = i; i < right; j = ++i) {
int ai = a[i + 1];
while (ai < a[j]) {
a[j + 1] = a[j];
if (j-- == left) {
break;
}
}
a[j + 1] = ai;
}
} else {
/*
* Skip the longest ascending sequence.
*/
do {
if (left >= right) {
return;
}
} while (a[++left] >= a[left - 1]);
/*
* Every element from adjoining part plays the role
* of sentinel, therefore this allows us to avoid the
* left range check on each iteration. Moreover, we use
* the more optimized algorithm, so called pair insertion
* sort, which is faster (in the context of Quicksort)
* than traditional implementation of insertion sort.
*/
for (int k = left; ++left <= right; k = ++left) {
int a1 = a[k], a2 = a[left];
if (a1 < a2) {
a2 = a1; a1 = a[left];
}
while (a1 < a[--k]) {
a[k + 2] = a[k];
}
a[++k + 1] = a1;
while (a2 < a[--k]) {
a[k + 1] = a[k];
}
a[k + 1] = a2;
}
int last = a[right];
while (last < a[--right]) {
a[right + 1] = a[right];
}
a[right + 1] = last;
}
return;
}
// 源码太多，在此省略
}
由于插入排序并不需要遍历整个数组，整个排序算法的核心性能消耗是移位，所以在数组长度较小的时候，插入排序的效果是非常好的。
可见我们的 JDK 排序利用了多个排序算法的各种优良属性，避免出现我们前面讲到的各种糟糕情况。所以我们不得不在此对各种算法进行一定的总结。
总结
相信从前面的文章中大家也有了自己对排序算法的认知，目前并没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。因此我们必须从多个角度剖析一下它们的优劣。
为了省时间，我们这里就直接搬运《大话数据结构》中的总结了。
希尔排序和堆排序，在南尘的文章中没有讲，感兴趣的直接 Google。
image.png
从算法的简单性来看，我们将 7 种算法分为两类:
- 简单算法:冒油、简单选择、直接插入。
- 改进算法:希尔、堆、归并、快速。
从平均情况来看，显然最后 3 种改进算法要胜过希尔排序，并远远胜过前 3 种简单算法 。
从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑 4 种复杂的改进算法。
从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。
从这三组时间复杂度的数据对比中，我们可以得出这样一个认识：
堆排序和归并排序就像两个参加奥数考试的优等生，心理素质强，发挥稳定。而快速排序像是很情绪化的天才，心情好时表现极佳，碰到较糟糕环境会变得差强人意。但是他们如果都来比赛计算个位数的加减法，它们反而算不过成绩极普通的冒泡和直接插入。
从空间复杂度来说，归并排序强调要马跑得快，就得给马吃个饱。快速排序也有相应的空间要求，反而堆排序等却都是少量索取，大量付出，对空间要求是 O(1)，如果执行算法的软件所处的环境非常在乎内存使用量的多少时，选择归并排序和快速排序就不是一个较好的决策了。
从稳定性来看，归并排序独占鳌头，我们前面也说过，对于非常在乎排序稳定性的应用中，归并排序是个好算法。
从待排序记录的个数上来说，待排序的个数 n 越小，采用简单排序方法越合适。 反之， n 越大，采用改进排序方法越合适。这也就是为什么在 JDK 中对快速排序优化时， 增加了一个阀值 47，低于阀值时换作直接插入排序的原因。
好了，本篇文章有点状态迷糊，大家且将就看看，我们下周再见。
