在 Rust 中实现算法不仅是为了学习排序逻辑，更是为了深入理解 Rust 的内存安全和所有权机制。今天，我将带大家通过实现一个经典的**快速排序（Quick Sort）**算法，来探讨 Rust 中的泛型编程、边界安全处理以及性能优化技巧。

本文实现的快速排序包含了三数取中法选取基准值，能够有效避免在有序数组上的性能退化。

核心算法思想

快速排序是一种基于分治法（Divide and Conquer）的排序算法。它的核心步骤分为三步：

1. 分解（Partition）：从数组中选择一个元素作为基准（Pivot），将所有小于基准的元素移到其左边，大于基准的元素移到其右边。
2. 递归（Recursion）：对基准左边和右边的子数组递归地执行快速排序。
3. 合并（Combine）：当递归结束时，数组自然就有序了，无需额外合并操作。

为了提升性能，我们采用了三数取中法（Median-of-three）来选择基准，这能极大降低遇到最坏情况（$O(n^2)$）的概率。

完整代码实现

以下是完整的 Rust 代码实现。如果你赶时间，可以直接复制这段代码运行。

///
/// Rust 语言的常用算法
/// 

/// 快速排序主函数
/// 
/// # 参数
/// * `arr` - 需要排序的可变切片引用
/// 
/// # 泛型约束
/// * `T: Ord ` - T 必须实现可排序和克隆 trait
/// 
/// # 示例
/// ```
/// let mut arr = vec![3, 1, 4, 1, 5];
/// quick_sort(&mut arr);
/// assert_eq!(arr, vec![1, 1, 3, 4, 5]);
/// ```
pub fn quick_sort<T: Ord>(arr: &mut [T]) {
    // 调用实际的快速排序实现，初始左右边界为整个数组范围
    quick_sort_impl(arr, 0, arr.len() - 1);
}

/// 快速排序递归实现函数
/// 
/// # 参数
/// * `arr` - 需要排序的可变切片引用
/// * `left` - 当前排序范围的左边界（包含）
/// * `right` - 当前排序范围的右边界（包含）
/// 
/// # 泛型约束
/// * `T: Ord` - T 必须实现可排序
fn quick_sort_impl<T: Ord>(arr: &mut [T], left: usize, right: usize) {
    // 递归终止条件：当左边界大于等于右边界时停止排序
    if left >= right {
        return;
    }
    
    // 对当前范围进行分区操作，返回基准元素的最终位置
    let pivot = partition(arr, left, right);
    
    
    // 递归排序基准元素左侧的部分（注意防止 usize 下溢）
    
    if let Some(prev) = pivot.checked_sub(1) {
        if left <= prev {
            quick_sort_impl(arr, left, prev);
        }
    }
    // 递归排序基准元素右侧的部分
    quick_sort_impl(arr, pivot + 1, right);
}

/// 三数取中法选择基准元素
/// 通过比较左、中、右三个位置的元素，将中位数放到中间位置
/// 
/// # 参数
/// * `arr` - 数组切片
/// * `left` - 左边界
/// * `right` - 右边界
/// 
/// # 返回值
/// 返回中位数元素的索引
/// 
/// # 泛型约束
/// * `T: Ord ` - T 必须实现可排序
fn get_mid<T: Ord>(arr: &mut [T], left: usize, right: usize) -> usize {
    // 计算中间位置索引
    let mid = (left + right) / 2;
    
    // 确保 arr[left] <= arr[mid] <= arr[right]
    // 如果左边元素大于中间元素，则交换
    if arr[left] > arr[mid] {
        arr.swap(left, mid);
    }
    
    // 如果左边元素大于右边元素，则交换
    if arr[left] > arr[right] {
        arr.swap(left, right);
    }
    
    // 如果中间元素大于右边元素，则交换
    if arr[mid] > arr[right] {
        arr.swap(mid, right);
    }
    
    // 返回中位数的索引
    mid
}

