面向资深开发者的Rust快速排序实现 | AI生成和翻译

Home 2025.06 English 中文

---

好的，鉴于您在算法、全栈开发乃至移动工程方面的深厚背景，您会发现 Rust 在内存安全和显式控制方面的做法在概念上相当熟悉，即使其语法和严格性是新的。让我们来剖析这个 Rust 实现的快速排序。

---

Rust 中的快速排序：面向经验丰富的开发者

这段 Rust 代码实现了经典的快速排序算法。快速排序的核心思想是选取一个元素作为基准，并围绕该基准对数组进行分区，使得小于基准的元素位于一侧，大于基准的元素位于另一侧。然后，将此过程递归地应用于子数组。

让我们来看看这些函数：

---

fn quick_sort(arr: &mut [i32])

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..]);
}

• arr: &mut [i32]：这里 Rust 的类型系统立刻展现了它的特色。
  • &mut 表示一个可变引用。这意味着 quick_sort 函数获得了对数组 arr 的借用引用，并且被允许原地修改该数组的内容。
  • [i32] 是一个 i32 整数的切片。在 Rust 中，[T] 是切片的类型，它表示对连续元素序列的一个视图。它不拥有数据；它只是指向数组或 Vec 的一部分。这对于效率至关重要，因为它避免了数据的复制。您从 C/C++/Java 背景中熟悉指针和数组片段；可以将其视为 Rust 管理这些概念的安全且显式的方式。
• 基本情况 if arr.len() <= 1：快速排序的标准递归基本情况。如果切片有 0 或 1 个元素，它已经是有序的，直接返回。
• let pivot_index = partition(arr);：调用 partition 函数（我们接下来会看）来重新排列切片。它返回基准元素的最终位置。
• let (left, right) = arr.split_at_mut(pivot_index);：这是 Rust 用于安全可变别名的一个关键特性。
  • split_at_mut 是可变切片的一个方法。它接受一个索引，并将可变切片分割成两个互不相交的可变切片。
  • left 将是 arr[0..pivot_index]，而 right 将是 arr[pivot_index..len]。
  • 这是 Rust 借用检查器的基础。您不能同时拥有对相同数据的两个可变引用。split_at_mut 确保 left 和 right 引用原始数组的完全独立的部分，从而满足借用检查器，并防止多线程上下文中的数据竞争（即使这里是单线程的，该原则仍然适用）。
• quick_sort(left);：递归地对 left 子切片进行排序。
• quick_sort(&mut right[1..]);：递归地对 right 子切片进行排序。
  • right[1..] 很重要：right 切片从 pivot_index 开始。由于 arr[pivot_index] 现在是已正确定位的基准元素，我们将其从右侧的递归调用中排除。
  • &mut 显式地从 right 重新借用了一个可变切片。

---

fn partition(arr: &mut [i32]) -> usize

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
}

这个函数实现了 Lomuto 分区方案，这是为快速排序分区数组的一种常见方式。

• let len = arr.len();：获取当前切片的长度。
• let pivot = arr[len - 1];：选择切片的最后一个元素作为基准。
• let mut i = 0;：i 充当一个指针，指向小于或等于基准的元素与大于基准的元素之间的”边界”。i 左侧的元素将是小于或等于基准的元素。
• for j in 0..len - 1：这个循环遍历除基准（位于 len - 1）之外的所有元素。
• if arr[j] <= pivot { ... }：如果当前元素 arr[j] 小于或等于基准：
  • arr.swap(i, j);：交换 arr[j] 和 arr[i]。这将较小的元素移动到”小于或等于”的区域。
  • i += 1;：递增 i 以扩展”小于或等于”的区域。
• arr.swap(i, len - 1);：循环结束后，i 是基准的正确位置。我们将基准（仍然在 len - 1）交换到其最终的排序位置。现在，i 左侧的所有元素都小于或等于 arr[i]（即基准），而右侧的所有元素都大于基准。
• i：函数返回 i，即基准元素的最终索引。

---

fn main()

fn main() {
    let mut arr = [3, 6, 8, 10, 1, 2, 1];
    println!("Before: {:?}", arr);
    quick_sort(&mut arr);
    println!("After: {:?}", arr);
}

• let mut arr = [3, 6, 8, 10, 1, 2, 1];：
  • let mut 声明一个可变变量。这允许您重新分配该变量或修改其内容（如果它是可变类型）。
  • [3, ...] 在栈上创建一个固定大小的数组。其大小在编译时已知。
• println!("Before: {:?}", arr);：使用 println! 宏进行输出。
  • {:?} 是调试打印格式说明符。它使用 Debug trait 来打印数组的人类可读表示形式。
• quick_sort(&mut arr);：调用 quick_sort 函数，传递对 arr 数组的可变引用。
• println!("After: {:?}", arr);：排序后再次打印数组。

---

为您总结的 Rust 特定要点

• 所有权和借用：这段代码是 Rust 核心概念的典型示例。您传递的是引用（& 和 &mut），而不是复制数据。&mut 引用对于原地修改数组至关重要，而借用检查器（例如，由 split_at_mut 强制执行）确保您永远不会同时拥有对相同数据的多个可变引用，从而在编译时消除了一整类的并发错误。这可能是与 Java 或 Python 等语言相比最大的范式转变，但它提供了无需垃圾收集器的内存安全。
• 切片 [T]：这对于处理连续数据非常强大。它们提供了对数组或向量部分的安全、高效视图，而无需分配新内存。
• 宏（println!）：您会在许多标准库函数（如 println!、vec!、format!）后面看到 !。这表明它们是宏，而不是常规函数。宏在编译时扩展代码，与常规函数相比，提供了更大的灵活性和能力（例如可变参数或编译时代码生成）。

鉴于您的背景，您很可能会欣赏 Rust 提供的性能特性和安全保证，即使”借用检查器之舞”需要一点时间来适应。这是一种关于内存管理的不同思维方式，但能带来高度健壮和高效的代码。

---

Back Donate