java堆排序代码

Python015

java堆排序代码,第1张

//从a[index]到a[len]除了a[index]外其它元素满足一个堆，把a[index]调整到合适位置

//这个堆满足父节点>孩子结点，且要保证2*index能取到index的左孩子，

public static void adjustHeap(int[] a,int index,int len){

int scn=a[index]

for(int i=2*indexi<=mi*=2){

if(i<m&&a[i]<a[i+1])i+=1

if(!a[i]>scn)break

a[index]=a[i]index=i

}

a[index]=scn

}

//数组a从a[1]开始存放元素，如果想从a[0]开始则要调整adjustHeap代码，以便满足完全二叉树

//性质，代码未经测试

public static void heapSort(int[] a){

for(int i=(a.length-1)/2i>0i--)

adjustHeap(a,i,a.length-1)

int tmp

for(int i=a.length-1i>1i--){

tmp=a[i]

a[i]=a[1]

a[1]=tmp

adjustHeap(a,1,i-1)

}

}

一般情况下，快速排序效率要高于堆排序。因为堆排序的常数较大（不过也是1～2之间吧）。

快速排序的平均时间复杂度是O(1.39nlogn)。一般来说，除非有需要绝对保证不能出现O(n^2)的要求，不使用堆排。

堆排序需要有效的随机存取。