Rust 实战：手把手教你实现高性能快速排序

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

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

核心算法思想

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

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

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

完整代码实现

以下是完整的 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]);/// ```pubfnquick_sort<T:Ord>(arr:&mut[T]){// 调用实际的快速排序实现，初始左右边界为整个数组范围quick_sort_impl(arr,0,arr.len()-1);}/// 快速排序递归实现函数////// # 参数/// * `arr` - 需要排序的可变切片引用/// * `left` - 当前排序范围的左边界（包含）/// * `right` - 当前排序范围的右边界（包含）////// # 泛型约束/// * `T: Ord` - T 必须实现可排序fnquick_sort_impl<T:Ord>(arr:&mut[T],left:usize,right:usize){// 递归终止条件：当左边界大于等于右边界时停止排序ifleft>=right{return;}// 对当前范围进行分区操作，返回基准元素的最终位置letpivot=partition(arr,left,right);// 递归排序基准元素左侧的部分（注意防止 usize 下溢）ifletSome(prev)=pivot.checked_sub(1){ifleft<=prev{quick_sort_impl(arr,left,prev);}}// 递归排序基准元素右侧的部分quick_sort_impl(arr,pivot+1,right);}/// 三数取中法选择基准元素/// 通过比较左、中、右三个位置的元素，将中位数放到中间位置////// # 参数/// * `arr` - 数组切片/// * `left` - 左边界/// * `right` - 右边界////// # 返回值/// 返回中位数元素的索引////// # 泛型约束/// * `T: Ord ` - T 必须实现可排序fnget_mid<T:Ord>(arr:&mut[T],left:usize,right:usize)->usize{// 计算中间位置索引letmid=(left+right)/2;// 确保 arr[left] <= arr[mid] <= arr[right]// 如果左边元素大于中间元素，则交换ifarr[left]>arr[mid]{arr.swap(left,mid);}// 如果左边元素大于右边元素，则交换ifarr[left]>arr[right]{arr.swap(left,right);}// 如果中间元素大于右边元素，则交换ifarr[mid]>arr[right]{arr.swap(mid,right);}// 返回中位数的索引mid}/// 分区函数：将数组分为小于基准和大于基准的两部分////// # 参数/// * `arr` - 需要分区的数组切片/// * `left` - 分区范围的左边界/// * `right` - 分区范围的右边界////// # 返回值/// 基准元素在分区后的最终位置索引////// # 泛型约束/// * `T: Ord` - T 必须实现可排序fnpartition<T:Ord>(arr:&mut[T],left:usize,right:usize)->usize{// 使用三数取中法获取基准元素的索引letmid_index=get_mid(arr,left,right);// 将基准元素交换到最左边，方便处理arr.swap(left,mid_index);// 初始化左右指针letmuti=left+1;letmutj=right;loop{// 从左边找到第一个大于等于pivot的元素whilei<=j&&arr[i]<arr[left]{i+=1;}// 从右边找到第一个小于pivot的元素whilei<=j&&arr[j]>arr[left]{j-=1;}// 如果指针相遇，则结束分区ifi>=j{break;}// 交换元素arr.swap(i,j);i+=1;j-=1;}// 将基准元素放到正确的位置arr.swap(left,j);// 返回基准元素的最终位置j}#[cfg(test)]modtests{usesuper::*;#[test]fntest_quick_sort(){letmutarr=vec![3,1,4,1,5];quick_sort(&mutarr);assert_eq!(arr,vec![1,1,3,4,5]);}}

代码核心亮点解析

1. 泛型约束与克隆优化

pubfnquick_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)来安全地处理这个问题：

ifletSome(prev)=pivot.checked_sub(1){quick_sort_impl(arr,left,prev);}

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

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

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

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

4. 双指针碰撞（Hoare Partition）

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

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

性能与复杂度分析

测试与验证

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

#[test]fntest_quick_sort(){letmutarr=vec![3,1,4,1,5];quick_sort(&mutarr);assert_eq!(arr,vec![1,1,3,4,5]);}

总结

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

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

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