堆积排序()是指利用堆积树（堆）这种数据结构所设计的一种排序算法堆排序算法java，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O(1)堆排序算法java， 最坏时间复杂度为O() ，堆排序的堆序的平均性能较接近于最坏性能。
中心思想是在使用数组存储的完全二叉树内从下往上每次构造大顶堆或者小顶堆，然后将找出来的堆顶数字放到数组结尾，剩下数组继续构造堆结构。
主要是参考了网上比较常见的两种堆排序的java实现，自己加了一些注释
实现1
采用递归，每次父节点与最大子节点交换后递归构造被交换后的子树
<pre class="prism-token token language-javascript">` public static void heapSort(int[] array) {
if (array == null || array.length = 1; i--) {
exchangeElements(array, 0, i);
maxHeap(array, i, 0);
System.out.println("maxHeap " + Arrays.toString(array) + " i is "
+ i);
}
}<p>
private static void buildMaxHeap(int[] array) {
if (array == null || array.length = 0; i--) {
maxHeap(array, array.length, i);
}
}
private static void maxHeap(int[] array, int heapSize, int index) {
// 堆编号x ，数组编号index ，a=index+1;
// 所以左节点数组编号=2a-1=index * 2 + 1
// 右节点数组编号=2a+1-1=index * 2 + 2
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (index != largest) {
exchangeElements(array, index, largest);// 将子节点更大的值换到父节点
System.out.println("maxHeap " + Arrays.toString(array)
+ " index is " + index + " left is " + left + " right is "
+ right + " largest is " + largest + " heapSize is "
+ heapSize);
maxHeap(array, heapSize, largest);// 原有父节点的值放到了子节点后可能不满足堆的性质，需要调整修改后largest节点对应的子树
}
}
private static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}`</pre></p>复制
实现2
while循环堆排序算法java 堆排序算法的java实现，同样父子节点交换后记录被换过的子节点位置，使用while (2 * k + 1