本文實例講述了Python實現堆排序的方法。分享給大家供大家參考，具體如下：
堆排序作是基本排序方法的一種，類似于合并排序而不像插入排序，它的運行時間為O(nlogn)，像插入排序而不像合并排序，它是一種原地排序算法，除了輸入數組以外只占用常數個元素空間。
堆（定義）：（二叉）堆數據結構是一個數組對象，可以視為一棵完全二叉樹。如果根結點的值大于（小于）其它所有結點，并且它的左右子樹也滿足這樣的性質，那么這個堆就是大（小）根堆。
我們假設某個堆由數組A表示，A[1]為樹的根，給定某個結點的下標i，其父結點、左孩子、右孩子的下標都可以計算出來：
PARENT(i):
return i/2
LEFT(i):
return 2i
RIGHT(i):
return 2i+1
堆排序Python實現
所謂堆排序的過程，就是把一些無序的對象，逐步建立起一個堆的過程。
下面是用Python實現的堆排序的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
def build_max_heap(to_build_list): """建立一個堆""" # 自底向上建堆 for i in range(len(to_build_list)/2 - 1, -1, -1): max_heap(to_build_list, len(to_build_list), i)def max_heap(to_adjust_list, heap_size, index): """調整列表中的元素以保證以index為根的堆是一個最大堆""" # 將當前結點與其左右子節點比較，將較大的結點與當前結點交換，然后遞歸地調整子樹 left_child = 2 * index + 1 right_child = left_child + 1 if left_child < heap_size and to_adjust_list[left_child] > to_adjust_list[index]: largest = left_child else: largest = index if right_child < heap_size and to_adjust_list[right_child] > to_adjust_list[largest]: largest = right_child if largest != index: to_adjust_list[index], to_adjust_list[largest] = \ to_adjust_list[largest], to_adjust_list[index] max_heap(to_adjust_list, heap_size, largest)def heap_sort(to_sort_list): """堆排序""" # 先將列表調整為堆 build_max_heap(to_sort_list) heap_size = len(to_sort_list) # 調整后列表的第一個元素就是這個列表中最大的元素，將其與最后一個元素交換，然后將剩余的列表再調整為最大堆 for i in range(len(to_sort_list) - 1, 0, -1): to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i] heap_size -= 1 max_heap(to_sort_list, heap_size, 0)if __name__ == '__main__': to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] heap_sort(to_sort_list) print to_sort_list |
希望本文所述對大家Python程序設計有所幫助。
