《Java 实现堆排序：深入理解与代码剖析》

2024-11-08 07:18:24

一、引言

排序算法在计算机科学领域中占据着重要的地位，它们能够帮助我们高效地组织和处理数据。堆排序作为一种高效的排序算法，基于二叉堆的数据结构，具有时间复杂度相对较低且性能稳定的优点。在这篇博客中，我们将详细解析一段用 Java 实现堆排序的代码，帮助大家深入理解堆排序的原理及实现细节。

二、堆排序原理

堆排序的核心思想是利用二叉堆这种数据结构的特性来进行排序。二叉堆分为大顶堆和小顶堆，在堆排序中通常使用大顶堆。大顶堆要求每个节点的值都不小于它的子节点的值。

堆排序主要分为两个步骤：

首先，将给定的数组构建成一个大顶堆。通过从最后一个非叶子节点开始，依次向上调整每个节点及其子节点的关系，使得整个数组满足大顶堆的性质。
然后，将堆顶元素（即数组中的最大值）与堆底元素交换位置，此时数组的末尾就放置了已排序好的最大值。接着，对除堆底元素外的剩余数组元素再次构建大顶堆，重复这个过程，直到整个数组都被排序完成。

三、代码分析

1. 代码整体结构

以下是我们要详细分析的 Java 堆排序代码：

package 排序;

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        //第一步，构建大顶堆
        for (int p = arr.length - 1; p >= 0; p--) {
            adjust(arr, p, arr.length);
        }
        //第二步 堆顶和堆底元素进行交换，除堆底外剩余元素继续构建大顶堆
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjust(arr, 0, i);
        }

        System.out.println(Arrays.toString(arr));
        //重复这样的操作
    }

    //堆的维护
    public static void adjust(int[] arr, int parent, int length) {
        //定义左孩子
        int child = 2 * parent + 1;
        while (child < length) {
            //定义右孩子
            int rchild = child + 1;
            if (rchild < length && arr[rchild] > arr[child]) {
                child++;
            }
            //child指向左右孩子的最大值
            //父子节点进行比较
            if (arr[parent] < arr[child]) {
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
                //parent指向child,child继续指向其左右孩子最大值
                parent = child;
                child = 2 * child + 1;
            } else {
                break;
            }
        }
    }
}

2. `main`方法

在 main 方法中，我们首先定义了一个整数数组 arr，并初始化它的值为 {5, 7, 4, 2, 0, 3, 1, 6}。这就是我们要进行排序的原始数组。

int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};

接下来，执行堆排序的两个主要步骤：

构建大顶堆：
通过一个循环，从数组的最后一个非叶子节点开始，依次调用 adjust 函数来调整每个节点及其子节点的关系，使得整个数组逐步构建成大顶堆。循环条件 for (int p = arr.length - 1; p >= 0; p--) 确保我们从最后一个非叶子节点（即 arr.length / 2 - 1 位置的节点）开始，一直到数组的第一个节点（索引为 0），逐个对节点进行调整。

for (int p = arr.length - 1; p >= 0; p--) {
    adjust(arr, p, arr.length);
}

交换与重新构建大顶堆：
在完成大顶堆的构建后，我们通过另一个循环，从数组的末尾开始，将堆顶元素（即数组中的最大值）与堆底元素交换位置。然后，调用 adjust 函数对除堆底元素外的剩余数组元素再次构建大顶堆。这个过程不断重复，直到整个数组都被排序完成。循环条件 for (int i = arr.length - 1; i >= 0; i--) 控制着每次交换和重新构建大顶堆的操作。

for (int i = arr.length - 1; i >= 0; i--) {
    int temp = arr[i];
    arr[i] = arr[0];
    arr[0] = temp;
    adjust(arr, 0, i);
}

最后，通过 Arrays.toString 方法将排序后的数组以字符串的形式输出到控制台，以便我们直观地查看排序的结果。

System.out.println(Arrays.toString(arr));

3. `adjust` 方法

adjust 方法是实现堆维护和调整的核心函数，用于确保在给定的节点及其子节点范围内，满足大顶堆的性质。

初始化左孩子节点：
首先，通过公式 int child = 2 * parent + 1 计算出给定父节点 parent 的左孩子节点的索引。

int child = 2 * parent + 1;

寻找左右孩子中的最大值：
接着，定义右孩子节点的索引为 rchild = child + 1，并通过条件判断 if (rchild < length && arr[rchild] > arr[child])，如果右孩子存在（即 rchild < length）且右孩子的值大于左孩子的值，就将 child 指针指向右孩子，使得 child 始终指向左右孩子中的最大值。

int rchild = child + 1;
if (rchild < length && arr[rchild] > arr[child]) {
    child++;
}

父子节点比较与交换：
然后，将父节点 parent 的值与 child 指向的孩子节点（即左右孩子中的最大值）的值进行比较。如果父节点的值小于孩子节点的值，就通过临时变量 temp 进行交换操作，使得较大的值向上移动，满足大顶堆的性质。同时，更新 parent 和 child 的值，以便继续向下检查和调整子节点，确保整个子树都满足大顶堆的性质。

if (arr[parent] < arr[child]) {
    int temp = arr[parent];
    arr[parent] = arr[child];
    arr[child] = temp;
    //parent指向child,child继续指向其左右孩子最大值
    parent = child;
    child = 2 * child + 1;
} else {
    break;
}

如果父节点的值不小于孩子节点的值，说明在当前节点及其子节点范围内已经满足大顶堆的性质，就可以停止调整，通过 break 语句跳出循环。

四、测试结果

当我们运行上述代码时，对于给定的初始数组 {5, 7, 4, 2, 0, 3, 1, 6}，经过堆排序后，控制台会输出排序后的数组，其结果应该是 {0, 1, 2, 3, 4, 5, 6, 7}。

码农公寓