快速排序的四種python實現
- 2020 年 1 月 13 日
- 筆記
快速排序演算法，簡稱快排，是最實用的排序演算法，沒有之一，各大語言標準庫的排序函數也基本都是基於快排實現的。
本文用python語言介紹四種不同的快排實現。
1. 一行程式碼實現的簡潔版本
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])
2. 網上常見的快排實現
def quick_sort(array, left, right): if left >= right: return low = left high = right key = array[low] while left < right: while left < right and array[right] > key: right -= 1 array[left] = array[right] while left < right and array[left] <= key: left += 1 array[right] = array[left] array[right] = key quick_sort(array, low, left - 1) quick_sort(array, left + 1, high)
由於快排是原地排序，因此不需要返回array。
array如果是個列表的話，可以通過len(array)求得長度，但是後邊遞歸調用的時候必須使用分片，而分片執行的原列表的複製操作，這樣就達不到原地排序的目的了，所以還是要傳上邊界和下邊界的。
3.《演算法導論》中的快排程式
def quick_sort(array, l, r): if l < r: q = partition(array, l, r) quick_sort(array, l, q - 1) quick_sort(array, q + 1, r) def partition(array, l, r): x = array[r] i = l - 1 for j in range(l, r): if array[j] <= x: i += 1 array[i], array[j] = array[j], array[i] array[i + 1], array[r] = array[r], array[i+1] return i + 1
這個版本跟上個版本的不同在於分片過程不同，只用了一層循環，並且一趟就完成分片，相比之下程式碼要簡潔的多了。
4. 用棧實現非遞歸的快排程式
先說兩句題外話，一般意義上的棧有兩層含義，一層是後進先出的數據結構棧，一層是指函數的記憶體棧，歸根結底，函數的記憶體棧的結構就是一個後進先出的棧。彙編程式碼中，調用一個函數的時候，修改的也是堆棧指針暫存器ESP，該暫存器保存的是函數局部棧的棧頂，另外一個暫存器EBP保存的是棧底。不知道與棧存儲空間相對的堆存儲空間，其組織結構是否也是一個完全二叉樹呢？
高級語言將遞歸轉換為迭代，用的也是棧，需要考慮兩個問題:
1）棧裡邊保存什麼？
2）迭代結束的條件是什麼？
棧裡邊保存的當然是需要迭代的函數參數，結束條件也是跟需要迭代的參數有關。對於快速排序來說，迭代的參數是數組的上邊界low和下邊界high，迭代結束的條件是low == high。
def quick_sort(array, l, r): if l >= r: return stack = [] stack.append(l) stack.append(r) while stack: low = stack.pop(0) high = stack.pop(0) if high - low <= 0: continue x = array[high] i = low - 1 for j in range(low, high): if array[j] <= x: i += 1 array[i], array[j] = array[j], array[i] array[i + 1], array[high] = array[high], array[i + 1] stack.extend([low, i, i + 2, high])
另外，當數組下標為-1時，C++、Java等語言中會報錯，但python中訪問的是最後一個元素，所以如果程式寫錯了，可能其他語言會報錯，但python會輸出一個錯誤的結果。
