Python 實現快排、堆排

---

1、快排

原理：（升序）

選取數組的首個元素做為中間值，緩存這個中間值，該位置變為空；

從右到左和中間值對比，找到第一個小于中間值的元素，把該值放到左邊的空位，該位置變為空；

從左到右和中間值對比，找到第一個大于中間值的元素，把該值放到右邊的空位，該位置變為空；

重復步驟2和3，直到左右空位相交，然后把緩存的中間值填入該位；

從第4步驟的左右空位相交位為界，分左右兩邊重復1-4步驟，直到需要排序數組的長度≤1；

程序代碼：

# 快排 def quick_sort(A, l, r):if l < r:pivot = A[l]left = lright = rwhile left < right:while A[right] > pivot and left < right:right -= 1# 左右不能相等，相等的話會進行移動，導致數組越界if left < right:A[left] = A[right]left += 1while A[left] <= pivot and left < right:left += 1if left < right:A[right] = A[left]right -= 1A[left] = pivotquick_sort(A, l, left-1)quick_sort(A, left+1, r)if __name__ == '__main__':S = [0, 2, 1, 6]quick_sort(S, 0, 3)print(S)

2、堆排

原理（用數組表示完全二叉樹的層序，最小堆）：

從最后一個葉子節點的父節點開始，比較該節點與子節點的大小；

如果父節點是最小值，繼續比較前面的節點；如果父節點不是最小值，父節點與最小值節點交換位置，并且考慮該變換對最小值節點的子節點的影響；

直到比較到根節點

程序代碼：

# 堆排 def heap_sort(A):for i in range((len(A) - 1) // 2, -1, -1):while i < len(A):# 子節點與父節點的位置關系left, right = i * 2 + 1, i * 2 + 2min_pos = iif (left < len(A)) and (A[left] < A[min_pos]):min_pos = leftif (right < len(A)) and (A[right] < A[min_pos]):min_pos = right# 如果最小值的位置改變了，需要考慮這個改變帶來的影響if min_pos != i:A[i], A[min_pos] = A[min_pos], A[i]i = min_poselse:breakif __name__ == '__main__':S = [4, 3, 2, 1]heap_sort(S)print(S)

---

GOOD LUCK!

---

總結

以上是生活随笔為你收集整理的Python 实现快排、堆排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。