堆排序(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)整為堆。然后再進(jìn)行(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的操作瘫镇，因為是沿著深度方向進(jìn)行調(diào)整的。
(3)堆排序：堆排序是利用上面的兩個過程來進(jìn)行的答姥。首先是根據(jù)元素構(gòu)建堆铣除。然后將堆的根節(jié)點取出(一般是與最后一個節(jié)點進(jìn)行交換)，將前面len-1個節(jié)點繼續(xù)進(jìn)行堆調(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)定的一種排序算法
