1. 步骤

• 建立最大堆：

  • 从数组中间的位置，往前遍历每个元素，进行下沉操作。
  • 因为叶子节点占整个数量的一半，且叶子节点不需要下沉。

• 交换根节点元素：

  • 最大堆建立完成后，根节点元素最大，此时将其与末尾元素交换，则该元素有序。

• 再次进行下沉操作：

  • 此时根节点为原来的末尾元素，对该元素进行下沉操作。
  • 即在此建立最大堆。

• 重复以上步骤，直到堆中只剩下一个元素。

2. 方法

2.1 获取左孩子的索引

/**
* 计算左孩子的index
*
* @param k 父亲节点的index
* @return
*/
private int leftChild(int k) {
    return 2 * k + 1;
}

2.2 下沉操作

• 因为每次都会将最大的元素放到最后，所以最后的元素是排好序的因此需要n来指定最后一个元素的位置，不参与下沉操作。
• 让j指向左右孩子中较大的元素，使用数组索引的时候注意越界问题。
• 如果父亲大于最大的孩子，则无需下沉，结束循环。
• 否则交换节点

/**
* @param arr 原始数组
* @param k   要下沉的节点的编号
* @param n   最后的元素的index，闭区间
*/
private void siftDown(int[] arr, int k, int n) {
    while (leftChild(k) <= n) {
        int j = leftChild(k);
        if (j + 1 <= n && arr[j] < arr[j + 1])
            j++;
        if (arr[k] >= arr[j])
            break;
        swap(arr, k, j);
        k = j;
    }
}

3. 代码

public class HeapSort{
    public void sort(int[] arr) {
        int n = arr.length - 1;
        // 建立最大堆
        for (int i = n / 2; i >= 0; i--) {
            siftDown(arr, i, n);
        }
        // 交换首尾元素并下沉
        while (n > 0) {
            swap(arr, 0, n--);
            siftDown(arr, 0, n);
        }
    }
    private int leftChild(int k) {
        return 2 * k + 1;
    }
    private void siftDown(int[] arr, int k, int n) {
        while (leftChild(k) <= n) {
            int j = leftChild(k);
            if (j + 1 <= n && arr[j] < arr[j + 1])
                j++;
            if (arr[k] >= arr[j])
                break;
            swap(arr, k, j);
            k = j;
        }
    }
}