掌握Rust排序算法（从冒泡到快排的完整指南）

为什么学习排序算法？

排序是计算机科学中最基础的操作之一。它不仅用于数据整理，还广泛应用于搜索、数据库优化、图形处理等领域。Rust作为一门内存安全且高性能的系统编程语言，非常适合用来实现高效且安全的排序算法。

1. 冒泡排序（Bubble Sort）

冒泡排序Rust 实现非常直观：重复遍历列表，比较相邻元素并交换顺序错误的项，直到整个列表有序。

fn bubble_sort(arr: &mut [i32]) {    let n = arr.len();    for i in 0..n {        for j in 0..n - 1 - i {            if arr[j] > arr[j + 1] {                arr.swap(j, j + 1);            }        }    }}fn main() {    let mut numbers = [64, 34, 25, 12, 22, 11, 90];    println!("排序前: {:?}", numbers);    bubble_sort(&mut numbers);    println!("排序后: {:?}", numbers);}

这段代码的时间复杂度为 O(n²)，适合教学但不适用于大规模数据。

2. 快速排序（Quick Sort）

如果你追求效率，快速排序Rust 实现是一个更优选择。它采用“分治法”策略：选择一个基准值（pivot），将数组分为小于和大于基准的两部分，然后递归排序子数组。

fn quick_sort(arr: &mut [i32]) {    if arr.len() <= 1 {        return;    }    let pivot_index = partition(arr);    {        let (left, right) = arr.split_at_mut(pivot_index);        quick_sort(left);        quick_sort(&mut right[1..]);    }}fn partition(arr: &mut [i32]) -> usize {    let len = arr.len();    let pivot = arr[len - 1];    let mut i = 0;    for j in 0..len - 1 {        if arr[j] <= pivot {            arr.swap(i, j);            i += 1;        }    }    arr.swap(i, len - 1);    i}fn main() {    let mut numbers = [64, 34, 25, 12, 22, 11, 90];    println!("排序前: {:?}", numbers);    quick_sort(&mut numbers);    println!("排序后: {:?}", numbers);}

快速排序的平均时间复杂度为 O(n log n)，是实际应用中最常用的排序算法之一。

3. 使用标准库排序

当然，在真实项目中，你通常不需要自己实现排序。Rust标准库提供了高效的 sort() 方法：

fn main() {    let mut numbers = vec![64, 34, 25, 12, 22, 11, 90];    numbers.sort(); // 默认使用稳定的排序算法（通常是Timsort的变种）    println!("排序结果: {:?}", numbers);}

总结

通过本教程，你已经了解了如何在Rust中实现基本的排序算法。无论是学习目的还是性能优化，掌握 Rust排序算法 都能帮助你写出更高效、更安全的代码。记住，Rust语言教程 中的基础知识是构建高级技能的基石。

现在，动手试试吧！修改代码、测试不同数据，你会对这些算法有更深的理解。