// 參考《算法導(dǎo)論》中的偽代碼
public void HeapSort(int[] num) {
buildMaxHeap(num);
for(int i=num.length-1; i>0; i--) {
exchange(num, i, 0);
maxHeapify(num, 0, i);
}
}
public void buildMaxHeap(int[] num) {
for(int i=num.length/2-1; i>=0; i--) {
maxHeapify(num, i, num.length);
}
}
public void maxHeapify(int[] num, int index, int length) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if(left<length && num[left]>num[largest])
largest = left;
if(right<length && num[right]>num[largest])
largest = right;
if(largest!=index) {
exchange(num, index, largest);
maxHeapify(num, largest);
}
}
- maxHeapify() 維護(hù)最大堆性質(zhì)的關(guān)鍵悉尾，時(shí)間復(fù)雜度
)
- buildMaxHeap() 建堆带到，線性時(shí)間復(fù)雜度
- heapSort() 堆排序，時(shí)間復(fù)雜度
)
