1.首先将无序序列（长度为n的数组）调整为堆，以大根堆为例
2.将堆顶元素和堆尾进行交换
3.将剩余的n-1个元素调整为堆，重复2,3.直至整个数组有序。
public void heapSort(int a[]){
makeHeap(a,a.length);
for(int i=a.length-1;i>=0;i--){
swap(a,i,0);//将堆顶元素和末尾元素交换
heapAdjust(a, 0, i);//重新对堆进行调整，注意当前位置是从0开始进行调整
}
}
public void makeHeap(int a[],int n){
for(int i=n/2-1;i>=0;i--){//从n/2-1位置开始调整
heapAdjust(a,i,n);
}
}
/**
* @param a
* @param i
* @param j
*<p>Description: </p>
*/
private void swap(int[] a, int i, int j) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
/**
* @param a
* @param i
*<p>Description: 调整为大根堆，i为当前需要调整的节点</p>
*/
private void heapAdjust(int[] a, int i,int n) {
int j=i*2+1;//i的左子节点
while(j<n){
if(j+1<n && a[j]<a[j+1]){//如果右子节点为大的，则j指向右边
j++;
}
if(a[i]<a[j]){//j代表左右孩子中较大的那个
swap(a, i, j);
}
else{//i所在的子树以满足大根堆的定义
break;
}
i=j;//如果i,j交换后，j所在的子树可能不满足堆的定义，继续调整
j=i*2+1;
}
}
/**
* @param args
*<p>Description: </p>
*/
public static void main(String[] args) {
//int a[]={16,7,3,20,17,8};
int a[]={10,7,8,5,4,6,1};
HeapSort h=new HeapSort();
h.heapSort(a);
System.out.println(Arrays.toString(a));
}
