堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，其最大、平均、最小时间复杂度都为O(nlogn)，空间复杂度为O(1)。
在将堆排序前我们先讲讲堆，堆是一颗具有以下性质的完全二叉树，它的每个父节点值都大于或小于左右孩子节点值，如果是大于则是大顶堆，小于则是小顶堆，用公式描述如下：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
image
如果我们将大顶堆的节点映射为一个数组的话则是下面这个样子：
image
排序原理
堆排序的步骤主要分为以下几步：
1.将无序序列（数组或集合）构建成一个大顶堆或小顶堆，一般升序用大顶堆，降序用小顶堆
2.交换根节点arr[0]与末尾节点arr[arr.length - 1]，此时末尾节点即为最大值
3.排除末尾节点，将前面的arr[0]至arr[arr.length - 2]的节点重新构建最大堆
4.重复步骤2，3的操作
用动画描述的话就是下面这个样子：
image
代码实现
public class HeapSort {
public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64 };
int arrayLength = a.length;
// 循环建堆
for (int i = 0; i < arrayLength - 1; i++) {
// 建堆
buildMaxHeap(a, arrayLength - 1 - i);
// 交换堆顶和最后一个元素
swap(a, 0, arrayLength - 1 - i);
}
System.out.println(Arrays.toString(a));
}
// 对data数组从0到lastIndex建大顶堆
public static void buildMaxHeap(int[] data, int lastIndex) {
// 从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存正在判断的节点
int k = i;
// 如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
if (biggerIndex < lastIndex) {
// 若果右子节点的值较大
if (data[biggerIndex] < data[biggerIndex + 1]) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大的子节点的值
if (data[k] < data[biggerIndex]) {
// 交换他们
swap(data, k, biggerIndex);
// 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
// 交换
private static void swap(int[] data, int i, int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
参考：
