演算法從入門到「放棄」（3）- 快速排序

08-10

來自專欄 AnotherWorld

本系列文章

演算法從入門到「放棄」（1）- 什麼是演算法？

演算法從入門到「放棄」（2）- 分而治之和解決循環

本文提煉

快速排序演算法。

什麼是排序演算法？

定義來自於維基百科，排序演算法，Sorting Algorithm.

在計算機科學中，排序演算法是一種將列表元素按一定順序排列的演算法。最常用的是數字排序和詞典排序。高效的排序對於優化其他演算法（如合併演算法）的效率非常重要，因為這些演算法需要在排序列表中輸入數據。排序對於規範化數據和生成人類可讀的輸出也很有用。更詳細點，任何排序演算法的輸出都必須滿足兩個條件：

輸出是按非遞減順序排列的（每個元素根據所需的總順序不小於前面的元素)；
輸出是輸入的一個排列（重新排序，但保留了所有原始元素）。

此外，輸入數據通常存儲在數組中，這允許我們可以隨機訪問，而不是只允許順序訪問的列表；儘管許多演算法可以在適當的修改之後應用於這兩種類型的數據。（最後一句沒有理解得很到位，故把原文在下面貼上了；有什麼更好的理解，歡迎在評論區留言，謝謝！）

Further, the input data is often stored inside of an array, which allows random access, rather than a list, which only allows sequential access; though many algorithms can be applied to either type of data after suitable modification.

什麼是快速排序？

定義來自於維基百科，快速排序，Quick Sort.

快速排序（有時稱為分區交換排序）是一種高效的排序演算法，它是一種系統的方法，可以將數組的元素按順序排列。由Tony Hoare 於1959 年開發並於1961 年出版，它到現在仍然是一種常用的排序演算法。當實現良好時，它的速度可能比其他主要競爭對手快兩到三倍，例如歸併排序或則堆排序。

快速排序是一種比較排序，這意味著它可以對任何類型的項目進行排序，其中「小於」關係（正式的，總順序）是我們人為定義的。在有效的實現中，它不是一個穩定的排序，這意味著相同排序項的相對順序沒有被保留。快速排序可以在一個數組中進行操作，需要少量額外的內存來執行排序。快速排序與選擇排序非常相似，只是快速排序並不總是選擇最壞的分區。

基本思想

快速排序使用的是分而治之策略，基本思想如下：

先從目標數據集中隨機選擇一個元素作為中心點/中間值 (pivot)。
接下來把比中間值小的數據移到中間值的左邊，把比中間值大的數據移到中間值的右邊（大概思路如此，具體操作看下面實例分析），這一過程被稱為分割/分區 (partition)。分區結束後，中間值現在所在的位置也是快速排序結束後的最終位置。
對中間值左右兩邊的資料庫分別不斷重複進行第1和第2步，直到所有的子集只剩下一個元素為止。

圖解

圖片來源：維基百科

評價演算法好壞

分類：排序演算法

最壞時間複雜度：?(n^2)

最優時間複雜度：?(n* log n)

平均時間複雜度：?(n* log n)

空間複雜度：根據實現的方式不同而不同

實例分析

舉個例子（例子來源維基百科），如下

假設我們現在現在有數組 array = [3,7,8,5,2,1,9,5,4]

1. 先隨機選擇一個數為中間值，因為任意哪個數都可以，我們這裡取5：

中間值 ↓3 7 8 5 2 1 9 5 4

2. 下面開始分區。將中間值和數組中最後一個數交換位置，如果選擇最後一個數為中間值則可以省略該步，這裡是5和4進行了交換：

中間值 ↓3 7 8 4 2 1 9 5 5

3. 接著依次從左到右（除了最後的中間值)，移動比中間值5小或相等的數到數組開頭，留下大於中間值的數在後面。在這個過程結束時，它也為中間值找到了最後擺放的位置。流程如下：

1）i == 0 時，index == 0，找到第一個小於中間值的數 3，將其與index 所在位置的數交換位置，也就是 3 自身，交換後將 index 增加 1，index == 1：

中間值 ↓ 3 7 8 4 2 1 9 5 5 ↑index

2）繼續，等到i == 3時，index == 1, 找到第二個小於中間值的數 4，交換，增加 index，index == 2:

中間值 ↓ ↓ ↓ 3 7 8 4 2 1 9 5 5 ↑ ↑ index i

3）重複步驟，i == 4，值是2，小於中間值 5，交換，增加 index，index == 3:

中間值 ↓ ↓ ↓3 4 8 7 2 1 9 5 5 ↑ ↑ index i

4）繼續，i ==5，值為1，小於5，交換，增加 index, index == 4:

中間值 ↓ ↓ ↓3 4 2 7 8 1 9 5 5 ↑ ↑ index i

5）現在i == 6，看下是怎麼個排列了：

3 4 2 1 8 7 9 5 5 ↑ ↑ index i

6）9 大於5，保持原狀即可。i ==7時，5等於中間值，交換，增加 index，index == 5:

中間值 ↓ ↓ ↓3 4 2 1 8 7 9 5 5 ↑ ↑ index i

7）最終index 的值為7，i 為7，就結束循環。循環結束後交換中間值和 index 位置的值：

3 4 2 1 5 5 9 8 7 ↑ 中間值

現在分區過程就完成了，接著就是對左右兩邊進行快速排序。

流程展示圖（圖片來源）

代碼展示

偽代碼

快速排序本身

algorithm quicksort(A, lo, hi) is //lo 最左邊值，hi 最右邊值，A 是數組 if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p - 1 ) //中間值p 左邊進行排序 quicksort(A, p + 1, hi) //中間值p 右邊進行排序

分區

algorithm partition(A, lo, hi) is pivot := A[hi] //暫定中間值是最右邊的值 i := lo - 1 //i初始值是lo -1 for j := lo to hi - 1 do //從最左邊到最右邊第二個數開始循環 if A[j] <= pivot then //如果A[j] 小於等於中間值即最右邊的值 i := i + 1 //i加1 swap A[i] with A[j] //交換A[i] 和 A[j]的位置 swap A[i + 1] with A[hi] //循環結束，交換A[i+1] 和 A[hi] return i + 1

在下一篇文章中，將著重講的是插入排序演算法。

如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！