堆排序应该是几大排序里最复杂的一个了，具体来看：
首先涉及了一个构建大顶堆的方法(升序排序使用大顶堆)：
/**
* 功能：将i对应的非叶子节点为根的树调整成大顶堆
* 举例 int[] arr = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => {4, 9, 8, 5, 6}
* 如果我们再次调用adjustHeap，传入的是i = 0 => {9, 6, 8, 5, 4}
* @param arr 待调整的数组
* @param i 表示非叶子结点在数组中的索引
* @param length 表示对多少个元素继续调整，len在逐渐减少
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i]; //先取出当前元素的值，保存在临时变量
//开始调整
//说明
//1. k = i * 2 + 1, k是i结点的左子结点
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) { //说明左子节点小于右子节点
k++; //k指向右子结点，至此k指向了左右结点里较大的
}
if (arr[k] > temp) { //如果子节点大于父节点
arr[i] = arr[k]; //把较大的值赋给当前结点
i = k; //让i指向k，继续循环比较
} else {
break;
}
}
//当for循环结束后，已经将以i为父节点的最大值放在了最顶
arr[i] = temp; //将temp放到调整后的位置
}
理解这个方法的关键在于，堆排序寻找非叶子结点，是从下到上，从左到右寻找非叶子结点的，第一次传入的索引i，在二叉树中的位置必然是相对靠下的，此时for循环是没作用的。但随着传入的i变化(非叶子结点的逐渐变高)，需要对于当前节点高度以下的子树，都已经实现了大顶堆，只是加入当前结点后，这个子树需要重新调整，重新形成新的大顶堆，这时候for循环就开始起作用了，可能会经过多次比较，最终找到当前节点应该放置的位置。这个方法每次执行完，索引i对应的二叉树以下的部分(子树)都实现了大顶堆。
对于方法：
public static void heapSort(int arr[]) {
int temp;
System.out.println("堆排序");
//将无序序列构建成一个堆，根据升序降序需求选择大顶堆和小顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
//将堆顶元素与末尾元素交换，将最大元素沉到数组末端
//重新调整结构，使其满足堆定义，然后继续交换堆顶元素与末尾元素，反复执行，直到整个序列有序
for (int i = arr.length - 1; i > 0; i--) {
//交换
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, i);
}
System.out.println(Arrays.toString(arr));
}
第一个for循环是根据传入i的不同，经过几次循环后实现了全部二叉树的大顶堆。第二个for循环根据在第一次执行时，可以确定的是二叉树的根结点放置的是所有元素中最大的，其他二叉树元素大小关系都不能确定，于是先将这个最大的数放置到数组的最后，也就是对应的二叉树的最低的位置，将最低的元素放到根结点的位置。此时除了根结点，显然其他子树都已经实现了大顶堆，于是剩下的工作就是在不断减小数组长度的同时，将整个数组对应的二叉树重构成大顶堆的形式了。
原文：https://www.cnblogs.com/LostSecretGarden/p/14730754.html