顧名思義携龟，堆排序就是利用堆的性質(zhì)進(jìn)行的選擇排序
堆
堆是一棵順序存儲的完全二叉樹
其中每個根結(jié)點的關(guān)鍵字都不大于其孩子結(jié)點的關(guān)鍵字，這樣的堆稱為小根堆衡创。
其中每個根結(jié)點的關(guān)鍵字都不小于其孩子結(jié)點的關(guān)鍵字帝嗡，這樣的堆稱為大根堆。
完全二叉樹性質(zhì)
設(shè)當(dāng)前元素為數(shù)組的第i個元素璃氢，那么哟玷，
(1) 它的左孩子結(jié)點是：2i + 1;
(2) 它的右孩子結(jié)點是：2i + 2;
(3) 它的父結(jié)點是：(i-1) / 2;
(4)從下往上第一個非葉子節(jié)點：(length / 2) - 1;
算法思路
- 構(gòu)造初始堆(從由下至上第一個非葉子節(jié)點開始)；
- 交換首尾元素；
- 數(shù)組長度減一攻走，把剩下的元素重新調(diào)整為大根堆饺著；
- 重復(fù)2、3直至剩下最后一個元素結(jié)束讼渊。
構(gòu)造堆示意圖
構(gòu)造堆示意圖
排序過程
排序過程
C代碼
void heapAdjust(int *a, int parent, int length) {
int temp = a[parent];
int child = 2 * parent + 1;//先看左孩子
while (child < length) {
// 如果有右孩子且右孩子大于左孩子,那么選取右孩子
if (child + 1 < length && a[child + 1] > a[child]) {
child++;
}
// 如果父節(jié)點大于子節(jié)點則跳出循環(huán)
if (temp > a[child]) break;
// 父節(jié)點小于子節(jié)點，給父節(jié)點賦值
a[parent] = a[child];
// 把孩子節(jié)點變?yōu)楦腹?jié)點繼續(xù)往下遍歷比較
parent = child;
child = 2 * parent + 1;
}
// 遍歷完成
a[parent] = temp;
}
void heapSort(int a[], int length) {
// 初始化堆
for (int i = length / 2 - 1; i >=0; i--) {
heapAdjust(a, i, length);
}
// 進(jìn)行n-1次循環(huán)尊剔，完成排序
for (int i = length - 1; i > 0; i--) {
//交換首尾元素
int temp = a[i];
a[i] = a[0];
a[0] = temp;
// 調(diào)整堆
heapAdjust(a, 0, i);
}
}
復(fù)雜度
