本文實例講述了Python實現的堆排序算法。分享給大家供大家參考，具體如下：
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
具體代碼如下：
|
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
|
#-*- coding: UTF-8 -*-import numpy as npdef MakeHeap(a): for i in xrange(a.size / 2 - 1, -1, -1):#對非葉子節點的子節點進行調節，構建堆 AdjustHeap(a, i, a.size)def AdjustHeap(a, i, n): j = i*2 +1 #選擇節點i的左子節點 x = a[i] #選擇節點的數值 while j < n: #循環對子節點及其子樹進行調整 if j + 1 < n and a[j+1] < a[j]: #找到節點i子節點的最小值 j += 1 if a[j] >= x : #若兩個子節點均不小于該節點，則不同調整 break a[i], a[j] = a[j], a[i] #將節點i的數值與其子節點中最小者的數值進行對調 i = j #將i賦為改變的子節點的索引 j = i*2 + 1 #將j賦為節點對應的左子節點def HeapSort(a): MakeHeap(a) #構建小頂堆 for i in xrange(a.size - 1,0, -1): #對堆中的元素逆向遍歷 a[i], a[0] = a[0], a[i] #將堆頂元素與堆中最后一個元素進行對調，因為小頂堆中堆頂元素永遠最小，因此，輸出即為最小元素 AdjustHeap(a, 0, i) #重新調整使剩下的元素仍為一個堆if __name__ == '__main__': a = np.random.randint(0, 10, size = 10) print "Before sorting..." print "---------------------------------------------------------------" print a print "---------------------------------------------------------------" HeapSort(a) print "After sorting..." print "---------------------------------------------------------------" print a[::-1] #因為堆排序按大到小進行排列，采用a[::-1]對其按從小到大進行輸出 print "---------------------------------------------------------------" |
運行結果：
希望本文所述對大家Python程序設計有所幫助。
原文鏈接：http://www.cnblogs.com/biaoyu/p/4831640.html
