掌握Rust堆排序（从零开始学Rust堆排序算法与数据结构）

什么是堆排序？

堆排序（Heap Sort）是一种基于堆这种数据结构的比较类排序算法。它的核心思想是：

1. 将待排序数组构建成一个最大堆（父节点值 ≥ 子节点值）；
2. 将堆顶（最大值）与末尾元素交换；
3. 缩小堆的范围（排除已排好的最大值），重新调整堆；
4. 重复步骤2-3，直到所有元素有序。

堆排序的时间复杂度为 O(n log n)，空间复杂度为 O(1)，是一种原地排序算法。

Rust 中如何实现堆排序？

在 Rust 中，我们可以不依赖外部库，仅用标准语法实现堆排序。关键在于两个函数：

• heapify：维护堆的性质（即父节点 ≥ 子节点）；
• heap_sort：主排序逻辑。

第一步：实现 heapify 函数

这个函数确保以某个节点为根的子树满足最大堆的性质。

fn heapify(arr: &mut [i32], n: usize, i: usize) {    let mut largest = i; // 初始化最大值为根    let left = 2 * i + 1; // 左子节点    let right = 2 * i + 2; // 右子节点    // 如果左子节点存在且大于根    if left < n && arr[left] > arr[largest] {        largest = left;    }    // 如果右子节点存在且大于当前最大值    if right < n && arr[right] > arr[largest] {        largest = right;    }    // 如果最大值不是根，则交换并继续堆化    if largest != i {        arr.swap(i, largest);        heapify(arr, n, largest); // 递归堆化受影响的子树    }}

第二步：实现 heap_sort 主函数

先构建最大堆，再逐个提取最大值放到末尾。

fn heap_sort(arr: &mut [i32]) {    let n = arr.len();    // 构建最大堆（从最后一个非叶子节点开始）    for i in (0..=n / 2).rev() {        heapify(arr, n, i);    }    // 逐个将堆顶（最大值）移到末尾    for i in (1..n).rev() {        arr.swap(0, i); // 将最大值放到末尾        heapify(arr, i, 0); // 对剩余元素重新堆化    }}

第三步：测试你的堆排序

fn main() {    let mut data = [12, 11, 13, 5, 6, 7];    println!("排序前: {:?}", data);    heap_sort(&mut data);    println!("排序后: {:?}", data);}

运行结果：

排序前: [12, 11, 13, 5, 6, 7]排序后: [5, 6, 7, 11, 12, 13]

为什么选择 Rust 实现堆排序？

Rust 的内存安全性和零成本抽象使其成为实现底层算法的理想语言。通过本教程，你不仅学会了Rust算法教程中的经典案例，也深入理解了数据结构Rust的实际应用。

小结

堆排序虽然不如快速排序在平均情况下的性能好，但它具有稳定的 O(n log n) 时间复杂度，且不需要额外内存。通过本教程，你已经掌握了如何在 Rust 中从零实现堆排序。希望这篇关于Rust堆排序的详细指南能帮助你在算法学习之路上更进一步！

关键词回顾：Rust堆排序、堆排序算法、Rust算法教程、数据结构Rust。