插入排序

主问题重现

我们在下面用形式化语言¹ (已加之修改)给出主问题的一个重现:

输入

$n$ 个数的数组 $< a_{1}, a_{2}, \dots, a_{n} >$

输出

输入数组的升序排列 $< a_{1}^{'}, a_{2}^{'}, \dots, a_{n}^{'} >$ ，满足 $a_{1}^{'} \leq a_{2}^{'} \leq \dots \leq a_{n}^{'}$

主问题思考

在《算法导论》中，我们先引入了插入排序，这并不特别简单(不如冒泡)但可以让我们进行较高级的初步学习。

来看下面实现:

实现1

pub fn realize<T: Ord>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

可以发现: 插入排序的核心逻辑是通过逐步比较和移动元素来维护一个有序的子序列。具体地:

有序部分逐步扩张：将数组分为已排序部分(初始仅含第一个元素)和未排序部分，每次从未排序部分取出第一个元素，将其插入到已排序部分的正确位置，直到所有元素有序。
原地插入：插入操作通过依次向后移动元素实现，无需额外空间。

注: 这里我们采用了泛型，使得任何实现了Ord trait的数组切片(理论上Vec也会自动转换)均可进行插入排序

在《算法导论》中，其实是不是通过swap，而是将操作值保存，直到最后再进行赋值，这样可以减少中间的连续交换导致的空间和时间损耗。代价是需要更高的数学水平，同时需要更多的trait(像接下来的实现)。

实现2

pub fn realize2<T: Ord + Copy>(arr: &mut [T]) {
    for i in 1..arr.len() {
        // 保存当前元素的值
        let key = arr[i];
        // 找到合适的插入位置
        let mut j = i;
        while j > 0 && key < arr[j - 1] {
            // 向后移动元素而不是交换
            arr[j] = arr[j - 1];
            j -= 1;
        }
        // 将保存的值插入到正确位置
        arr[j] = key;
    }
}

(注: 需要Copy)

也可以使用Clone:

pub fn realize2_clone<T: Ord + Clone>(arr: &mut [T]) {
    for i in 1..arr.len() {
        // 保存当前元素的值
        let key = arr[i].clone();
        // 找到合适的插入位置
        let mut j = i;
        while j > 0 && key < arr[j - 1] {
            // 向后移动元素而不是交换
            arr[j] = arr[j - 1].clone();
            j -= 1;
        }
        // 将保存的值插入到正确位置
        arr[j] = key;
    }
}

练习与回答

尝试将实现1改为降序排列(满足 $a_{1}^{'} \geq a_{2}^{'} \geq \dots \geq a_{n}^{'}$ )。

实现3

// 对应练习 1
pub fn realize3<T: Ord>(arr: &mut [T]) {
    for i in 0..arr.len() - 1 {
        let mut j = i;
        while j > 0 && arr[j] > arr[j - 1] {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

注: 可以发现: 在插入排序中，只需修改比较条件即可改变排序方向

所以我们也有实现4这种可以设置排序规则的:

实现4

// 实现以`compare`来控制排序规则的插入排序
pub fn realize4<T, F>(arr: &mut [T], compare: F)
where
    F: Fn(&T, &T) -> bool,
{
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && compare(&arr[j], &arr[j - 1]) {
            arr.swap(j, j - 1);
            j -= 1;
        }
    }
}

上面这种比较，对于学习过其他语言的读者来说，应该不成问题。这个比较很显然的允许我们操作一些更特殊的类型，比如说结构体:

#[derive(Debug)]
struct Person {
    name: String,
    age: u32,
}

fn main() {
    // 创建可变的结构体数组
    let mut people = vec![
        Person { name: "Alice".to_string(), age: 30 },
        Person { name: "Bob".to_string(), age: 25 },
        Person { name: "Charlie".to_string(), age: 35 },
    ];
    
    // 按年龄升序排序
    realize4(&mut people, |a, b| a.age < b.age);
    println!("按年龄排序: {:?}", people);
    
    // 按名字字典序排序
    realize4(&mut people, |a, b| a.name < b.name);
    println!("按名字排序: {:?}", people);
}

我们再来看别的例题，继续深化学习:

考虑以下查找问题:

输入: $n$ 个数的数组 $< a_{1}, a_{2}, \dots, a_{n} >$ 和一个值 $v$

输出: 下标 $i$ 使得 $v = A [i]$ ，或者当 $v$ 不在 $A$ 出现时，返回特殊值 $N I L$ ²

尝试给出一个线性查找³的例子。

观察来看，这道题目适合Option可以用Option::None来解决NIL。

实现5

pub fn realize5<T: PartialEq>(arr: &[T], v: T) -> Option<usize> {
    for i in 0..arr.len() {
        if v == arr[i] {
            return Some(i);
        }
    }
    None
}

这里用 PartialEq 而非 Eq 以支持部分(宽松)相等，而无需反射(自反)

本处"形式化语言"并非指是一种由严格定义的符号组成的字符串集合，而是描述一类算法对于输入/输出关系的控制，以自然语言化，较精准化，弱数学化提供算法行为。 ↩
NIL是算法描述中表示“空”或“终止”的通用符号。并且与NULL等空指针中区分。在一些结构(如链表)，NIL是一类特殊哨兵值(后见)，在标准库实现中，NIL就有所存在。 ↩
线性查找(Linear Search)，也称为顺序查找，是一种简单直观的搜索算法。它的核心思想是逐个遍历数据集中的元素，直到找到目标值或遍历完所有元素。 ↩

Keyboard shortcuts

算法学习