算法之旅 | 快速排序法

AlanKeene 發布于2019-08-22 11:11 / 1247人閱讀

摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時間復雜度為。快速排序法的原理快速排序是一種劃分交換排序，它采用分治的策略，通常稱其為分治法。

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語句來實現

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

定義一個函數，形參用于接收數組

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是什么，在此就不多說了，直接上圖吧

相關文章鏈接

算法之旅 | 選擇排序法
算法之旅 | 冒泡排序法

開開心心每一天

生活艱辛，代碼不易，但，不要忘記微笑！

云服務器 GPU云服務器快速排序法js 快速排序算法最好的快速排序算法最快速的排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/91960.html

算法之旅 | 選擇排序法

摘要：由于排序的算法有很多，在本次算法系列的分享當中，我們先從簡單易上手的選擇排序法開始，其它的排序算法會隨后陸續跟大家一起分享。 HTML5學堂-碼匠：數據快速的計算與排序，與前端頁面性能有直接的關系。由于排序的算法有很多，在本次算法系列的分享當中，我們先從簡單易上手的選擇排序法開始，其它的排序算法會隨后陸續跟大家一起分享。算法的基本概念算法是什么，它有何作用為解決一個問題而采取的方...

liaorio 2019-08-20 18:52 評論0 收藏0
算法之旅 | 冒泡排序法

摘要：學堂碼匠本期繼續走入算法冒泡排序法。冒泡排序法完整代碼冒泡排序法的優化假如序列的數據為使用上面的冒泡排序法進行排序，得到的結果肯定沒有問題，但是，待排序的序列是有序的，理論上是無需遍歷排序。 HTML5學堂-碼匠：本期繼續走入算法 —— 冒泡排序法。冒泡排序算法相對簡單，容易上手，穩定性也比較高,算是一種較好理解的算法，也是面試官高頻提問的算法之一。 Tips：關于算法及排序的基礎知識...

qujian 2019-08-20 19:05 評論0 收藏0