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