堆排序
堆的定義
n個元素的序列{k
k
…
kn)當且僅當滿足以下關系時
稱之為堆
![](http://tw.wingwit.com/Article/UploadFiles/201311/2013111515411012.gif)
![](http://tw.wingwit.com/Article/UploadFiles/201311/2013111515411001.gif)
若將和序列{k
k
…
kn)對應的一維數組(即以一維數組作此序列的存儲結構)看成是一個完全二叉樹
則堆的含義表明
完全二叉樹中所有非終端結點的值均不大於(或不小於)其左
右孩子結點的值
由此
若序列{k
k
…
kn)是堆
則堆頂元素(或完全二叉樹的根)必為序列中n個元素的最小值(或最大值)
這兩種堆分別稱之為小根堆和大根堆
堆排序(Heap Sort)
對一組待排序的關鍵字
首先是把它們按堆的定義排列成一個序列(稱為初建堆)
這就找到了最大關鍵字
然後將最大的關鍵字取出
用剩下的關鍵字再重建堆
便得到次大關鍵字
如此反復進行
直到把全部關鍵字排好序為止
堆排序算法
![](http://tw.wingwit.com/Article/UploadFiles/201311/2013111515411163.gif)
![](http://tw.wingwit.com/Article/UploadFiles/201311/2013111515411156.gif)
堆排序的平均時間復雜度接近於O(nlgn)
堆排序是一種不穩定的排序方法
From:http://tw.wingwit.com/Article/program/sjjg/201311/23797.html