public int[]heapSort(int[] A, int n) {
//循环建堆
for(int i=0;i
buildMaxHeap(A,n-1-i); //建堆 n-1-i为最后一个元素的下标
swap(A,0,n-1-i); //交换堆顶和最后一个元素
}
return A;
}
private void swap(int[] A, int i, intj) {
int tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
//对A数组从下标0到下标lastIndex建大顶堆
private void buildMaxHeap(int[] A, intlastIndex) {
//从lastIndex处节点（最后一个节点）的父节点开始
for(int i=(lastIndex-1)/2;i>=0;i--){
int k=i; //k保存正在判断的节点
//如果当前k节点的子节点存在
while(k*2+1<=lastIndex){
int biggerIndex=2*k+1; //k节点的左子节点的索引为2K+1
//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if(biggerIndex
//若果右子节点的值较大
if(A[biggerIndex]
biggerIndex++; //biggerIndex总是记录较大子节点的索引
}
}
if(A[k]
swap(A,k,biggerIndex); //交换他们
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else
break;
} //while
}//for
}// buildMaxHeap方法
