Java 数据结构之堆排序（HeapSort）详解及实例

什么是堆排序

堆排序是一种树形选择排序，它的特点是不需要建立临时数组存放已排序的元素，而是直接在原数组上进行排序，因此空间复杂度比较小，时间复杂度为 $O(nlogn)$。

堆排序中需要用到的数据结构是堆，它是一种特殊的二叉树。堆分为大根堆和小根堆，大根堆满足任何一个非叶子节点的值都不小于其子节点的值，小根堆则相反，任何一个非叶子节点的值都不大于其子节点的值。

堆排序的算法步骤

1. 将待排序的序列构建成一个大根堆或小根堆。
2. 将堆顶元素（最大值或最小值）与末尾元素交换，从而将最大值或最小值放到了末尾。
3. 将剩余的序列重新构建成一个堆。
4. 重复步骤 2 和步骤 3，直到整个序列排序完成。

Java 代码实现

我们以使用大根堆进行从小到大排序为例，以下为 Java 代码实现：

public static void heapSort(int[] arr) {
    int len = arr.length;

    // 构建大根堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, len);
    }

    // 交换堆顶元素到末尾
    for (int i = len - 1; i > 0; i--) {
        swap(arr, 0, i);
        adjustHeap(arr, 0, i);
    }
}

private static void adjustHeap(int[] arr, int i, int len) {
    int temp = arr[i];
    for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
        if (k + 1 < len && arr[k] < arr[k + 1]) {
            k++;
        }
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    arr[i] = temp;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

其中， adjustHeap 方法是用于调整堆的方法， swap 方法是交换元素的方法。

示例说明

以下为两个示例说明：

示例一

对数组 [4, 6, 8, 5, 9] 进行从小到大排序。

构建大根堆：

    4
  /   \
6      8

/ \
5 9

第一次交换堆顶元素到末尾：

    9
  /   \
6      8

/ \
5 4

重新构建堆：

    6
  /   \
5      8

/ \
4 9

第二次交换堆顶元素到末尾：

    8
  /   \
5      6

/ \
4 9

重新构建堆：

    6
  /   \
5      4

第三次交换堆顶元素到末尾：

    5
  /   \
4      6

重新构建堆：

    4

排序完成，数组变成了 [4, 5, 6, 8, 9]。

示例二

对数组 [8, 7, 6, 5, 4, 3, 2, 1] 进行从小到大排序。

构建大根堆：

    8
  /   \
7      6

/ \ / \
5 4 3 2
/
1

第一次交换堆顶元素到末尾：

    1
  /   \
7      6

/ \ / \
5 4 3 2
/
8

重新构建堆：

    7
  /   \
5      6

/ \ / \
1 4 3 2
/
8

第二次交换堆顶元素到末尾：

    2
  /   \
5      6

/ \ / \
1 4 3 7
/
8

重新构建堆：

    6
  /   \
5      4

/ \ / \
1 2 3 7
/
8

第三次交换堆顶元素到末尾：

    3
  /   \
5      4

/ \ / \
1 2 6 7
/
8

重新构建堆：

    5
  /   \
1      4

/ \ / \
3 2 6 7
/
8

第四次交换堆顶元素到末尾：

    4
  /   \
1      2

/ \ / \
3 5 6 7
/
8

重新构建堆：

    3
  /   \
1      2

/ \ / \
4 5 6 7
/
8

第五次交换堆顶元素到末尾：

    2
  /   \
1      3

/ \ / \
4 5 6 7
/
8

重新构建堆：

    1
  /   \
4      3

/ \ / \
2 5 6 7
/
8

第六次交换堆顶元素到末尾：

    1
  /   \
2      3

/ \ / \
4 5 6 7
/
8

重新构建堆：

    2
  /   \
4      3

/ \ / \
5 1 6 7
/
8

第七次交换堆顶元素到末尾：

    1
  /   \
4      3

/ \ / \
5 2 6 7
/
8

重新构建堆：

    4
  /   \
5      3

/ \ / \
1 2 6 7
/
8

排序完成，数组变成了 [1, 2, 3, 4, 5, 6, 7, 8]。

总结

堆排序相对于其他排序算法来说，其代码实现比较简单，空间复杂度比较小，时间复杂度较优秀。但是由于堆排序的算法思路和数组中数据的存储方式不同于其他排序算法，所以有时候可能会有一些不易于理解的地方。