堆排序是一種選擇排序。是不穩定的排序方法。時間複雜度為O(nlog2n)。特點是在排序過程中，將排序陣列看成是一棵完全二叉樹的順序儲存結構，利用完全二叉樹中雙親節點和孩子節點之間的內在關係，在當前無序區中選擇關鍵字最大(或最小)的記錄。

其基本思想是

1、將要排序的陣列建立為一個大根堆。大根堆的堆頂元素就是這個堆中最大的元素。

2、將大根堆的堆頂元素和無序區最後一個元素交換，並將無序區最後一個位置例入有序區，然後將新的無序區調整為大根堆。

3、重複操作，無序區在遞減，有序區在遞增。

初始時，整個陣列為無序區，第一次交換後無序區減一，有序區增一。

每一次交換，都是大根堆的堆頂元素插入有序區，所以有序區保持是有序的。

P.S.

大根堆和小根堆

堆：是一顆完全二叉樹。

大根堆：所有節點的子節點比其自身小的堆

小根堆：所有節點的子節點比其自身大的堆