大家好，歡迎來到 Crossin的編程教室 ！
如果你還不懂快速排序，那麽希望這篇講解可以讓你理解快排的核心思想。
上次介紹了程式碼視覺化工具pythontutor，並且用快排的程式碼做了演示。
後來有小夥伴說沒太看懂。那今天我們就用pythontutor來詳細過一遍這個快排的程式碼。
快速排序是一種非常常見的排序演算法，雖然在實際開發中，你幾乎不需要自己去寫，但它卻是筆試面試的高頻問題，甚至「手寫快排」已經成為了一個梗。
快排的原理說起來很簡單，就是從序列中挑出一個基準的數，比它小的放左邊，比它大或相等的放右邊。然後對兩邊的序列再分別采用這個方式進一步劃分，直到子序列只剩下一個或沒有元素為止。
這種思想叫作 分治 ，就是把一個復雜的問題劃分成相同或相似子問題，以此類推，直到子問題可以簡單求解。分治在程式碼上的實作通常會用到 遞迴函式 。
來看具體的程式碼：
def quick_sort(arr): if len(arr) <= 1: return arr pivot = 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]，返回並輸出，程式結束。
快速排序還有其他一些寫法，比如不新建子列表，而是在原列表上透過交換元素位置達到劃分左右子列表的目的，又比如使用列表裏前中後三個元素的中值作為劃分的基準數。這些會在一定程度上最佳化程式的執行效率，但核心的演算法原理還是一樣的。
作者：Crossin的編程教室
Crossin的新書【 碼上行動：用ChatGPT學會Python編程 】已經上市了。 本書以ChatGPT為輔助，系統全面地講解了如何掌握Python編程，適合Python零基礎入門的讀者學習。
購買後可加入讀者交流群，Crossin為你開啟陪讀模式，解答你在閱讀本書時的一切疑問。
添加微信 crossin123 ，加入編程教室共同學習 ~
感謝 轉發 和 點贊 的各位~
