[本篇博文會對常見的排序算法進行分析與總結，并會在最後提供幾道相關的一線網際網路企業面試/筆試題來鞏固所學及幫助我們查漏補缺。項目位址：https://github.com/absfree/Algo。由于個人水準有限，叙述中難免存在不清晰準确的地方，希望大家可以指正，謝謝大家：）]
一、概述
我們在日常開發中經常需要對一組資料對象進行排序，這裡的資料對象不僅包括數字，還可能是字元串等抽象資料類型（Abstract Data Type）。由于排序是很多其他操作（比如二分查找）能夠高效進行的基礎，是以我們有必要掌握好常見的排序算法，本篇文章會分析幾種最常用的排序算法，并進一步探索排序的本質，進而能夠更加全面透徹的了解各種排序算法。本篇博文會用Java來描述各種排序算法的實作，由于本篇文章的側重點在與分析各項算法的原理及其一般實作，是以我們假定待比較的資料對象均為int類型（然而在實際應用中我們應該假定它們為Comparable類型）。若未加特殊說明，我們以下的排序算法都會按照升序排列。在算法的具體實作中，我們用到了StdRandom、StdOut和StdIn這三個靜态代碼庫，它們可以在這裡https://github.com/absfree/Algo/tree/master/src/util找到，每個方法的作用都可以通過它們的名稱看出來，源碼中也有相應的注釋。
二、基本排序算法
1. 冒泡排序
假如我們現在按身高升序排隊，一種排隊的方法是：從第一名開始，讓兩人互相比身高，若前者高則交換位置，更高的那個在與剩下的人比，這樣一趟下來之後最高的人就站到了隊尾。接着重複以上過程，直到最矮的人站在了隊列首部。我們把隊頭看作水底，隊尾看作水面，那麼第一趟比較下來，最高的人就像泡泡一樣從水底”冒“到水面，第二趟比較則是第二高的人……排隊的過程即為對資料對象進行排序的過程（這裡我們排序的”名額“是身高），上述過程即描述了冒泡排序的思想。從以上過程我們可以看到，若對n個人進行排隊，我們需要n-1趟比較，而且第k趟比較需要進行n-k次比較。通過這些資訊，我們能夠很容易的算出冒泡排序的複雜的。首先，排序算法通常都以資料對象的兩兩比較作為”關鍵操作“，這裡我們可以得出，冒泡排序需要進行的比較次數為: (n-1) + (n-2) + ... + 1 = n*(n-1) / 2，是以冒泡排序的時間複雜度為O(n^2)。
了解了冒泡排序的原理，就不難實作它了，具體實作代碼如下：
public class Bubble {
public static void sort(int[] a) {
int N = a.length;
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < N - i - 1; j++) {
if (a[j] > a[j+1]) {
exchange(a, j, j+1);
}
}
}
}
public static void exchange(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
int N = 20;
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = StdRandom.uniform(0, 1000);
}
sort(a);
for (Integer i : a) {
StdOut.print(i + " ");
}
}
} 複制
關于冒泡排序有一點需要注意的是，在最好情況下（即輸入數組已經完全有序），冒泡排序的時間複雜度能夠提升到O(N)。我們隻需增加一個boolean型變量isOrdered，在第一輪排序中一旦a[j] > a[j+1]，就把isOrdered設為false，否則isOrdered設為true，然後我們在每趟排序前檢查isOrdered，一旦發現它為false，即認為排序已完成。
2. 選擇排序
回到上面我們提到的排隊問題，除了上面提到的方法，還有這樣一種排隊的方法，讓目前隊頭的人依次與其後的每個人進行比較，比較後較矮的那個人繼續與後面的人進行比較，這樣第一趟比較下來，就能夠找到最矮的人， 然後把這個最矮的人和目前隊頭的人交換一下位置。然後第二趟比較，讓第二名依次與後面比較，可以找到第二矮的人，然後讓第二矮的人和目前隊列第二名交換位置，依此類推，一共進行n-1趟比較後，就能完成整個排隊過程。根據上述描述，我們可以知道，第k趟比較需要進行的數組元素的兩兩比較的次數為n-k次，是以共需要的比較次數為n*(n-1) / 2，是以選擇排序算法的時間複雜度與冒泡排序一樣，也為O(n^2)。選擇排序的Java描述如下：
public class Selection {
public static void sort(int[] a) {
int N = a.length;
for (int i = 0; i < N - 1; i++) {
int min = i;
for (int j = i + 1; j < N; j++) {
if (a[j] < a[min]) {
min = j;
}
}
exchange(a, i, min);
}
}
public static void exchange(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} 複制
3. 插入排序
回想下我們平時打撲克抓牌的過程，通常我們用右手抓牌，每抓一張牌，就放到左手上，抓下一張牌後，會把這張牌依次與左手上的牌比較，并把它插入到一個合适的位置（通常按照牌面大小）。上述的過程即為插入排序的過程，假設待排序數組為a，我們從a[1]開始，讓a[1]與a[0]比較，若a[1]較小，則讓a[1]和a[0]交換位置，此時a[0]和a[1]就相當于已經放入左手中的牌。然後我們再讓a[2]與a[1]、a[0]比較，并為它找到一個合适的位置，以此類推，直到為數組的最後一個元素也找到了合适的位置。
了解了插入排序的思想後，我們便能夠得到它的時間複雜度。對于n個元素，一共需要進行n-1輪比較，而第k輪比較需要進行k次數組元素的兩兩比較，是以共需要進行的比較次數為：1 + 2 + ... + (n-1)，是以插入排序的時間複雜度同冒泡排序一樣，也為O(n^2)。插入排序的Java描述如下：
public class Insertion {
public static void sort(int[] a) {
int N = a.length;
int i, j;
for (i = 1; i < N; i++) {
for (j = i - 1; j >= 0 && a[i] < a[j]; j--) {
}
//這裡跳出内層循環，a[i]應被插入到a[j]後
int tmp = a[i];
for (int k = i; k > j + 1; k--) {
a[k] = a[k-1];
}
a[j+1] = tmp;
}
}
} 複制
我們來簡單地解釋下以上代碼。以抓牌過程來舉例，i為剛抓的牌的索引，i-1即為我們剛排好的牌中的最後一張的索引，j為左手中目前正與我們剛抓的牌進行比較的牌的索引。在内層循環中，我們從左手已排好牌中的最後一張開始，若發現剛抓的牌比目前牌的牌面大，就再與前一張比較（j--），直到剛抓的牌大于等于目前牌的牌面，就會跳出内層循環，這時我們把a[i]插入到a[j]後，就把剛抓的牌插入到已排好牌中的合适的位置了。重複以上過程就能完成待排序數組的排序。
關于插入排序我們需要注意的是，在平均情況下以及最壞情況下，它的時間複雜度均為O(n^2)，而在最好情況下（輸入數組完全有序），插入排序的時間複雜度能夠提升至O(N)。實際上，排序的本質就是消除逆序對，所謂逆序對，就是不符合我們所要求的排序順序的兩個數。比如說[1,3,4,2]為待排序數組，那麼它的逆序數為2——(3,2)和(4,2)都是降序的，不符合我們升序的要求。插入排序對于部分有序的數組的排序尤為有效，所謂部分有序，指的是待排序數組的逆序數小于數組尺寸的某個倍數。若我們待排序數組完全有序時，每一輪排序都隻需比較一次，就能找到待排序元素在已排序數組中的合适的位置，而部分有序時，比較的次數也能控制在數組尺寸的常數倍之内。是以，插入排序對于部分有序的數組十分高效，也很适合小規模的數組。
4. 希爾排序
希爾排序是對插入排序的一種改進，它的核心思想是将待排序數組中任意間隔為h的元素都變為有序的，這樣的數組叫做h有序數組。比如數組[5, 3, 2, 8, 6, 4, 7, 9, 5], 我們可以看到a[0]、a[3]、a[6]是有序的，a[1]、a[4]、a[7]是有序的，a[2]、a[5]、a[8]是有序的，是以這個數組是一個h有序數組（h=3）。根據h有序數組的定：義，我們可以知道，當h=1時，相應的h有序數組就是一個已經排序完畢的數組了。希爾排序的大緻過程如下：把待排序數組分割為若幹子序列（一個子序列中的元素在原數組中間隔為h，即中間隔了h-1個元素），然後對每個子序列分别進行插入排序。然後再逐漸減小h，重複以上過程，直至h變為足夠小時，再對整體進行一次插入排序。由于h足夠小時，待排序數組的逆序數已經很小，是以再進行一次希爾排序是很快的。希爾排序通常要比插入排序更加高效。
實作希爾排序時，我們需要選取一個h的取值序列，這裡我們直接采用算法（第4版） (豆瓣)一書中提供的h取值序列（1,4,13,40,121, ...)。即h = 3 * k + 1，其中k為[0, N/3)區間内的整數。希爾排序的Java描述如下：
public class Shell {
public static void sort(int[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1; //h的取值序列為1, 4, 13, 40, ...
}
while (h >= 1) {
int n, i ,j, k;
//分割後，産生n個子序列
for (n = 0; n < h; n++) {
//分别對每個子序列進行插入排序
for (i = n + h; i < N; i += h) {
for (j = i - h; j >= 0 && a[i] < a[j]; j -= h) {
}
int tmp = a[i];
for (k = i; k > j + h; k -= h) {
a[k] = a[k-h];
}
a[j+h] = tmp;
}
}
h = h / 3;
}
}
} 複制
實際上，h的取值序列的選取會影響到希爾排序的性能，不過以上我們選取的h值序列在通常情況下性能與複雜的取值序列相接近，但是在最壞情況下的性能要差一些。分析希爾排序的複雜度不是一件容易的事，這裡我們引用《算法》一書中關于希爾排序複雜度的結論：
使用遞增序列1, 4, 13, 40, 121, 364, ...的希爾排序所需的比較次數不會超過數組尺寸的若幹倍乘以遞增序列的長度。
也就是說，在通常情況下，希爾排序的複雜度要比O(n^2)好得多。實際上，最壞情況下希爾排序所需要的比較次數與O(n^1.5)成正比，在實際使用中，希爾排序要比插入排序和選擇排序、冒泡排序快得多。而且盡管待排序數組很大，希爾排序也不會比快速排序等進階算法慢很多。是以當需要解決排序問題而用沒有現成系統排序函數可用時，可以優先考慮希爾排序，當希爾排序确實滿足不了對性能的要求時，在考慮使用快速排序等算法。
到這裡，我們要介紹的基本排序算法就介紹完了，再介紹快速排序、歸并排序、堆排序等進階排序算法前，我們先來簡單地介紹下如何比較各種排序算法的實際性能，這也能夠幫助我們直覺的看到希爾排序相比與插入排序等的性能優勢。
5. 比較不同排序算法的性能
盡管插入排序和選擇排序的複雜度都為O(n^2)，但是它們所包含的常數系數是不同的，因而這兩種算法的實際執行時間之比應該是一個常數，下面我們來設計實驗來測試下以上我們介紹的幾種基本排序算法的實際執行性能。相關代碼如下：
public class SortCompare {
public static double time(String alg, int[] a) {
long startTime = System.currentTimeMillis();
if (alg.equals("Insertion")) {
Insertion.sort(a);
} else if (alg.equals("Selection")) {
Selection.sort(a);
} else if (alg.equals("Bubble")) {
Bubble.sort(a);
} else if (alg.equals("Shell")) {
Shell.sort(a);
}
long endTime = System.currentTimeMillis();
return (double) (endTime - startTime) / 1000.0;
}
public static double timeRandomInput(String alg, int N, int T) {
//使用alg指定的排序算法将長度為N的數組排序，共排序T次，并計算總時間
double total = 0.0;
int[] a = new int[N];
for (int t = 0; t < T; t++) {
for (int i = 0; i < N; i++) {
a[i] = StdRandom.uniform(10 * N);
}
total += time(alg, a);
}
return total;
}
public static void main(String[] args) {
String alg1 = args[0];
String alg2 = args[1];
int N = Integer.parseInt(args[2]);
int T = Integer.parseInt(args[3]);
double t1 = timeRandomInput(alg1, N, T);
double t2 = timeRandomInput(alg2, N, T);
StdOut.printf("For %d random ints\n %s is", N, alg1);
StdOut.printf(" %.1f times faster than %s", t2/t1, alg2);
}
} 複制
我們來對1000個數進行排序，來比較下以上介紹的算法的性能。我這裡得到的輸出結果如下：
For 1000 random ints
Shell is 4.9 times faster than Insertion
For 1000 random ints
Shell is 7.6 times faster than Selection
For 1000 random ints
Shell is 11.7 times faster than Bubble 複制
我們可以直覺的看到，希爾排序要比其他三種排序都快，而插入排序要比選擇排序、冒泡排序快，冒泡排序在實際執行性能最差。
基本排序算法對于中小規模的資料集的排序在一般情況下足夠用了，但是對于大規模資料集的排序，我們還是很有必要使用一些較進階的排序算法，下面我們來逐一介紹它們。
三、歸并排序
歸并排序使用了一種叫做”分治“的思想來解決排序問題。分治也就是"分而治之“，也就是把一個大問題分解為衆多子問題，而後分别得到每個子問題的解，最終以某種方式合并這些子問題的解就可以得到原問題的解。歸并排序的主要思想是：将待排序數組遞歸的分解成兩半，分别對它們進行排序，然後将結果“歸并”（遞歸的合并）起來。我們知道，遞歸算法都有一個base case，遞歸分解數組的base case就是分解完的兩個數組長度為為1，這時候它們本身就有序，此時就可以進行歸并了。
歸并排序的時間複雜度為O(nlogn), 它的主要缺點是所需的額外空間與待排序數組的尺寸成正比。
1. 歸并方法實作
首先，我們先來實作歸并方法，這個方法接收一個int[]數組a以及low、mid、high參數，用于将a[low..mid]（代表a[low]到a[mid]間的元素，包括a[low]和a[mid]）和a[mid+1..high]歸并為一個數組，這個方法假設a[low..mid]與a[mid+1..high]都是有序的。
下面我們用一個具體例子來描述歸并算法的執行過程，假如我們的輸入數組為[2, 4, 6, 8, 1, 3, 5, 7]，low為0，mid為3，high為7。我們稱a[low..mid]為左數組，a[mid+1..high]為右數組，歸并方法的執行過程如下：
- 取左右數組的第一個元素進行比較，較小的那個放入新數組的第一個位置中，如下圖所示：
- 取右數組的下一個元素與2進行比較，較小的放入新數組的下一個位置，如下圖所示：
- 下一步我想不用我說大家也知道了，實際上我們可以把這個過程想象成左右兩邊輪番出人比武，比輸的那個就被淘汰到“場外”，由于兩邊都是讓弱的先出場，是以随後第一個出局的肯定就是最弱的。最後新數組中就按“武功高低”的升序對輸入元素進行了排序。以上我們描述的就是歸并方法的執行過程。
了解了歸并方法的原理，我們就不難用Java來描述它了，相關代碼如下：
private static void merge(int[] a, int low, int mid, int high) {
int i = low; //左數組下一個要進行比較的元素的索引
int j = mid + 1; //右數組下一個要進行比較的元素的索引
int N = high + 1; //本次歸并的元素數目
int[] tmpArray = new int[N]; //用于暫時存放比較後的元素
for (int k = low; k <= high; k++) {
if (i > mid) { //左數組元素已全比較完
tmpArray[k] = a[j++];
} else if (j > high) { //右數組元素已全比較完
tmpArray[k] = a[i++];
} else if (a[j] < a[i]) { //右數組元素小于左數組
tmpArray[k] = a[j++];
} else { //右數組元素大于等于左數組
tmpArray[k] = a[i++];
}
}
for (int k = low; k < N; k++) {
a[k] = tmpArray[k];
}
} 複制
在以上代碼中，我們使用了一個輔助數組tmpArray來暫時存放比較後的數組元素，待歸并完成後，再複制回原數組。
2. 自頂向下的歸并排序
上面我們介紹了歸并過程的實作，歸并方法要求輸入數組的左半部分和右半部分分别有序。那麼下面我們來介紹如何利用上面我們實作的merge方法來實作對一個資料集的歸并排序。
在最開始我們介紹過歸并排序的主要思想是将待排序數組遞歸的分解成兩半，分别對它們進行排序，然後将結果歸并起來。具體過程如下：将數組遞歸的分為兩部分，直至兩部分長度都為1，則認為到達了base case，這時開始執行歸并過程。
這裡我們還是以上面的輸入數組舉例，遞歸分解數組的示意圖如下：
我們可以看到，當數組分解為隻有單個元素後，那麼它就是有序的了，是以這時就滿足了上面我們實作的歸并方法的輸入參數的條件，我們通過調用歸并方法就能夠以單元素數組為起點，逐漸構造出已排序的完整數組。相關的實作代碼如下：
public class Merge {
private static void merge(int[] a, int low, int mid, int high) {
...
}
public static void sort(int[] a) {
int N = a.length;
sort(a, 0, N - 1);
}
private static void sort(int[] a, int low, int high) {
//base case
if (high <= low) {
return;
}
int mid = (low + high) / 2;
sort(a, low, mid);
sort(a, mid+1, high);
merge(a, low, mid, high);
}
public static void main(String[] args) {
int N = 20;
int a[] = new int[N];
for (int i = 0; i < N; i++) {
a[i] = StdRandom.uniform(1000);
}
sort(a);
for (Integer i : a) {
StdOut.print(i + " ");
}
}
} 複制
如果感覺以上代碼比較抽象，大家可以畫出“遞歸調用圖”來幫助我們了解遞歸調用的過程，還是以上面的輸入數組為例，我們畫一下對它進行歸并排序的遞歸調用圖：
通過這個圖，我們可以直覺地看到sort方法的遞歸調用過程。對于以上sort方法，以下幾個方法能夠提升它的性能：
- 對小規模子數組使用插入排序。
- 執行merge方法前，先判斷下數組是否有序。這個方法能夠大幅提升算法在最好情況（輸入數組完全有序）的性能。
四、快速排序
快速排序是目前應用最廣泛的排序算法之一，它是一般場景中大規模資料排序的首選，它的實際性能要好于歸并排序。通常情況下，快速排序的時間複雜度為O(nlogn)，但在最壞情況下它的時間複雜度會退化至O(n^2)，不過我們可以通過對輸入數組進行“随機化”（打亂元素的排列順序）來避免最壞情況的發生。除了實際執行性能好，快速排序的另一個優勢是它能夠實作“原地排序”，也就是說它幾乎不需要額外的空間來輔助排序。下面我們來具體介紹下這個優秀排序算法的原理及實作。
1. 基本原理
快速排序的主要思想如下：假設待排序數組為a[0..N-1]，遞歸的對該數組執行以下過程：選取一個切分元素，而後通過數組元素的交換将這個切分元素移動到位置j，使得所有a[0..j-1]的元素都小于等于a[j]，所有a[j+1..N-1]的元素都大于等于a[j]。
在快速排序中，切分元素的選取很關鍵，通常我們可以選取輸入數組的第一個元素作為切分元素，然後把它交換到數組中的合适位置使得它左邊的元素都小于等于它，右邊的元素都大于等于它，而後對其左右兩邊的子數組遞歸執行切分過程，即可完成對整個數組的排序。下面我們來看一下切分方法的Java描述，并以此來講解切分過程的具體實作：
1 private static int partition(int[] a, int low, int high) {
2 int i = low + 1;
3 int j = high + 1;
4
5 //p為切分元素
6 int p = a[low];
7 while (true) {
8 //從數組中的第二個元素開始尋找第一個大于等于切分元素的數組元素，若找到則i為其索引
9 while (a[++i] < p) {
10 if (i == high) {
11 break;
12 }
13 }
14 //此時i為從數組首部開始第一個大于等于切分元素的數組元素的索引，若沒有找到則為high
15
16 //從數組末元素開始尋找第一個小于等于切分元素的數組元素，若找到則j為其索引
17 while (a[--j] > p) {
18 if (j == low) {
19 break;
20 }
21 }
22 //此時j為從數組末開始第一個小于等于切分元素的數組元素的索引，若沒有找到則為low
23
24 if (i >= j) {
25 break;
26 }
27 exchange(a, i, j);
28 }
29 exchange(a, low, j);
30 return j;
31 } 複制
結合以上代碼，我們來講解一下确定切分過程的具體實作。首先在第6行中，我們選取了數組的首元素作為切分元素并将它儲存在變量p中，然後在第7行進入一個無限循環中。
第9行到第13行是一個内層循環，在這個循環中，我們從數組的第二個元素開始，讓切分元素p與每個數組元素進行比較，當相應位置的元素大于等于p或是已經到達數組末尾時，這個循環就會終止。此時i的值為第一個大于等于p的元素的索引或是high的值，若為high的值則表示數組中不存在大于等于p的元素。
然後我們來到了第17行到第21行的内層循環中，這個循環會從數組末元素開始，讓p與數組元素逐一進行比較，當相應位置的元素小于等于p或是已比較到數組首時則終止循環。此時j的值為第一個小于等于p的元素的索引或是low的值，若為low的值則表示數組中不存在小于等于p的元素。
接下來，執行第24行的if語句判斷i和j的大小，若i >= j, 會跳出無限循環。i >= j對應着以下四種情況：
- 第一種情況：數組中存在大于等于p的元素，也存在小于等于p的元素，此時若i>=j說明第一個大于等于p的元素在第一個小于等于p的元素的右邊（或是它倆本身是一個元素），我們來看下這種情況的圖示：
實際上， 左圖中a[j]與a[i]間是不存在元素的，因為沒有元素能同時滿足大于p和小于p這兩個條件。是以在這種情況下，實際上a[i]和a[j]是相鄰的。是以這時候我們隻需跳出無限循環，并交換a[low]和a[j]就能夠完成切分；
- 第二種情況：數組中存在大于等于p的元素，而不存在小于等于p的元素，即此時i為第一個大于等于p的元素的索引，j為low，是以這時必然滿足i > j。那麼此時我們便已經完成了切分（a[j]右邊的元素均大于p，左邊沒有元素），是以直接跳出無限循環，為統一上一種情況，我們也交換下low和j處的元素（雖然實際上就是自己和自交換）；
- 第三種情況：數組中不存在大于等于p的元素，存在小于等于p的元素，此時i為high，j為第一個小于等于p的元素的索引，是以此時i = j = high。是以此時也完成了切分（a[j]左邊的元素均小于p，右邊沒有元素），是以這時候跳出無限循環并将low處和j處的元素呼喚，就完成了切分。
- 第四種情況：數組中既不存在大于等于p的元素，也不存在小于等于p的元素，這意味着數組中的所有元素都等于p。那麼此時經過兩個内層循環後，i的值為high，j的值為low。是以已經完成了切分，此時跳出無限循環後，為了與以上情況相統一，交換low與j處的元素（實際上是自己和自己交換）。
下面我們再來看一下當i < j時我們應該怎麼做。首先我們需要明确的是i < j意味着第一個大于等于p的元素(a[i])在第一個小于等于p的元素(a[j])的左邊。如下圖所示：
那麼現在問題來了，a[i]和a[j]之間的元素和p的關系是怎樣的呢？答案是無法确定，是以當i<j時我們還不能貿然退出無限循環，得先把a[i]與a[j]之間的元素與p的大小關系确定了才行。不過現在的問題是出現了兩隻“攔路虎”——突然出現了a[i]這個大于等于p的元素攔着我們讓我們無法繼續向數組尾部尋找小于p的元素，而a[j]這個小于等于p的元素的出現使得我們無法向數組頭部探索是否還有大于p的元素。那麼解決方法來了，我們隻要想辦法移除這兩個擋道的不就行啦。慢着...交換下a[i]和a[j]不就好了，這樣我們就可以繼續探索了呀，再遇到攔路虎的時候再交換它倆就可以了呀...以上代碼第27行就完成了這個交換的工作。
關于切分方法還有一點需要我們注意的是：在從左向右“掃描”時，必須在遇到大于等于切分元素p的元素時停下來，在從右向左掃描時，必須在遇到小于等于切分元素p的元素時停下來。若不是這樣做的話，當數組有大量重複元素時，快速排序的時間複雜度就會退化至O(n^2)。
現在，我們已經結合源代碼，比較詳細地闡述了切分過程的實作。下面，讓我們借助這個切分過程，來實作用快速排序算法對一個數組進行排序。
2. 實作
實際上，搞懂了上面的切分過程，來具體實作快速排序是很容易的，參考代碼如下：
1 public static void sort(int[] a) {
2 StdRandom.shuffle(a); //打亂輸入數組的元素間的相對順序，避免出現最壞情況
3 sort(a, 0, a.length - 1);
4 }
5
6 private static void sort(int[] a, int low, int high) {
7 if (high <= low) {
8 return;
9 }
10 int j = partition(a, low, high);
11 sort(a, low, j-1);
12 sort(a, j+1, high);
13 } 複制
跟我們前面所描述的快速排序的基本思想一樣，遞歸地對待排數組進行切分就能夠完成排序。這裡我們簡單介紹下快速排序的性能特點。快速排序算法的實際執行性能依賴與切分是否均衡，當正好把數組從中間”切開”時，快速排序的實際性能最好。切分越不均衡快速排序的實際性能就越差，最壞情況下（第一次選取的切分元素是數組裡最小的，第二次的切分元素是第二小的...），算法的時間複雜度會退化到O(n^2)。是以為了避免最壞情況的發生，我們在使用快速排序對數組排序時，會先打亂一下數組元素的順序。一個好消息是在平均情況下，我們将數組打亂後再取第一個元素作為切分元素，切分通常是比較均衡的。
3. 對快速排序算法的改進
盡管快速排序已經具有非常優秀的實際性能，但是仍然有許多行之有效的方法能夠明顯提升快速排序的速度，下面我們将簡單地介紹以下這些方法。
（1）對于小數組使用插入排序
對于尺寸比較小的數組，插入排序要比快速排序快，是以當遞歸調用切分方法到切分所得數組已經很小時，我們不妨用插入排序來排序小數組。隻需要把以上快速排序實作代碼的7—9行改為如下：
if (high <= low + SIZE) { //SIZE為使用插入排序的臨界數組尺寸，可以選取[5，15]上的整數
Insertion.sort(a, low, high);
return;
} 複制
（2）三取樣切分
這項改進方案的手段是改進切分過程，具體方法如下：在每次切分時，從待切分數組中随即抽取3個元素，而後計算出它們3個元素的中位數來作為切分元素。也就是說，相比于上面我們實作的快速排序，三取樣切分就是在切分元素的選取上有所不同。以下是三取樣切分的實作：
public class Quick3d {
public static void sort(int[] a) {
sort(a, 0, a.length);
}
private static void sort(int[] a, int low, int high) {
if (high <= low) {
return;
}
int lt = low;
int i = low + 1;
int gt = high;
int p = a[low];
while (i <= gt) {
if (a[i] < p) {
exchange(a, i++, lt++);
} else if (a[i] > p) {
exchange(a, i++, gt--);
} else {
i++;
}
}
}
public static void exchange(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} 複制
五、堆排序
1. 優先隊列
介紹堆排序之前，我們需要先介紹一種常用的資料結構——優先隊列，因為堆排序就是基于優先隊列實作的。優先隊列可以分為最大優先隊列和最小優先隊列，最大優先隊列主要支援兩種操作：插入元素和删除最大元素，最小優先隊列則支援插入元素和删除最小元素。在下面的介紹中，若未加特殊說明，我們所說的優先隊列指的是最大優先隊列。優先隊列适用于如下這種場景：不需要對資料集完全有序，我們隻需要擷取資料集最大的一個或幾個元素。優先隊列可以基于數組實作，也可以基于二叉堆來實作，通常二叉堆都基于二叉堆來實作，是以這裡我們主要介紹這種實作。
（1）幾個概念
在介紹基于二叉堆實作的優先隊列前，我們先來介紹幾個概念，這幾個概念的定義均來自于Sedgewick的《算法》一書。第一個我們要介紹的概念堆有序，它的定義如下：
當一棵二叉樹的每個結點都大于等于它的兩個子結點時，它被稱為堆有序。
第二個概念是二叉堆，它的定義如下：
二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數組中按照層級存儲（不用數組的第一個位置）。
我們來畫張圖說明一下堆有序的完全二叉樹是怎樣按照層級存儲在數組中的：
從上圖中我們可以看到二叉樹中的元素是怎樣和數組中對應的。使用這種順序将二叉樹元素存儲在數組中所帶來的一個最直接的好處就是很容易定位到一個數組元素a[k]在樹中的父結點和兩個子結點在數組的的位置：a[k]的父結點為a[k/2]，左子結點為a[2*k], 右子結點為a[2*k+1]。這種容易定位父子結點的性質加上下面的一個二叉堆的特性使得我們能夠基于二叉堆高效的實作優先隊列：一棵大小為N的完全二叉樹的高度為floor(lgN)。（其中floor表示向下取整，lgN表示以2為底的N的對數）
（2）基于二叉堆實作的優先隊列
我們通過前面對二叉堆的定義可以知道，二叉堆可看做一棵堆有序的完全二叉樹，是以二叉堆的各個元素間是有着一定的相對順序的。具體說來，就是每個結點都大于等于它的兩個子結點。所謂堆的有序化是指：當我們向二叉堆中添加一個元素或從二叉堆中删除一個元素後，導緻二叉堆的有序性貝爾打破，這時我們要通過某種過程來恢複二叉堆的有序性，這個過程就是堆的有序化。（若未做特殊說明，以下提到的“堆”均指“二叉堆”）。
堆的有序化可分為兩種，一種是由下向上的有序化，通常叫做上浮（swim）；還有一種是由上向下的有序化，通常叫做下沉（sink）。它們的名字便很清楚了表明了它們各自的作用，上浮就是讓一個結點向上移動到滿足堆有序的位置，下沉就是讓一個結點向下移動到滿足堆有序的位置，下面我們來分别介紹它們。
a. 上浮過程的實作
什麼情況下我們需要上浮呢？通常是某個結點的值變大或是我們向堆中添加一個新結點時（它會被添加到數組尾部，也就是成為堆的葉子結點），我們需要把這個結點上浮到一個合适的位置以保證堆有序。根據堆有序的定義，當我們要進行上浮的結點大于它的父結點時，我們就需要把它不斷的上浮，直到它小于等于它的父結點。參考代碼如下：
private void swim(int k) {
while (k > 1 && a[k/2] < a[k]) {
exchange(k, k/2 );
k = k / 2;
}
} 複制
b. 下沉過程的實作
當某個結點的值比它的某個子結點更小時，我們需要把該結點下沉來保證堆的有序性。下沉操作的過程中，我們應當先比較被下沉結點的兩個子結點的大小，而後讓被下沉結點與較大的那個比較，若是小于它，則兩者交換，而後重複這個過程直到父結點大于等于兩個子結點或是到達末尾。參考代碼如下：
private void sink(int k) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && a[2*k] < a[2*k+1]) {
j++;
}
if (k >= j) {
break;
}
exchange(k, j);
k = j;
}
} 複制
了解了堆的有序化的過程，優先隊列的insert方法以及delMax方法的實作就很容易了，下面我們來基于以上的swim和sink方法來介紹insert與delMax方法的具體實作。為簡單起見，我們假設結點均為int型。
c. insert方法的實作
有了上面的鋪墊，實作insert方法就很簡單了，我們隻需要把新結點添加到數組a的尾部，然後把它上浮到合适的位置即可，具體實作代碼如下：
public void insert(int node) {
a[++N] = node;
swim(N);
} 複制
d. delMax方法的實作
由于我們始終保持二叉堆處于有序狀态，是以根結點就是最大的結點，我們可以删除根結點，然後把數組尾部結點放入根結點的位置，再把它進行下沉即可，參考代碼如下：
public int delMax(int k) {
exchange(1, N);
int max = a[N--];
a[N+1] = -1;
sink(1);
return max;
} 複制
現在我們已經成功實作了一種insert方法與delMax方法的複雜度均為O(logn)的優先隊列。實際上我們上面實作的每次可以删除一個最大結點的優先隊列叫做最大有限隊列，與它相對的每次可以删除一個最小結點的優先隊列就是最小優先隊列。接下來讓我們基于（最大）優先隊列來實作堆排序。
2. 堆排序
我們知道，每次調用優先隊列的delMax方法都會删除一個最大的結點，其時間複雜度為O(logN)。那麼對于一個大小為N的資料集，我們隻需要将它包含的元素都添加到優先隊列中，然後調用N次delMax不就可以實作排序了嗎？實際上這種差別與之前我們所介紹的排序方法的排序實作就是堆排序，堆排序的時間複雜度為O(nlogn)。
堆排序通常分為兩個階段，第一個階段是堆的構造階段，用于把我們輸入的無序數組構造成二叉堆；第二個階段是下沉排序階段，這個階段我們删除一個最大結點并下沉以保證堆有序。下面我們來具體介紹這兩個階段的實作。
（1）堆的構造階段
這個階段我們的任務是把一個無序數組構造成一個二叉堆，要實作這一任務，我們可以從數組的尾部開始對每個元素調用sink方法，若一個結點的兩個子結點都已經是堆，那麼我們對該結點調用sink就可以将它們整合成一個堆。對于沒有子結點的堆，我們無需對其調用sink方法。
（2）下沉排序階段
下沉排序的邏輯很簡單，就是讓最大結點（即根結點）與數組末尾對應的結點交換，這樣就把最大結點移動到了數組末尾，然後把剛交換到根結點的結點進行sink，此時根結點即為第二大的結點，然後再将根結點與數組末尾對應的結點交換….這樣重複N-1次就能實作數組的原地排序。
結合以上兩個階段，就可以得到堆排序的完整實作：
public class Heap {
private static void sink(int[] a, int k, int N) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && a[j] < a[j+1]) {
j++;
}
if (a[k] >= a[j]) {
break;
}
exchange(a, k, j);
k = j;
}
}
public static void sort(int[] a) {
int N = a.length - 1;
for (int k = N/2; k >= 1; k--) {
sink(a, k, N);
}
while (N > 1) {
exchange(a, 1, N--);
sink(a, 1, N);
}
}
public static void exchange(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
} 複制
（3）堆排序算法的評價
《算法》一書中對堆排序評價如下：
堆排序是我們所知的唯一能夠同時最優地利用空間和時間的方法——在最壞情況下他也能保證~2NlgN次比較和恒定的額外空間。
其中~2NlgN表示比較次數的增長量級為2NlgN。也就是說若設比較次數為f(N)，當N足夠大時，f(N) / 2NlgN趨向于1。由于這個特性，堆排序算法适合于空間資源十分緊張的嵌入式系統。
堆排序的一個主要缺點在于緩存不友好，因為它經常要對記憶體中不相鄰的元素進行比較，是以緩存命中率要低于快速排序、歸并排序等算法。
六、排序算法的總結
1. 穩定性
在比較各個排序算法前，我們先來介紹以下穩定性這個重要的概念。它的定義如下：
如果一個排序算法能夠保留數組中重複元素的相對位置則可以被稱為是穩定的。
這個性質在有些場景中是必要的，特别是我們要對資料集進行多輪排序時。比如我們要排序的是交易事務資料集，每個交易事務都有交易時間和交易金額等資訊。我們第一輪先按照交易金額排序，然後我們想再對于這些交易事務按照交易時間排一次序。此時若排序算法是穩定的，上一步具有相同交易時間的事務在第二輪排序後的相對順序是不變的，而若算法不穩定第二輪對交易時間的排序會破壞第一輪排序的成果。顯然我們在這種情況下更希望排序算法是穩定的。
我們前面介紹的幾種算法中，穩定的排序算法有冒泡排序、插入排序和歸并排序，而選擇排序、希爾排序、快速排序和堆排序都是不穩定的。
2. 原地排序
所謂的原地排序指的是對待排數組進行排序時隻需在原數組處來回移動數組元素來實作排序。我們之前介紹的排序算法中，原地排序的算法有：選擇排序、插入排序、希爾排序、快速排序與堆排序；非原地排序算法隻有歸并排序（我們使用了tmpArray來輔助排序）。
七、實戰名企面試題
這一部分我們來一起解決幾道一線網際網路企業的關于排序的面試/筆試題，以檢驗我們的學習成果以及能夠讓我們在以後的面試中增添一份信心。
【2015阿裡巴巴研發工程師筆試題】個數約為50K的數列需要進行從小到大排序，數列特征是基本逆序(多數數字從大大小，個别亂序)，以下哪種排序算法在事先不了解數列特征的情況下性能最優。（ ） A. 冒泡排序 B. 改進冒泡排序 C. 選擇排序 D. 快速排序 E. 堆排序 F.插入排序
根據題目中的描述，首先我們可以排除A、B、C，因為它們的時間複雜度都是O(n)。接下來我們看下D選項，我們前面提到過，快速排序在最壞情況下的時間複雜度會退化至O(n^2)，F選項的插入排序在逆序數很大時性能也很差（O(n^2)）。而堆排序在最壞情況下的複雜度也為O(logn)，是以這裡我們應該選擇堆排序。
【2016阿裡巴巴校招筆試題】現有1GB資料進行排序，計算資源隻有1GB記憶體可用，下列排序方法中最可能出現性能問題的是（ ）
A. 堆排序 B. 插入排序 C. 歸并排序 D. 快速排序 E. 選擇排序 F. 冒泡排序
根據題目的描述，我們能夠很明确的知道這道題考察我們的是原地排序的概念，這裡我們隻需要選擇非原地排序的占用額外空間最大的算法，顯然答案是”C. 歸并排序"。
【京東】假設你隻有100Mb的記憶體，需要對1Gb的資料進行排序，最合适的算法是（ ）
A. 歸并排序 B. 插入排序 C. 快速排序 D. 冒泡排序
根據題目，我們可以知道，我們現有的記憶體限制使得我們無法把資料一次性加載到記憶體中，是以我們隻能先加載一部分資料，對其排序後存入磁盤中。然後再加載一些資料，把它們“合并”到已排序的資料集中去，重複這個過程直到排序完成，顯然最能勝任這個工作的是歸并排序。
【選自《劍指offer》】輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。
初看這道題，根據前面的介紹，我們立刻就能夠想好幾種方案：
第一個方案是使用（最小）優先隊列。具體方法就是把輸入數組input中的元素都添加到優先隊列中，然後調用k次delMin方法我們就能歐得到最小的k個數字。相信這種解法的代碼在了解了優先隊列的實作後我們大家都能寫出來。
第二個方案是使用冒泡排序k輪。
第三個方案是使用快速排序中的partition方法。我們知道partition方法會傳回一個索引j，會把原數組切分為a[low..j-1]（所包含元素均小于等于a[j]）和a[j..high]（所包含的元素都大于等于a[j]，N為輸入數組的尺寸）。這裡我們初始化low為0，high為input..length-1，然後調用partition方法。若傳回的j等于k-1（意味着a[low..j]中的元素數等于k），則傳回a[low..j]即可；若j大于k-1（意味着a[low..j]包含的元素數大于k），此時我們把partition的high參數更新為j-1；若j小于k-1（意味着a[low..j]的元素數小于k，此時我們把low更新為j+1）。以上情況中，隻要j不等于k-1，我們就根據j的與k-1的關系更新low或是high然後繼續調用partition方法，直到傳回的j等于k-1。具體實作代碼如下：
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
if (input == null) {
return null;
}
ArrayList<Integer> list = new ArrayList<Integer>(k);
int low = 0;
int high = input.length - 1;
int j = partition(input, low, high);
while (j != k-1){
if (j > k-1){
high = j - 1;
} else {
low = j + 1;
}
j = partition(input, low, high);
}
for (int i = 0; i < k; i++) {
list.add(input[i]);
}
return list;
}
private static int partition(int[] a, int low, int high) {
int i = low;
int j = high + 1;
int p = a[low];
while (true) {
while (a[++i] < p) {
if (i == high) {
break;
}
}
while (a[--j] > p) {
if (j == low) {
break;
}
}
if (i >= j) {
break;
}
exchange(a, i, j);
}
exchange(a, low, j);
return j;
} 複制
參考資料：
《算法（第四版）》（Sedgewick等）
http://blog.csdn.net/shakespeare001/article/details/51280814