如何實現快速排序的方法

快速排序法

HTML5學堂-碼匠：前幾期「演算法之旅」跟大家分享了冒泡排序法和選擇排序法，它們都屬於時間複雜度為O(n^ 2)的「慢」排序。今天跟大家分享多種排序演算法裡使用較廣泛，速度快的排序演算法 —— 快速排序法 [ 平均時間複雜度為O (n logn) ]。

Tips 1：關於「演算法」及「排序」的基礎知識，在先前「選擇排序法」中已詳細講解，可點擊文後的相關文章連結查看，在此不再贅述。

Tips 2：如果沒有特殊說明，本文的快速排序是從小到大的排序。

快速排序法的原理

快速排序是一種分割交換排序，它採用分治的策略，通常稱之為分治法。

分治法

基本概念：將原問題分解為若干個規模較小但結構與原問題相似的子問題。遞歸地解決這些子問題，然後將這些子問題的結果組合成原問題的結果。

基本原理

從序列中任一個數字作為「基準」；

所有小於「基準」的數，都挪到「基準」的左邊；所有大於等於「基準」的數，都移到「基準」的右邊；

在這次移動結束之後，該「基準」就處於兩個序列的中間位置，不再參與後續的排序；

針對「基準」左邊和右邊的兩個子序列，不斷重複上述步驟，直到所有子序列只剩下一個數為止。

原理圖解

現有一個序列為 [8, 4, 7, 2, 0, 3, 1]，如下示範快速排序法如何對其進行排序。

實現快速排序的步驟分解

選擇“基準”，並將其從原始數組分離

先取得基準的索引值，再使用splice數組方法取出基準值。

Tips：在此實例中， 基準的索引值 = parseInt（序列長度 / 2）

Tips：splice方法會改變原始陣列。例如，arr = [1, 2, 3]; 基準索引值為1，基準值為2，原始陣列變成arr = [1, 3];

遍歷序列，拆分序列

與「基準」比較大小，並拆分為兩個子序列

小於「基準」的數儲存於leftArr數組當中，大於等於「基準」的數儲存於rightArr數組當中

Tips：當然，也可以將小於等於「基準」的數存於leftArr，大於「基準」的數存於rightArr

由於要遍歷序列，將每一個數與「基準」進行大小比較，所以，需要藉助for語句來實現

#遞歸調用，遍歷子序列並組合子序列的結果

定義一個函數，形參用於接收陣列

1. function quickSort(arr) { };

實作遞歸呼叫遍歷子序列，用concat數組方法組合子序列的結果

判斷子序列的長度

遞歸呼叫的過程中，子序列的長度等於1時，則停止遞歸調用，返回目前數組。

快速排序法完整程式碼

#快速排序法的效率

時間複雜度

最壞情況：每一次選取的「基準」都是序列中最小的數/最大的數，這種情況與冒泡排序法類似（每次只能確定一個數[基準數]的順序），時間複雜度為O（n^2）

最好情況：每一次選取的「基準」都是序列中最中間的一個數（是中位數，而不是位置上的中間），那麼每次都把目前序列分成了長度相等的兩個子序列。這時候，第一次就有n/2、n/2兩個子序列，第二次就有n/4、n/4、n/4、n/4四個子序列，依此類推，n個數總共需要logn次才能排序完成（2^x=n，x=logn），然後每次都是n的複雜度，時間複雜度為O（n logn）

空間複雜度

最壞情況：需要進行n‐1 次遞歸調用，其空間複雜度為O（n）

最好情況：需要logn次遞歸調用，其空間複雜度為O（logn ）

演算法的穩定性

快速排序是一種不穩定排序演算法

例如：現有序列為[1, 0, 1, 3]，「基準」數字選擇為第二個1

在第一輪比較之後，變成了[0, 1, 1, 3]，左序列為[0]，右序列為[1, 3]（右序列的1是先前的第一個1）

不難發現，原序列的兩個1的先後順序被破壞了，改變了先後順序，自然就是「不穩定」的排序演算法了

關於O

在先前的「冒泡排序法」一文當中，我們詳細講解過O是什麼，在此就不多說了，直接上圖吧

以上是如何實現快速排序的方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！