堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。堆分為大根堆和小根堆。大根堆的要求是每個節(jié)點的值都不大于其父節(jié)點的值。?在數(shù)組的非降序排序中，需要使用的就是大根堆，因為根據(jù)大根堆的要求可知，最大的值一定在堆頂。查看完整代碼

1.堆的存儲：ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），當(dāng)然，這是小根堆，大根堆則換成>=號。//k(i）父節(jié)點，K(2i）則是左子節(jié)點，k(2i+1）是右子節(jié)點

2.算法思想：

(1) 先將構(gòu)建一個大根堆，此堆為初始的無序區(qū)

(2) 再將堆頂(根節(jié)點)與最后一個元素交換，由此得到新的無序區(qū)array[1..n-1]和有序區(qū)array[n]。

(3)由于交換后新的無序區(qū)可能違反堆性質(zhì)，故應(yīng)將新的無序區(qū)再一次調(diào)整為堆。然后再進行(2)操作，直到無序區(qū)只有一個元素為止。此時排序結(jié)束

3.算法步驟：

(1)建堆，建堆是不斷調(diào)整堆的過程，從len/2處開始調(diào)整，一直到第一個節(jié)點，此處len是堆中元素的個數(shù)。建堆的過程是線性的過程，從len/2到0處一直調(diào)用調(diào)整堆的過程，相當(dāng)于o(h1)+o(h2)…+o(hlen/2) 其中h表示節(jié)點的深度，len/2表示節(jié)點的個數(shù)，這是一個求和的過程，結(jié)果是線性的O(n)。

(2)調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節(jié)點i和它的孩子節(jié)點left(i),right(i)，選出三者最大(或者最小)者，如果最大（小）值不是節(jié)點i而是它的一個孩子節(jié)點，那邊交互節(jié)點i和該節(jié)點，然后再調(diào)用調(diào)整堆過程，這是一個遞歸的過程。調(diào)整堆的過程時間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作，因為是沿著深度方向進行調(diào)整的。

(3)堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點取出(一般是與最后一個節(jié)點進行交換)，將前面len-1個節(jié)點繼續(xù)進行堆調(diào)整的過程，然后再將根節(jié)點取出，這樣一直到所有節(jié)點都取出。堆排序過程的時間復(fù)雜度是O(nlgn)。因為建堆的時間復(fù)雜度是O(n)（調(diào)用一次）；調(diào)整堆的時間復(fù)雜度是lgn，調(diào)用了n-1次，所以堆排序的時間復(fù)雜度是O(nlgn)

4.算法分析：

時間復(fù)雜度：O(N*logN)由于建初始堆所需的比較次數(shù)較多，所以堆排序不適合較少的

空間復(fù)雜度：堆排序是就地排序，空間復(fù)雜度O(1）

穩(wěn)定性：不穩(wěn)定的一種排序算法