上個廁所的功夫，就學會了“快速排序”演算法

快速排序由於排序效率在同為O（N*logN）的幾種排序方法中效率較高，因此經常被採用，再加上快速排序思想——分治法也確實實用，因此很多軟體公司的筆試面試，包括像BAT、位元組、美團等知名IT公司都喜歡考查快速排序原理和手寫原始碼。

一、概念

快速排序，顧名思義就是一種以效率快為特色的排序演算法，快速排序（Quicksort）是對氣泡排序的一種改進。由英國計算機專家：託尼·霍爾（Tony Hoare）在1960年提出。

二、基本思想

從排序陣列中找出一個數，可以隨機取，也可以取固定位置，一般是取第一個或最後一個，稱為基準數。然後將比基準小的排在左邊，比基準大的放到右邊；

如何放置呢，就是和基準數進行交換，交換完左邊都是比基準小的，右邊都是比較基準大的，這樣就將一個數組分成了兩個子陣列，然後再按照同樣的方法把子陣列再分成更小的子陣列，直到不能分解（子陣列只有一個值）為止。以此達到整個資料變成有序序列。

快速排序採用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)，現在各種語言中自帶的排序庫很多使用的都是快速排序。

空間複雜度

快速排序是一種原地排序，只需要一個很小的棧作為輔助空間，空間複雜度為O（log2n），所以適合在資料集比較大的時候使用。

時間複雜度

時間複雜度比較複雜，最好的情況是O（n），最差的情況是O（n2），所以平時說的O（nlogn），為其平均時間複雜度。

O（n）：理想的情況，每次劃分所選擇的中間數恰好將當前序列幾乎等分，經過log2n趟劃分，便可得到長度為1的子表。這樣，整個演算法的時間複雜度為O（nlog2n）。

O（n2）：最壞的情況，每次所選的中間數是當前序列中的最大或最小元素，這使得每次劃分所得的子表中一個為空表，另一子表的長度為原表的長度-1。這樣，長度為n的資料表的快速排序需要經過n趟劃分，使得整個排序演算法的時間複雜度為O（n2）。

三、演算法步驟

1。選定一個基準數（一般取第一位數字）作為中心點（Pivot）；2。將大於Pivot的數字放到Pivot的左邊；3。將小於Pivot的數字放到Pivot的右邊；4。

第一次排序結束後，分別對左右子序列繼續遞迴重複前三步操作。

四、具體示例

例項陣列：arr［］ = {19，97，9，17，1，8}；

1。取出基準數Pivot，以該值為中心軸。

快速排序中的規則：右邊有坑，就從左邊Arr[L + n]取值來填，反之左邊有坑，則從右邊Arr[R - n]取值來填；

2。從左邊取的基準值，左邊的Arr［L］就空出來了，則先從右側取值來填，從最右側下標開始，在Arr［R］ 取到第一個值“8”；

3。將取到的Arr［R］與基準值比較，發現小於基準值，則插入到Arr［R］，佔到了基準值Pivot的位置上。

4。然後從Arr［L+1］的位置取出值，繼續向右匹配並排序，將匹配到的值（匹配規則如下）插入到右側Arr［R］的空位置上；

匹配規則：大於基準值的插入到Arr[R]，如果小於，則直接忽略並跳過，繼續向右取值，直到座標L和座標R重合。

5。發現取出的值大於Pivot（基準值），則將其插入到Arr［R］。

6。左邊有坑，從右邊Arr［R-1］繼續匹配，Arr［R-1］ = 1，小於基準值，則插入到Arr［L］的坑中；

7。右邊有坑了，繼續從左邊取值繼續匹配，則取到Arr［L+1］ = 9，小於基準值，則忽略並跳過，繼續找Arr［L + 1］繼續匹配。

8。繼續從左邊座標 + 1 取值繼續匹配，則取到Arr［L］ = 17，又小於基準值，則忽略並跳過，繼續找Arr［L + 1］繼續匹配。

9。最後L座標和R座標重合了，將Pivot基準值填入

10。至此，快速排序第一輪完整流程結束，分出了左右子序列，左邊都是小於Pivot基準值的，右邊都是大於Pivot基準值的。

11。

繼續對左、右

子

序列遞迴進行處理，一直縮小到左、右都是一個值，則快速排序結束，最終得出順序陣列{1,8,9,17,19,97}；

中間遞迴流程這裡不再贅述。

五、快排程式碼

@java程式碼

