Rust 如何优雅实现冒泡排序
冒泡排序作为一种经典的排序算法，以其直观的比较与交换逻辑，成为算法学习的重要起点。尽管它在性能上并非最优，但在理解排序思想和编程实践上仍有独特价值。本文将带你走进冒泡排序的核心原理，结合 Rust 语言的安全性与简洁性，探索如何以优雅的方式实现这一算法。从逐步拆解的过程到高效的代码实现，无论你是算法爱好者还是 Rust 编程的探索者，这篇文章都将为你呈现一场技术与美感的碰撞。
本文深入剖析了冒泡排序的工作机制，通过示例数组 [5, 3, 8, 4, 2] 清晰展示了相邻元素比较与交换的每一步操作。接着，我们提供了 Python 和 Rust 两种语言的实现，其中 Rust 版本利用 swapped 标志位优化循环，在数组已有序时提前退出，兼顾效率与逻辑清晰。代码还包含全面测试，验证了算法在多种场景下的可靠性。Rust 实现通过借用检查和 arr.swap() 等特性，展现了语言的安全性与优雅表达。本文适合希望理解冒泡排序本质或探索 Rust 编程之美的读者。
冒泡排序（Bubble Sort）算法详解
冒泡排序是一种简单的基于比较的排序算法，其核心思想是通过相邻元素的反复比较和交换，将较大的元素逐步“浮”到数组的末尾（像气泡上浮一样，因此得名）。以下是逐步解析：
算法步骤（黑板图示）
假设对数组 [5, 3, 8, 4, 2] 升序排序：
初始状态: [5, 3, 8, 4, 2]
第1轮:
比较 5↔3 → 交换 → [3, 5, 8, 4, 2]
比较 5↔8 → 不交换
比较 8↔4 → 交换 → [3, 5, 4, 8, 2]
比较 8↔2 → 交换 → [3, 5, 4, 2, 8] （最大值8已到末尾）
第2轮:
比较 3↔5 → 不交换
比较 5↔4 → 交换 → [3, 4, 5, 2, 8]
比较 5↔2 → 交换 → [3, 4, 2, 5, 8] （次大值5就位）
第3轮:
比较 3↔4 → 不交换
比较 4↔2 → 交换 → [3, 2, 4, 5, 8] （4就位）
第4轮:
比较 3↔2 → 交换 → [2, 3, 4, 5, 8] （完全有序）
实操冒泡排序
Python 代码
def bubble_sort(arr):
n = len(arr)
for i in range(n-1): # 外层控制轮数
swapped = False # 优化：若本轮无交换，则已有序
for j in range(n-1-i): # 内层比较相邻元素
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j] # 交换
swapped = True
if not swapped:
break
return arr
# 测试
print(bubble_sort([5, 3, 8, 4, 2])) # 输出: [2, 3, 4, 5, 8]
Rust 代码
// 目标：对数组进行冒泡排序
fn bubble_sort(arr: &mut [i32]) {
let len = arr.len();
let mut swapped; // 标记本轮是否有交换发生
for i in 0..len {
swapped = false;
// 每次只需比较到 len - i - 1
// len-i-1 中的 i 正好是已完成的轮数，也是已排序的元素数
// -1 是因为比较的是 arr[j] 和 arr[j+1]，防止数组越界
for j in 0..len - i - 1 {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
swapped = true; // 标记有交换发生
}
}
// 如果本轮没有交换，说明数组已有序，可以提前终止
if !swapped {
break;
}
}
}
fn bubble_sort(arr: &mut [i32]) {
let len = arr.len();
let mut swapped;
for i in 0..len {
swapped = false;
for j in 0..len - i - 1 {
if arr[j] > arr[j + 1] {
arr.swap(j, j + 1);
swapped = true;
}
}
if !swapped {
break;
}
}
}
#[test]
fn test_bubble_sort() {
// 普通测试用例
let mut arr = [5, 3, 4, 1, 2];
bubble_sort(&mut arr);
assert_eq!(arr, [1, 2, 3, 4, 5]);
// 已排序数组
let mut arr2 = [1, 2, 3, 4, 5];
bubble_sort(&mut arr2);
assert_eq!(arr2, [1, 2, 3, 4, 5]);
// 逆序数组
let mut arr3 = [5, 4, 3, 2, 1];
bubble_sort(&mut arr3);
assert_eq!(arr3, [1, 2, 3, 4, 5]);
// 空数组
let mut arr4: [i32; 0] = [];
bubble_sort(&mut arr4);
assert_eq!(arr4, []);
// 单元素数组
let mut arr5 = [1];
bubble_sort(&mut arr5);
assert_eq!(arr5, [1]);
}
fn main() {
let mut arr = [5, 3, 4, 1, 2];
println!("Before sorting: {:?}", arr);
bubble_sort(&mut arr);
println!("After sorting: {:?}", arr);
}
这段 Rust 代码实现了一个冒泡排序算法，主要包含三个部分：排序函数实现、测试用例和主函数演示。冒泡排序的核心思想是通过反复比较相邻元素并交换它们的位置，使得较大的元素逐渐"浮"到数组末尾。该实现特别添加了 swapped 标志位进行优化：在外层循环的每一轮开始时将 swapped 设为 false，在内层循环中若发生元素交换则设为 true；当完成一轮比较后若 swapped 仍为 false，说明数组已完全有序，可提前终止排序，这使得算法在最佳情况（已排序数组）下的时间复杂度从 O(n²) 降为 O(n)。测试用例验证了算法对普通数组、已排序数组、逆序数组、空数组和单元素数组都能正确工作，而主函数则展示了实际使用时的输入输出效果。整个实现体现了 Rust 的安全特性（如借用检查确保内存安全）和简洁语法（如 arr.swap() 方法）。
总结
冒泡排序虽简单，却承载了算法设计的基础思想。通过本文的解析，我们不仅掌握了其通过相邻交换实现有序化的过程，还见证了 Rust 如何以优雅的方式赋予这一经典算法新的生命。Rust 实现的优化设计与安全特性，让代码既高效又可靠，充分体现了现代编程语言的魅力。对于算法学习者，这是一次扎实的实践；对于 Rust 爱好者，这是一场优雅实现的启发。未来，不妨尝试用 Rust 挑战更复杂的排序算法，探索技术之美的更多可能。
参考
