Rust编程日记-1：用Rust验证基础算法实践-一叶飘零

最近决定通过实现基础算法来深入学习Rust语言特性。作为一门以安全性和性能著称的系统级语言，Rust在算法实现中展现出的独特魅力（如所有权机制、模式匹配）令人着迷。本文将记录如何用Rust实现并验证经典算法，涵盖冒泡排序、二分查找、链表操作和递归算法，并通过测试代码确保其正确性。

一、算法实现与验证

1. 冒泡排序：理解可变性与借用

冒泡排序的核心是通过相邻元素的交换将最大值“浮”到数组末尾。在Rust中，需明确变量的可变性（mut）和数组的借用方式。

fn bubble_sort<T: PartialOrd>(arr: &mut [T]) {
    let len = arr.len();
    for i in 0..len {
        for j in 0..len - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

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

    #[test]
    fn test_bubble_sort() {
        let mut arr = [3, 1, 4, 1, 5, 9, 2, 6];
        bubble_sort(&mut arr);
        assert_eq!(arr, [1, 1, 2, 3, 4, 5, 6, 9]);
    }
}

实现要点：

泛型<T: PartialOrd>使函数支持任何可比较类型
arr.swap()直接操作内存，避免手动值交换
测试模块通过#[cfg(test)]条件编译，仅在校验时启用

2. 二分查找：利用Option和模式匹配

二分查找要求数据集有序，并通过中间值比较缩小范围。Rust的Option<usize>完美表达“找到索引”或“不存在”两种状态。

fn binary_search<T: PartialOrd>(arr: &[T], target: &T) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;
        if &arr[mid] == target {
            return Some(mid);
        } else if &arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    None
}

#[test]
fn test_binary_search() {
    let arr = [1, 3, 5, 7, 9];
    assert_eq!(binary_search(&arr, &5), Some(2));
    assert_eq!(binary_search(&arr, &10), None);
}

避坑指南：

使用left + (right - left) / 2而非(left + right)/2防止整数溢出
模式匹配Some/None代替传统的-1返回值，增强代码可读性

3. 链表实现：探索所有权与智能指针

链表是理解Rust内存管理的绝佳案例。通过Box智能指针和Option枚举实现单向链表：

#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(value: T) -> Self {
        Node { value, next: None }
    }
}

struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> LinkedList<T> {
    fn push_front(&mut self, value: T) {
        let mut new_node = Box::new(Node::new(value));
        new_node.next = self.head.take();
        self.head = Some(new_node);
    }
}

#[test]
fn test_linked_list() {
    let mut list = LinkedList { head: None };
    list.push_front(3);
    list.push_front(2);
    list.push_front(1);
    assert!(matches!(list.head, Some(node) if node.value == 1));
}

核心机制：

Box在堆上分配数据，确保固定大小
Option.take()转移所有权，避免悬垂指针
#[derive(Debug)]为结构体自动实现调试打印

4. 递归算法：斐波那契数列与栈安全

递归是算法设计中的重要范式。实现斐波那契数列时需注意Rust的栈溢出风险：

fn fibonacci(n: u64) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

// 尾递归优化版本
fn fibonacci_tail(n: u64) -> u64 {
    fn helper(a: u64, b: u64, n: u64) -> u64 {
        match n {
            0 => a,
            1 => b,
            _ => helper(b, a + b, n - 1),
        }
    }
    helper(0, 1, n)
}

#[test]
fn test_fibonacci() {
    assert_eq!(fibonacci(10), 55);
    assert_eq!(fibonacci_tail(10), 55);
}

性能对比：

普通递归时间复杂度O(2ⁿ)，空间O(n)
尾递归版本优化为O(n)时间复杂度，但Rust不保证尾调用优化（TCO）

二、Rust算法实践总结

通过实现上述算法，深刻体会到Rust的独特优势：

内存安全：编译器严格检查所有权，避免空指针和野指针
零成本抽象：泛型代码与手写C性能相当
模式匹配：优雅处理Option和Result类型
测试友好：内置测试框架简化验证流程

挑战与反思：

链表等递归数据结构需要谨慎处理所有权
递归深度较大时需改用迭代防止栈溢出
生命周期标注在复杂场景中仍需深入学习