本文實例講述了Python堆排序原理與實現(xiàn)方法。分享給大家供大家參考，具體如下：
在這里要事先說明一下我也是新手，很多東西我了解不是很深入，寫算法完全是鍛煉自己邏輯能力同時順帶幫助讀研的朋友么解決一些實際問題。所以很多時候考慮的東西不是很全面能請各位看到博文的大牛們指正。對于排序算法說實在的我覺得已經(jīng)寫爛了，但是為什么還是要過一遍呢？還是為了能夠打牢基礎(chǔ)。說一下自己的看法，對于已經(jīng)的玩爛的算法因該怎么學。首先最重要的還是了解算法的基本模型和算法思想，我覺得這是非常重要的。其次的話首先先嘗試自己實現(xiàn)算法每個步驟的功能，當遇到瓶頸的時候回去看算法思想。當你寫出來的時候就應(yīng)該去網(wǎng)上找找有沒有更好的實現(xiàn)方法。編程大的魅力在于每個人都有每個人的套路。然后去思考自己還有哪些地方寫的不夠好。寫算法實際上目標只有兩個，對基礎(chǔ)語法的鞏固和對算法思想的理解。
堆排序
堆
在這里首先要先解釋一下什么是堆，堆棧是計算機的兩種最基本的數(shù)據(jù)結(jié)構(gòu)。堆的特點就是FIFO(first in first out)先進先出，這里的話我覺得可以理解成樹的結(jié)構(gòu)。堆在接收數(shù)據(jù)的時候先接收的數(shù)據(jù)會被先彈出。
棧的特性正好與堆相反，是屬于FILO(first in/last out)先進后出的類型。棧處于一級緩存而堆處于二級緩存中。這個不是本文重點所以不做過多展開。
堆排序節(jié)點訪問和操作定義
堆節(jié)點的訪問
在這里我們借用wiki的定義來說明：
通常堆是通過一維數(shù)組來實現(xiàn)的。在陣列起始位置為0的情況中
(1)父節(jié)點i的左子節(jié)點在位置(2*i+1);
(2)父節(jié)點i的右子節(jié)點在位置(2*i+2);
(3)子節(jié)點i的父節(jié)點在位置floor((i-1)/2);
堆操作
堆可以分為大根堆和小根堆，這里用大堆的情況來定義操作:
(1)大堆調(diào)整(MAX_Heapify):將堆的末端子節(jié)點作調(diào)整，使得子節(jié)點永遠小于父節(jié)點。這是核心步驟，在建堆和堆排序都會用到。比較i的根節(jié)點和與其所對應(yīng)i的孩子節(jié)點的值。當i根節(jié)點的值比左孩子節(jié)點的值要小的時候，就把i根節(jié)點和左孩子節(jié)點所對應(yīng)的值交換，當i根節(jié)點的值比右孩子的節(jié)點所對應(yīng)的值要小的時候，就把i根節(jié)點和右孩子節(jié)點所對應(yīng)的值交換。然后再調(diào)用堆調(diào)整這個過程，可見這是一個遞歸的過程。
(2)建立大堆(Build_Max_Heap):將堆所有數(shù)據(jù)重新排序。建堆的過程其實就是不斷做大堆調(diào)整的過程，從len/2出開始調(diào)整，一直比到第一個節(jié)點。
(3)堆排序(HeapSort):移除位在第一個數(shù)據(jù)的根節(jié)點，并做大堆調(diào)整的遞歸運算。堆排序是利用建堆和堆調(diào)整來進行的。首先先建堆，然后將堆的根節(jié)點選出與最后一個節(jié)點進行交換，然后將前面len-1個節(jié)點繼續(xù)做堆調(diào)整的過程。直到將所有的節(jié)點取出，對于n個數(shù)我們只需要做n-1次操作。
這里用網(wǎng)上的一張直觀圖來感受一下
代碼：
重慶分公司
重慶分公司
# -*- coding: utf-8 -*-
#! python2
import random
def MAX_Heapify(heap,HeapSize,root):#在堆中做結(jié)構(gòu)調(diào)整使得父節(jié)點的值大于子節(jié)點
left = 2*root + 1
right = left + 1
larger = root
if left < HeapSize and heap[larger] < heap[left]:
larger = left
if right < HeapSize and heap[larger] < heap[right]:
larger = right
if larger != root:#如果做了堆調(diào)整則larger的值等于左節(jié)點或者右節(jié)點的，這個時候做對調(diào)值操作
heap[larger],heap[root] = heap[root],heap[larger]
MAX_Heapify(heap, HeapSize, larger)
def Build_MAX_Heap(heap):#構(gòu)造一個堆，將堆中所有數(shù)據(jù)重新排序
HeapSize = len(heap)#將堆的長度當獨拿出來方便
for i in xrange((HeapSize -2)//2,-1,-1):#從后往前出數(shù)
MAX_Heapify(heap,HeapSize,i)
def HeapSort(heap):#將根節(jié)點取出與最后一位做對調(diào)，對前面len-1個節(jié)點繼續(xù)進行對調(diào)整過程。
Build_MAX_Heap(heap)
for i in range(len(heap)-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
MAX_Heapify(heap, i, 0)
return heap
if __name__ == '__main__':
a = [30,50,57,77,62,78,94,80,84]
print a
HeapSort(a)
print a
b = [random.randint(1,1000) for i in range(1000)]
print b
HeapSort(b)
print b另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
