() 堆排序是對樹型選擇排序的改進克服了樹型選擇排序的缺點其定義在前面已多次談到請參見上面四應用題的題和題()篩選是堆排序的基礎算法由於堆可以看作具有n個結點的完全二叉樹建堆過程是從待排序序列第一個非終端結點ën/û開始直到根結點進行篩選的過程堆建成後即可選得一個關鍵字最大或最小的記錄然後堆頂元素與序列中最後一個元素交換再將序列中前n記錄重新調整為堆可選得一個關鍵字次大或次小的記錄依次類推則可得到元素的有序序列
() void Sift(RecType R[]int iint m)
{ //假設R[i+m]中各元素滿足堆的定義本算法調整R[i]使序列R[im]中各元素滿足堆的性質
R[]=R[i];
for(j=*i; j<=m; j*=)
{ if(j<m && R[j]key<R[j+l]key) j++; //建大根堆
if(R[]key<R[j]key) { R[i]=R[j]; i=j;} else break;
}//for
R[i]=R[];
}//Sift
void HeapSort(RecType R[]int n)
{ //對記錄序列R[n]進行堆排序
for(i=n/;i>;i) Sift(Rin);
for(i=n;i>;i){ R[]<>R[i]; Sift(Ri);}//for
}//HeapSort
()堆排序的時間主要由建堆和篩選兩部分時間開銷構成對深度為h的堆篩選所需進行的關鍵字比較的次數至多為(h－)對n個關鍵字建成深度為h(=ëlognû+)的堆所需進行的關鍵字比較的次數至多C (n)它滿足下式
調整堆頂n次總共進行的關鍵字比較的次數不超過
因此堆排序的時間復雜度為O(nlogn)
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23180.html
