大家好，歡迎來到 crossin的編程教室 ！
如果你還不懂快速排序，那麼希望這篇講解可以讓你理解快排的核心思想。
之前我介紹過代碼可視化工具pythontutor，並且用快排的代碼做了演示。
一個能幫你看懂程序的代碼可視化工具
後來有小夥伴說沒太看懂。那今天我們就用pythontutor來詳細過一遍這個快排的代碼。
快速排序是一種非常常見的排序演算法，雖然在實際開發中，你幾乎不需要自己去寫，但它卻是筆試面試的高頻問題，甚至「手寫快排」已經成為了一個梗。
快排的原理說起來很簡單，就是從序列中挑出一個基準的數，比它小的放左邊，比它大或相等的放右邊。然後對兩邊的序列再分別採用這個方式進一步劃分，直到子序列只剩下一個或沒有元素為止。
這種思想叫作分治，就是把一個複雜的問題劃分成相同或相似子問題，以此類推，直到子問題可以簡單求解。分治在代碼上的實現通常會用到遞歸函數。
來看具體的代碼：
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[0]left = []right = []for i in arr[1:]:if i < pivot:left.append(i)else:right.append(i)return quick_sort(left) + [pivot] + quick_sort(right)arr = [3, 2, 7, 9, 5, 1, 8]sorted_arr = quick_sort(arr)print(sorted_arr)
quick_sort就是實現快排的遞歸函數，arr是待排序的列表
遞歸函數都需要有一個結束條件，不然程序就要死循環到stackoverflow了，這裡的結束條件就是序列的長度小於等於1，因為沒有元素或只有1個元素的序列不用做任何操作它就是有序的。
當然一開始，我們這個序列是不滿足的，於是程序往下走，選取列表第一個元素3為pivot，也就是基準數，然後創建左右兩個子列表。接下來就是對第一個元素往後的列表進行遍歷，比基準小的（2、1）就加到左列表，相等或大的（7、9、5、8）就加到右列表。
到這裡都還比較好理解，然後接下來就是整個代碼最核心的一句話了。
return quick_sort(left) + [pivot] + quick_sort(right)這裡直接就return返回結果了，結果是什麼呢，是把左列表進行快排的結果，加上基準數，再加上右列表進行快排的結果。
看起來好像還挺簡單的，可是現在左列表和右列表都還沒有排序呢，怎麼就能這樣加起來呢？
哎，這就是遞歸的精妙之處。我們繼續結合代碼往下走。
單看這行代碼的優先順序，會先去調用quick_sort(left)拿到返回值，再調用quick_sort(right)拿到返回值，然後再執行列表的+運算，也就是合併列表，最後return返回。
那現在再次進入 quick_sort，參數就成了 left，也就 [2, 1]。雖然這時候人眼一看就知道排序結果應該是 [1, 2]，但程序還是要一步一步來。pivot是2，left 是 [1]，right是空列表。然後繼續下一層的遞歸。這時候，quick_sort([1]) 和 quick_sort([]) 都會觸髮結束條件了，於是直接返回，返回結果再和剛才這一層的pivot，也就是 [2] 合併在一起，就成了 [1, 2]。然後，它才能返回給再上面一層的函數，也就是我們最外層的quick_sort裡面這個quick_sort(left)的結果。
解決了quick_sort(left)，接下來就是quick_sort(right)了，這時參數成了[7,9,5,8]，pivot是7，left是[5]，right是[9,8]。
left因為只有一個元素所以調用後直接返回，但right還要繼續往下走，pivot是9，left是[8]，right是[]，再多調用一層，然後返回[8,9]，再跟上一層合併成[5,7,8,9]，返回給最外層。
這時候遞歸調用的函數全部都返回了，left、pivot、right再加一起，就是最後的結果[1,2,3,5,7,8,9]，返回並輸出，程序結束。
快速排序還有其他一些寫法，比如不新建子列表，而是在原列表上通過交換元素位置達到劃分左右子列表的目的，又比如使用列表裡前中後三個元素的中值作為劃分的基準數。這些會在一定程度上優化程序的執行效率，但核心的演算法原理還是一樣的。
如果本文對你有幫助，歡迎點贊、評論、轉發。你們的支持是我更新的動力~
