堆排序算法的讲解及Java版实现

目录

• 概述
• 堆的实现
• 堆排序的实现
• Java版实现示例

概述

堆排序（Heap Sort）是一种选择排序，它的平均时间复杂度为 O(nlogn)，实用性较高。

堆排序的基本思想是：

1. 将待排序的序列构建成一个大顶堆（或小顶堆）；
2. 此时，整个序列的最大值（或最小值）就是堆顶的根节点；
3. 将其与末尾元素进行交换，此时末尾就为最大值（或最小值）；
4. 然后将剩下的 n-1 个元素重新构建成一个堆，继续进行交换操作，直到整个序列有序。

堆的实现

在堆排序中，我们需要用到堆的数据结构。堆实际上是一个完全二叉树，分为大顶堆和小顶堆。

• 大顶堆：每个节点的值都大于或等于其左右子节点的值。
• 小顶堆：每个节点的值都小于或等于其左右子节点的值。

实现堆的时候，我们可以用一维数组来表示。假设数组的下标从 1 开始，那么对于下标为 i 的节点：

• 左节点索引为 i * 2；
• 右节点索引为 i * 2 + 1；
• 父节点索引为 i / 2。

堆排序的实现

堆排序算法的思路分成两个主要的过程：

1. 将序列构建成堆；
2. 将堆顶元素与末尾元素交换，并且重新将剩下的元素构建成堆，重复操作直到整个序列有序。

具体实现过程：

1. 构建大根堆（升序排序）或小根堆（降序排序），即使每个非叶子节点的值都大于或等于（或小于或等于）其子节点的值。

   1. 从后向前遍历数组，对于当前索引为 i 的元素：
      1. 将其与左右子节点中较大的那一个交换位置，直到满足堆的定义。
   2. 当整个数组都构建完毕后，堆顶元素就是最大值（或最小值）。

2. 将堆顶元素与末尾元素进行交换，并且重新将其余元素构建成堆。

   1. 将堆顶元素与末尾元素互换位置，此时末尾就是数组中的最大值（或最小值）。
   2. 对于前面 n-1 个元素重新进行构建堆的操作。

重复上述步骤，直到整个序列有序。

Java版实现示例

public class HeapSort {
    public static void sort(int[] arr) {
        // 构建大根堆
        buildHeap(arr, arr.length - 1);
        // 从后向前遍历数组，依次将堆顶元素与末尾元素交换，并重新构建堆
        for (int i = arr.length - 1; i >= 1; i--) {
            swap(arr, 0, i); // 将堆顶元素与末尾元素交换位置
            heapify(arr, 0, i - 1); // 重新构建堆
        }
    }

    // 构建大根堆
    private static void buildHeap(int[] arr, int end) {
        for (int i = (end - 1) / 2; i >= 0; i--) {
            heapify(arr, i, end);
        }
    }

    // 以节点 i 为根的子树重新构建大根堆
    private static void heapify(int[] arr, int i, int end) {
        int left = i * 2 + 1; // 左子节点索引
        int right = i * 2 + 2; // 右子节点索引
        int max = i; // 堆的最大节点索引
        // 找到堆中最大的节点
        if (left <= end && arr[left] > arr[max]) {
            max = left;
        }
        if (right <= end && arr[right] > arr[max]) {
            max = right;
        }
        if (max != i) { // 若最大节点不是当前节点，就将其交换位置
            swap(arr, i, max);
            heapify(arr, max, end); // 对以 max 为根的子树进行堆化操作
        }
    }

    // 交换数组中下标为 i 和 j 的元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

示例一：对数组 {7, 6, 5, 4, 3, 2, 1} 进行堆排序（升序排列）

int[] arr = {7, 6, 5, 4, 3, 2, 1};
HeapSort.sort(arr);
System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7]

示例二：对数组 {-1, 0, 3, 5, 2, 1} 进行堆排序（降序排列）

int[] arr = {-1, 0, 3, 5, 2, 1};
HeapSort.sort(arr);
System.out.println(Arrays.toString(arr)); // 输出 [5, 3, 2, 1, 0, -1]

以上就是堆排序算法的讲解及Java版实现的完整攻略。