package com。softsec。demo； /** * Created with IDEA * * @Author Chensj * @Date 2020/5/17 19：04 * @Description * @Version 1。0 */public class quickSortDemo { public static void main（String［］ args） { // 建立測試陣列 int［］ arr = new int［］{19，97，9，17，1，8}； System。out。println（“排序前：”）； showArray（arr）； // 列印陣列 // 呼叫快排介面 quickSort（arr）； System。out。println（“\n” + “排序後：”）； showArray（arr）；// 列印陣列 } /** * 快速排序 * @param array */ public static void quickSort（int［］ array） { int len； if（array == null || （len = array。length） == 0 || len == 1） { return ； } sort（array， 0， len - 1）； } /** * 快排核心演算法，遞迴實現 * @param array * @param left * @param right */ public static void sort（int［］ array， int left， int right） { if（left > right） { return； } // base中存放基準數 int base = array［left］； int i = left， j = right； while（i ！= j） { // 順序很重要，先從右邊開始往左找，直到找到比base值小的數 while（array［j］ >= base && i < j） { j——； } // 再從左往右邊找，直到找到比base值大的數 while（array［i］ <= base && i < j） { i++； } // 上面的迴圈結束表示找到了位置或者（i>=j）了，交換兩個數在陣列中的位置 if（i < j） { int tmp = array［i］； array［i］ = array［j］； array［j］ = tmp； } } // 將基準數放到中間的位置（基準數歸位） array［left］ = array［i］； array［i］ = base； // 遞迴，繼續向基準的左右兩邊執行和上面同樣的操作 // i的索引處為上面已確定好的基準值的位置，無需再處理 sort（array， left， i - 1）； sort（array， i + 1， right）； } /** * 陣列列印 * @param num */ private static void showArray（int［］ num） { for （int i = 0； i < num。length； i++） { System。out。print（num［i］ + “ ”）； } }}

返回結果：

排序前：19 97 9 17 1 8 排序後：1 8 9 17 19 97 Process finished with exit code 0

@python程式碼

#快速排序 傳入列表、開始位置和結束位置def quick_sort（ li ， start ， end ）： # 如果start和end碰頭了，說明要我排的這個子數列就剩下一個數了，就不用排序了 if not start < end ： return mid = li［start］ #拿出第一個數當作基準數mid low = start #low來標記左側從基準數始找比mid大的數的位置 high = end #high來標記右側end向左找比mid小的數的位置 # 我們要進行迴圈，只要low和high沒有碰頭就一直進行，當low和high相等說明碰頭了 while low < high ： #從high開始向左，找到第一個比mid小或者等於mid的數，標記位置，（如果high的數比mid大，我們就左移high） # 並且我們要確定找到之前，如果low和high碰頭了，也不找了 while low < high and li［high］ > mid ： high -= 1 #跳出while後，high所在的下標就是找到的右側比mid小的數 #把找到的數放到左側的空位 low 標記了這個空位 li［low］ = li［high］ # 從low開始向右，找到第一個比mid大的數，標記位置，（如果low的數小於等於mid，我們就右移low） # 並且我們要確定找到之前，如果low和high碰頭了，也不找了 while low < high and li［low］ <= mid ： low += 1 #跳出while迴圈後low所在的下標就是左側比mid大的數所在位置 # 我們把找到的數放在右側空位上，high標記了這個空位 li［high］ = li［low］ #以上我們完成了一次 從右側找到一個小數移到左側，從左側找到一個大數移動到右側 #當這個while跳出來之後相當於low和high碰頭了，我們把mid所在位置放在這個空位 li［low］ = mid #這個時候mid左側看的數都比mid小，mid右側的數都比mid大 #然後我們對mid左側所有數進行上述的排序 quick_sort（ li ， start， low-1 ） #我們mid右側所有數進行上述排序 quick_sort（ li ， low +1 ， end ） #入口函式if __name__ == ‘__main__’： li = ［19，97，9，17，1，8］ quick_sort（li ， 0 ， len（li） -1 ） print（li）

六、總結

快速排序是當前最為流行的排序演算法之一，各大公司面試中頻頻出現，希望透過這篇文章，讓你對快速排序知識點有一定的瞭解，在日後面試或各種考試中對你有所幫助！

目前在職Java開發，如果你現在也在學習Java，在入門學習Java的過程當中缺乏基礎入門的影片教程， 可以關注並私信我：01。免費領取2020年最新Java基礎精講影片教程，學習手冊，面試題，開發工具，PDF文件書籍教程，以下資料截圖：

關注並私信我：01。即可領取以上學習資料。