相對冒泡排序、選擇排序等算法而言，快速排序的具體算法原理及實現有一定的難度。為了更好地理解快速排序，我們仍然以舉例說明的形式來詳細描述快速排序的算法原理。在前面的排序算法中，我們以5名運動員的身高排序問題為例進行講解，為了更好地體現快速排序的特點，這里我們再額外添加3名運動員。實例中的8名運動員及其身高信息詳細如下(F、G、H為新增的運動員)： A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
在前面的排序算法中，這些排序都是由教練主導完成了，現在運動員人數增加了，教練也想趁機去休息一下，于是教練叫來了兩名助手，讓這兩名助手以快速排序法的排序方式來實現對8名運動員的身高從左到右、從低到高的排序。
按照快速排序法的算法原理，兩名助手分別站在運動員排列的兩側，如下圖所示：
首先，助手1從排列中選出一名運動員(一般選擇左側第1位運動員或最中間的運動員)，這里選擇運動員A(181)。由于排序是從左到右、從低到高，所以助手1需要一個身高比A(181)更小的運動員(選出來的A(181)作為比較的基準，本輪所有的比較，都是與最初選出來的運動員A(181)比較)：
下面我們來繼續參考快速排序第一輪的詳細示意圖。
當兩名助手在排序尋找的過程中相遇后，就停止當前輪次的比較，并把最初選出來的運動員A(181)放在兩名助手相遇的空位上：
在快速排序中，當兩名助手相遇時，本輪排序就結束了。此時，我們發現，以兩名運動員相遇的位置A(181)作為分割點，排列左邊的都是身高比A(181)小的運動員，排列右側的都是身高比A(181)大的運動員。這個時候，我們再把A(181)左側和右側的兩個排序分開來看，如果我們繼續使用上述兩名助手的排序方法分別對兩邊的排列進行排序，那么經過多次排列后，最后就能夠得到我們所需要的排序結果。
上面就是快速排序的整個排序實現過程。快速排序就是利用上述的排序規則，將一個排列分為兩個排列，兩個排列分為四個排列，直到無排列可分為止，最后就得到了我們所需要的排序結果。
現在，我們依然編程Java代碼來實現使用快速排序對上述8名運動員的身高進行排序：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
/** * 對指定的數組中索引從start到end之間的元素進行快速排序 * * @param array 指定的數組 * @param start 需要快速排序的數組索引起點 * @param end 需要快速排序的數組索引終點 */public static final void quickSort(int[] array, int start, int end) { // i相當于助手1的位置，j相當于助手2的位置 int i = start, j = end; int pivot = array[i]; // 取第1個元素為基準元素 int emptyIndex = i; // 表示空位的位置索引，默認為被取出的基準元素的位置 // 如果需要排序的元素個數不止1個，就進入快速排序(只要i和j不同，就表明至少有2個數組元素需要排序) while (i < j) { // 助手2開始從右向左一個個地查找小于基準元素的元素 while (i < j && pivot <= array[j]) j--; if (i < j) { // 如果助手2在遇到助手1之前就找到了對應的元素，就將該元素給助手1的"空位"，j成了空位 array[emptyIndex] = array[emptyIndex = j]; } // 助手1開始從左向右一個個地查找大于基準元素的元素 while (i < j && array[i] <= pivot) i++; if (i < j) { // 如果助手1在遇到助手2之前就找到了對應的元素，就將該元素給助手2的"空位"，i成了空位 array[emptyIndex] = array[emptyIndex = i]; } } // 助手1和助手2相遇后會停止循環，將最初取出的基準值給最后的空位 array[emptyIndex] = pivot; // =====本輪快速排序完成===== // 如果分割點i左側有2個以上的元素，遞歸調用繼續對其進行快速排序 if (i - start > 1) { quickSort(array, 0, i - 1); } // 如果分割點j右側有2個以上的元素，遞歸調用繼續對其進行快速排序 if (end - j > 1) { quickSort(array, j + 1, end); }}//主方法public static void main(String[] args) { // =====使用快速排序法對表示8名運動員身高的數組heights進行從低到高的排序===== // A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182) int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 }; // 調用快速排序方法 quickSort(heights, 0, heights.length - 1); // 輸出排序后的結果 for (int height : heights) { System.out.println(height); }} |
以上Java代碼運行結果輸出如下：
|
1
2
3
4
5
6
7
8
|
163169172181182187189191 |
注意：由于局部思維差異，上述快速排序的代碼實現可能存在多種變體。不過，無論何種形式的變體，快速排序的核心思想并不會發生改變。
另一種實現：單向掃描
快速排序的數組切分還有另一種單向掃描的版本，具體步驟是選擇數組中最后一個元素作為切分元素，同樣設置兩個指針，指針i指向數組中第一個元素前面一個位置，j則指向數組中第一個元素。j從前左右往右掃描，遇到小于等于切分元素時就把i加一，然后交換i和j指向的元素。最后把i+1位置的元素和切分元素交換即可完成一次數組劃分。代碼實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
int partition(int[] a, int lo, int hi) { int i = lo - 1, j = lo; int v = a[hi]; while (j < hi) { if (a[j] <= v) { swap(a, ++i, j); } j++; } swap(a, i + 1, hi); return i + 1;} |
