public class HeapSort { static void HeapAdjust(int H[],int s,int n){//使H[s...m]称为一个大顶堆 int rc=H[s]; int j; for(j=2*s;j<=n;j=j*2){ if(j<n-1&&H[j]<H[j+1]) ++j;//j为父节点的最大孩子 if(rc>=H[j]) break;//rc应该掺入在j的父位置上 H[s]=H[j];//j上移 s=j; } H[s]=rc; }
static void Heap_Sort(int H[]){ int n=H.length; for(int i=n/2;i>0;i--){ HeapAdjust(H,i,n); }// for(int k=n-1;k>1;k--){ int temp=H[1]; H[1]=H[k]; H[k]=temp;//将堆顶记录和 当前未经排序子序列中最后一个记录交换。 HeapAdjust(H,1,k-1); } } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int A[]={0,3,5,9,2,7}; Heap_Sort(A); for(int i=0;i<A.length;i++) System.out.print(A[i]); } } |