/// 分区函数：将数组分为小于基准和大于基准的两部分
/// 
/// # 参数
/// * `arr` - 需要分区的数组切片
/// * `left` - 分区范围的左边界
/// * `right` - 分区范围的右边界
/// 
/// # 返回值
/// 基准元素在分区后的最终位置索引
/// 
/// # 泛型约束
/// * `T: Ord` - T 必须实现可排序
fn partition<T: Ord>(arr: &mut [T], left: usize, right: usize) -> usize {
    // 使用三数取中法获取基准元素的索引
    let mid_index = get_mid(arr, left, right);
    
    // 将基准元素交换到最左边，方便处理
    arr.swap(left, mid_index);   
    

    // 初始化左右指针
    let mut i = left + 1;
    let mut j = right;

    loop {
        // 从左边找到第一个大于等于pivot的元素
        while i <= j && arr[i] < arr[left] {
            i += 1;
        }
        
        // 从右边找到第一个小于pivot的元素
        while i <= j && arr[j] > arr[left] {
            j -= 1;
        }
        
        // 如果指针相遇，则结束分区
        if i >= j {
            break;
        }
        
        // 交换元素
        arr.swap(i, j);
        i += 1;
        j -= 1;
    }
    
    // 将基准元素放到正确的位置
    arr.swap(left, j);    
    // 返回基准元素的最终位置
    j
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_quick_sort() {
        let mut arr = vec![3, 1, 4, 1, 5];
        quick_sort(&mut arr);
        assert_eq!(arr, vec![1, 1, 3, 4, 5]);
    }
}

代码核心亮点解析

1. 泛型约束与克隆优化

pub fn quick_sort<T: Ord >(arr: &mut [T])

• Ord: 确保类型可以比较大小（这是排序的前提）。

2. 防御性编程：checked_sub

这是 Rust 特有的安全处理技巧。
在快速排序中，我们需要对基准左边的区间 [left, pivot-1] 进行递归。如果 pivot 是 0，那么 pivot - 1 会导致 usize 下溢（Underflow）。

• 在 C++/C 中：这会导致未定义行为或数据损坏。
• 在 Rust 中：Debug 模式会 panic，Release 模式会回绕成一个极大值。

我们使用 pivot.checked_sub(1) 来安全地处理这个问题：

if let Some(prev) = pivot.checked_sub(1) {
    quick_sort_impl(arr, left, prev);
}

如果 pivot 为 0，checked_sub(1) 会返回 None，从而跳过左侧的递归，保证了程序的健壮性。

3. 三数取中法（Median-of-three）

fn get_mid<T: Ord>(arr: &mut [T], left: usize, right: usize) -> usize

为了避免在已经有序的数组上性能退化为 $O(n^2)$，我们不盲目选择第一个或最后一个元素作为基准，而是取最左、最右、中间三个元素，将其中位数放到 left 位置作为基准。这能显著提高算法在实际数据中的平均性能。

4. 双指针碰撞（Hoare Partition）

partition 函数使用了 Hoare 的原始分区方案：

• 指针 i 从左往右找比基准大的。
• 指针 j 从右往左找比基准小的。
• 一旦找到，就交换两者。
  这种方案在处理包含大量重复元素的数组时，效率通常高于单向扫描的 Lomuto 方案。

性能与复杂度分析

指标	描述
平均时间复杂度	$O(n\log n)$
最坏时间复杂度	$O(n^2)$ (虽然三数取中大大降低了这种概率)
空间复杂度	$O(\log n)$ (递归调用栈的深度)
稳定性	不稳定 (相同元素的相对位置可能发生改变)

测试与验证

我们在代码中附带了一个简单的单元测试。你可以通过 cargo test 命令来验证算法的正确性。

#[test]
fn test_quick_sort() {
        let mut arr = vec![3, 1, 4, 1, 5];
        quick_sort(&mut arr);
        assert_eq!(arr, vec![1, 1, 3, 4, 5]);
    }

总结

通过这个实现，我们不仅复习了快速排序的经典逻辑，还学习了如何在 Rust 中：

1. 使用 checked_sub 处理无符号整数的边界安全。
2. 利用泛型 T: Ord + Clone 编写通用的容器算法。
3. 通过三数取中法优化算法性能。

注：在实际生产环境中，建议直接使用标准库的 arr.sort() 或 arr.sort_unstable()，它们经过了极致的汇编优化。手写此算法主要用于学习和特定需要自定义排序逻辑的场景。