排序算法之快速排序（Quicksort）解析

no_mkd

一。快速排序算法的優點，為什麼稱之為快排？

Quicksort 是對歸並排序算法的優化，繼承了歸並排序的優點，同樣應用了分治思想。

所謂的分治思想就是對一個問題「分而治之」，用分治思想來解決問題需要兩個步驟：

1. 如何「分」？（如何縮小問題的規模）
2. 如何「治」？（如何解決子問題）

快排的前身是���並，而正是因為歸並存在不可忽視的缺點，才產生了快排。歸並的最大問題是需要額外的存儲空間，並且由於合併過程不確定，致使每個元素在序列中的最終位置上不可預知的。針對這一點，快速排序提出了新的思路：把更多的時間用在「分」上，而把較少的時間用在「治」上。從而解決了額外存儲空間的問題，並提升了算法效率。

快排之所以被稱為「快」排，是因為它在平均時間上說最快的，主要原因是硬件方面的，每趟快排需要指定一個「支點」（也就是作為分界點的值），一趟中涉及的所有比較都是與這個「支點」來進行比較的，那麼我們可以把這個「支點」放在寄存器裡，如此這般，效率自然大大提高。除此之外，快排的高效率與分治思想也是分不開的。

二。算法思想

按照快排的思想，對一已知序列排序有如下步驟：

1. 指定「支點」

   注意，是「指定」，並沒有明確的約束條件，也就是說這個支點是任意一個元素，一般我們選擇兩種支點：當前序列首元，或者隨機選取

   兩種方式各有優劣，前者勝在簡單，但可能影響算法效率

   快排中，支點的最終位置越靠近中間位置效率越高，讀起來可能有點怪怪的，注意支點是一個值（具體元素），而不是字面意思的位置，當支點在最終序列中的位置靠前或者靠後時算法效率都不高（類似於「最壞情況」）

   因此，後者在一定程度上減少了最壞情況的發生次數，但隨機選取需要耗費額外的時間

   所以在具體應用中一般採用第一種方式來指定「支點」，也就是直接把當前序列的首元作為「支點」

2. 進行一趟快排

   快排中，一趟操作的最終目的是把「支點」放到它應該去的地方，舉個例子，已知序列{7, -1, 5, 23, 100, 101}，那麼第一趟快排的結果是{_, _, 7, _, _, _}

   可以看到，首元（支點）已經去了它該去的地方（在最終的結果序列中，7 就在中間位置，沒錯吧）

3. 對子序列進行快排

   第 2 步不僅確定了 7 的最終位置，還把原序列自然地劃分為兩個子序列{_, _}和{_, _, _}，這裡用"_"代替具體的數值，因為我們也不知道第 2 步的結果具體是什麼，除非真正地做一趟快排，當然，在這裡不必要，下面會有針對具體例子的詳細解釋

   很自然的我們想到了對子序列進行同樣的操作，然後對子序列的子序列再進行同樣的操作...遞歸

   當所有的子序列長度都為 1 的時候，排序結束

三。具體實例

現有一序列{9, 0, 8, 10, -5, 2, 13, 7}，我們用快速排序算法來對其排序

首先，聲明一些特殊的記號，便於描述

• 數字後面跟的大寫字母表示指針，例如 2.5P 表示指針 P 指向元素 2.5 所在的位置
• @表示垃圾數字，也就是說，當前位置是幾都無所謂，不必糾結於此，後面會有具體解釋
• _表示該位的元素與上一行一樣（_表示不變）

P.S.想要真正弄明白的話，現在拿出紙和筆吧，光靠眼睛是絕對不夠的

下面正式開始一趟快排的過程解析

解釋：

1. 第一行是初始狀態，快排需要兩個指針 L 和 H（表示低位 Low，高位 High），一個臨時變量 temp

   初始時，低位指針 L 指向首元 9，高位指針 H 指向尾元 7，temp=首元 9（temp 就是所謂的」支點「）

2. 進行如下操作：（先不要問為什麼）

   比較*H 與 temp，若*H 大，則向前移動 H 繼續比較，若*H 小，則*L = *H，*H = @（H 指向的值變成垃圾數字了），向後移動 L

   因為 7 < 9，所以把 L 指向的 9 變成 7，把 H 指向的 7 變成垃圾數字，向後移動 L 指針，得到第二行的結果

3. 進行如下操作：（先不要問為什麼）

   比較*L 與 temp，若*L 小，則向後移動 L 繼續比較，若*L 大，則*H = *L，*L = @（L 指向的值變成垃圾數字了），向前移動 H

   因為 0 < 9，所以向後移動 L，得到第三行的結果

4. 因為 8 < 9，同上
5. 因為 10 > 9，所以把 H 指向的垃圾數字 @變成 10，把 L 指向的 10 變成垃圾數字，向前移動 H 指針，得到第 5 行的結果
6. 因為 13 > 9，所以向前移動 H 指針，得到第 6 行的結果
7. 因為 2 < 9，所以把 L 指向的垃圾數字 @變成 2，把 H 指向的 2 變成垃圾數字，並向後移動 L 指針，得到第 7 行的結果
8. 因為 -5 < 9，所以向後移動 L 指針得到第 8 行的結果
9. 進行如下操作：（先不要問為什麼）

   若 L = H，則*L = *H = temp，一趟快排結束

   因為 L 指針與 H 指針重合了，所以把 L 指向的垃圾數字 @變成 temp 的值 9，一趟結束

   至此，我們確定了支點 9 的最終位置，給定序列也被自然的分為兩個子序列{7, 0, 8, 2, -5}和{13, 10}，對子序列進行相同的操作，最終能夠得到有序序列

下面來解釋上面提到的三組操作

簡單的說，上面的三組操作上為了找出 temp 的最終位置，每一步都保證 L 前面都比 temp 小，H 後面都比 temp 大。所以，H 與 L 重合的位置上的元素只能是 temp 的值了

上面提到的三組操作可以簡化成下面的幾條規則，便於記憶：

1. L 指向的值小則 L 移動，反之賦值並移動指針
2. H 指向的值大則 H 移動，反之同上
3. 若 HL 重合，則賦值 temp
4. H，L 輪流與 temp 比較，規則是賦值一次後算一輪結束（所以一開始也可以從 L 與 temp 開始比較，下一輪 H 與 temp 比，再下一輪...）

P.S.至於怎麼移動，自然是低位指針只能向高位移動，反之亦然。至於賦值後移動哪個指針，當然是另一個指針（非當前指針）了

四。總結

排序算法的應用都需要結合具體環境來考慮，例如若給定序列部分有序，自然是折半插入算法最快...

快速排序也並不是最好的，它的」快「是建立在綜合考慮的基礎上，具體情況則不一定

快速排序也不是萬能的，例如當給定序列規模很小時，選擇排序就要比快排好很多

另外，常見的排序算法有：

1. 桶排序/箱排序（Bucketsort）
2. 基數排序（Radixsort）
3. 插入排序（Insertsort）
4. 選擇排序（Selectsort）
5. 歸並排序（Mergesort）
6. 快速排序（Quicksort）
7. 堆排序（Heapsort）