代码如下:
package com.package5;
public class HeapSort {
public static void main(String[] args) {
int[] arr={10,50,30,20,60,80,70,90,40};
System.out.println(arr.length/2);
HSort(arr); //进行排序
for(int i:arr)
System.out.println(i);
}
public static void HSort(int[] a){
int i;
for(i=a.length/2;i>0;i--){
MaxHeap(a,i,a.length); //构建大顶堆
}
for(i=a.length;i>1;i--){
swap(a,1,i);//将堆顶纪录和当前未排序子序列的最后一个纪录交换
MaxHeap(a, 1, i-1); //将a[]数组其余部分重新调整为大顶堆
}
}
public static void swap(int[] a, int i, int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void MaxHeap(int[] a, int s, int m) {
int temp,j;
temp=a[s];
for(j=2*s;j<=m;j*=2){ //沿关键字较大的孩子节点向下筛选
if(j<m&&a[j]<a[j+1]){ //!!!!!!!!报 java.lang.ArrayIndexOutOfBoundsException
++j; //j为关键字中较大纪录的下标
}
if(temp>=a[j]){
break;
}
a[s]=a[j];
s=j;
}
a[s]=temp; //插入数据
}
}