實作算法:
private static int leftChild(int i){
return 2*i+1;
}
private static <AnyType extends Comparable<? super AnyType>> void percDown(AnyType[] a,int i,int n){
int child;
AnyType tmp;
for(tmp=a[i];leftChild(i)<n;i=child){
child = leftChild(i);if(child != (n-1)&&a[child].compareTo(a[child+1])<0)
child++;
if(tmp.compareTo(a[child])<0)
a[i]=a[child];
else
break;
}
a[i]=tmp;
}
public static <AnyType extends Comparable<? super AnyType>> void heapsort(AnyType[] a){
for(int i=a.length/2;i>=0;i--)//buildHeap
percDown(a,i,a.length);
for(int i=a.length-1;i>0;i--){
swapReferences(a,0,i);//deleteMaxpercDown(a,0,i);
}
}
堆排序總是使用至少NlogN-O(N)次比較,輸入資料可以達到這個值
平均比較次數為2NlogN-O(N)