詳細(xì)代碼請(qǐng)參考Algorithm。參考代碼比文字好理解。
堆排序是時(shí)間復(fù)雜度為O(N*lgN)的排序方法。是指利用堆積樹(shù)（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種，可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素，是完全二叉樹(shù)?；舅枷胧前汛判虻脑匕凑沾笮≡诙鏄?shù)位置上排列，排序好的元素要滿足：父節(jié)點(diǎn)的元素要大于等于其子節(jié)點(diǎn)；這個(gè)過(guò)程叫做堆化過(guò)程，如果根節(jié)點(diǎn)存放的是最大的數(shù)，則叫做大根堆；如果是最小的數(shù)，自然就叫做小根堆了。根據(jù)這個(gè)特性（大根堆根最大，小根堆根最小），就可以把根節(jié)點(diǎn)拿出來(lái)，然后再堆化下，再把根節(jié)點(diǎn)拿出來(lái)，循環(huán)到最后一個(gè)節(jié)點(diǎn)，就排序好了。
整個(gè)排序主要核心就是堆化過(guò)程，堆化過(guò)程一般是用父節(jié)點(diǎn)和他的孩子節(jié)點(diǎn)進(jìn)行比較，取最大的孩子節(jié)點(diǎn)和其進(jìn)行交換；但是要注意這應(yīng)該是個(gè)逆序的，先排序好子樹(shù)的順序，然后再一步步往上，到排序根節(jié)點(diǎn)上。然后又相反（因?yàn)楦?jié)點(diǎn)也可能是很小的）的，從根節(jié)點(diǎn)往子樹(shù)上排序。最后才能把所有元素排序好。
由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為O(1）.它是不穩(wěn)定的排序方法。（排序的穩(wěn)定性是指如果在排序的序列中，存在前后相同的兩個(gè)元素的話，排序前和排序后他們的相對(duì)位置不發(fā)生變化）
堆的存儲(chǔ)
一般都用數(shù)組來(lái)表示堆，i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i – 1) / 2。它的左右子結(jié)點(diǎn)下標(biāo)分別為2 * i + 1和2 * i + 2。如第0個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1和2。
堆的操作——插入刪除
每次插入都是將新數(shù)據(jù)放在數(shù)組最后?？梢园l(fā)現(xiàn)從這個(gè)新數(shù)據(jù)的父結(jié)點(diǎn)到根結(jié)點(diǎn)必然為一個(gè)有序的數(shù)列，現(xiàn)在的任務(wù)是將這個(gè)新數(shù)據(jù)插入到這個(gè)有序數(shù)據(jù)中——這就類似于直接插入排序中將一個(gè)數(shù)據(jù)并入到有序區(qū)間中。
堆的刪除，按定義，堆中每次都只能刪除第0個(gè)數(shù)據(jù)。為了便于重建堆，實(shí)際的操作是將最后一個(gè)數(shù)據(jù)的值賦給根結(jié)點(diǎn)，然后再?gòu)母Y(jié)點(diǎn)開(kāi)始進(jìn)行一次從上向下的調(diào)整。調(diào)整時(shí)先在左右兒子結(jié)點(diǎn)中找最小的，如果父結(jié)點(diǎn)比這個(gè)最小的子結(jié)點(diǎn)還小說(shuō)明不需要調(diào)整了，反之將父結(jié)點(diǎn)和它交換后再考慮后面的結(jié)點(diǎn)。相當(dāng)于從根結(jié)點(diǎn)將一個(gè)數(shù)據(jù)的“下沉”過(guò)程。
堆排序
堆建好之后堆中第0個(gè)數(shù)據(jù)是堆中最小的數(shù)據(jù)。取出這個(gè)數(shù)據(jù)再執(zhí)行下堆的刪除操作。這樣堆中第0個(gè)數(shù)據(jù)又是堆中最小的數(shù)據(jù)，重復(fù)上述步驟直至堆中只有一個(gè)數(shù)據(jù)時(shí)就直接取出這個(gè)數(shù)據(jù)。由于堆也是用數(shù)組模擬的，故堆化數(shù)組后，第一次將A[0]與A[n - 1]交換，再對(duì)A[0…n-2]重新恢復(fù)堆。第二次將A[0]與A[n – 2]交換，再對(duì)A[0…n - 3]重新恢復(fù)堆，重復(fù)這樣的操作直到A[0]與A[1]交換。由于每次都是將最小的數(shù)據(jù)并入到后面的有序區(qū)間，故操作完成后整個(gè)數(shù)組就有序了。
大根堆和小根堆
根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆，又稱最小堆。根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆，又稱最大堆。堆中任一子樹(shù)亦是堆。堆實(shí)際上是二叉堆（Binary Heap），類似地可定義k叉堆。
大根堆排序算法的基本操作：
①建堆，建堆是不斷調(diào)整堆的過(guò)程，從len/2處開(kāi)始調(diào)整，一直到第一個(gè)節(jié)點(diǎn)，此處len是堆中元素的個(gè)數(shù)。建堆的過(guò)程是線性的過(guò)程，從len/2到0處一直調(diào)用調(diào)整堆的過(guò)程，相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點(diǎn)的深度，len/2表示節(jié)點(diǎn)的個(gè)數(shù)，這是一個(gè)求和的過(guò)程，結(jié)果是線性的O(n)。
②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過(guò)程中會(huì)用到，而且在堆排序過(guò)程中也會(huì)用到。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i)，選出三者最大(或者最小)者，如果最大（小）值不是節(jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn)，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過(guò)程，這是一個(gè)遞歸的過(guò)程。調(diào)整堆的過(guò)程時(shí)間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的。
③堆排序：堆排序是利用上面的兩個(gè)過(guò)程來(lái)進(jìn)行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換)，將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過(guò)程，然后再將根節(jié)點(diǎn)取出，這樣一直到所有節(jié)點(diǎn)都取出。堆排序過(guò)程的時(shí)間復(fù)雜度是O(nlgn)。因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是O(n)（調(diào)用一次）；調(diào)整堆的時(shí)間復(fù)雜度是lgn，調(diào)用了n-1次，所以堆排序的時(shí)間復(fù)雜度是O(nlgn)。
