数据结构与算法：Java实现堆排序案例

原创墨蓝 2024-10-18 14:45 32阅读 0赞

堆排序是一种基于比较的排序算法，其主要思想是将待排序的序列构造成一个大顶堆（或小顶堆），然后通过调整来使堆满足性质，这样取出堆顶元素就是当前最小值，然后继续调整以保证剩余元素的有序。以下是Java实现堆排序的案例：

```java
// 定义节点类，包含数据和下一个节点
class Node {
    int data;
    Node next;

// 构造函数
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 堆排序实现
public class HeapSort {
    // 将数组构造成大顶堆
    void heapify(Node root, int index) {
        // 获取当前节点的下标
        int childIndex = 2 * index + 1;

// 如果孩子索引在有效范围内，且其值小于父节点，就交换位置
        if (childIndex < root.next.data && childIndex > index) {
            swap(root, childIndex);
            heapify(root, childIndex);
        }
    }

// 交换两个节点的位置
    void swap(Node node1, Node node2) {
        int temp = node1.data;
        node1.data = node2.data;
        node2.data = temp;
    }

// 堆排序函数，对输入的数组进行排序
    public void heapSort(Node arr[]) {
        int n = arr.length;

// 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, i);
        }

// 逐个将最大值放到末尾
        for (int i = n - 1; i >= 0; i--) {
            swap(arr, 0, i + 1);
            heapify(arr, 0, i + 1);
        }
    }
}
```

上述代码首先定义了一个堆节点类，然后实现了大顶堆的构建和调整，以及堆排序的全过程。最后可以通过创建数组并调用`heapSort`方法来进行实际排序操作。