堆排序
1、堆排序原理
堆排序是利用到了堆这种数据结构，我们首先回顾一下二叉堆的特性：
- 最大堆的堆顶是整个堆中的最大元素。
- 最小堆的堆顶是整个堆中的最小元素。
以最大堆为例，如果删除一个最大堆的堆顶（并不是完全删除，而是跟末尾的节点交换位置），经过自我调整，第2大的元素就会被交换上来，成为最大堆的新堆顶。如下图所示：
在删除值为10的堆顶节点后，经过调整，值为9的新节点就会顶替上来；在删除值为9的堆顶节点后，经过调整，值为8的新节点就会顶替上来……
由于二叉堆的这个特性，每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。
而二叉堆实际是存储在数组中的，堆排序过后数组中的元素排列如下：
综上，堆排序的步骤为：
- 把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
- 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。
2、堆排序的代码实现
堆排序的代码如下如下（升序排列）：
/**
* “下沉”调整
* @param array 待调整的堆
* @param parentIndex 要“下沉”的父节点
* @param length 堆的有效大小
*/
public static void downAdjust(int[] array, int parentIndex,int length) {
// temp 保存父节点值，用于最后的赋值
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
// 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
if (childIndex + 1 < length && array[childIndex + 1] >array[childIndex]) {
childIndex++;
}
// 如果父节点大于任何一个孩子的值，则直接跳出
if (temp >= array[childIndex])
break;
//无须真正交换，单向赋值即可
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}
/**
* 堆排序（升序）
* @param array 待调整的堆
*/
public static void heapSort(int[] array) {
// 1. 把无序数组构建成最大堆
for (int i = (array.length-2)/2; i >= 0; i--) {
downAdjust(array, i, array.length);
}
System.out.println(Arrays.toString(array));
// 2. 循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶
for (int i = array.length - 1; i > 0; i--) {
// 最后1个元素和第1个元素进行交换
int temp = array[i];
array[i] = array[0];
array[0] = temp;
// “下沉”调整最大堆
downAdjust(array, 0, i);
}
