第二十三 排序

排序（Sorting）是计算机科学中最基础、最重要的算法问题之一。它的目标是将一组数据按照某种特定的顺序重新排列。无论是数据库查询、搜索引擎排序，还是日常的数据处理，排序都无处不在。Rust 作为一门系统级编程语言，对排序提供了高效的标准库支持，同时也允许我们深入底层，亲手实现各种经典算法。

一、排序的基本概念

1.1 什么是排序

排序是将一组无序的数据元素按照关键字的大小重新排列，使其满足递增或递减顺序的过程。例如，将 [3, 1, 4, 1, 5] 排列为 [1, 1, 3, 4, 5]。

1.2 稳定性

稳定性是排序算法的一个重要属性。如果排序算法在排序后能够保持相等元素的原始相对顺序，则称该算法是稳定的；反之则是不稳定的。

例如，对 [("Alice", 85), ("Bob", 90), ("Carol", 85)] 按分数排序，稳定排序会保持 Alice 在 Carol 之前；而不稳定排序可能改变它们的相对位置。

1.3 时间复杂度与空间复杂度

原地排序（In-place） 指空间复杂度为 O(1) 的排序算法，不需要额外的存储空间。

二、简单排序

2.1 冒泡排序

冒泡排序（Bubble Sort）通过重复遍历数组，比较相邻元素并交换位置，使较大的元素逐渐“冒泡“到数组末端。

#![allow(unused)]
fn main() {
fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        let mut swapped = false;
        for j in 0..n - i - 1 {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
                swapped = true;
            }
        }
        if !swapped {
            break; // 已排序，提前退出
        }
    }
}
}

冒泡排序思路简单，但效率较低，适合教学理解和极小数据集。

2.2 选择排序

选择排序（Selection Sort）每次从未排序部分选出最小（或最大）元素，放到已排序部分的末尾。

#![allow(unused)]
fn main() {
fn selection_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        let mut min_idx = i;
        for j in i + 1..n {
            if arr[j] < arr[min_idx] {
                min_idx = j;
            }
        }
        arr.swap(i, min_idx);
    }
}
}

选择排序的交换次数最少（最多 n-1 次），但不稳定。

2.3 插入排序

插入排序（Insertion Sort）将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。

#![allow(unused)]
fn main() {
fn insertion_sort(arr: &mut [i32]) {
    for i in 1..arr.len() {
        let key = arr[i];
        let mut j = i;
        while j > 0 && arr[j - 1] > key {
            arr[j] = arr[j - 1];
            j -= 1;
        }
        arr[j] = key;
    }
}
}

插入排序对小规模或基本有序的数据非常高效，是归并排序和快速排序的常用优化手段。

三、高效排序

3.1 快速排序

快速排序（Quick Sort）采用分治策略，选择一个基准元素（pivot），将数组划分为小于基准和大于基准的两部分，然后递归排序。

#![allow(unused)]
fn main() {
fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot_index = partition(arr);
    let (left, right) = arr.split_at_mut(pivot_index);
    quick_sort(left);
    quick_sort(&mut right[1..]);
}

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

快速排序是实际应用中平均性能最好的排序算法之一。Rust 标准库的 sort_unstable 就是基于快速排序的优化版本（内省排序）。

3.2 归并排序

归并排序（Merge Sort）同样采用分治策略，将数组不断二分，直到子数组长度为 1，然后逐层合并两个有序子数组。

#![allow(unused)]
fn main() {
fn merge_sort(arr: &mut [i32]) {
    let len = arr.len();
    if len <= 1 {
        return;
    }
    let mid = len / 2;
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);

    let mut temp = arr.to_vec();
    merge(&arr[..mid], &arr[mid..], &mut temp);
    arr.copy_from_slice(&temp);
}

fn merge(left: &[i32], right: &[i32], temp: &mut [i32]) {
    let (mut i, mut j, mut k) = (0, 0, 0);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            temp[k] = left[i];
            i += 1;
        } else {
            temp[k] = right[j];
            j += 1;
        }
        k += 1;
    }
    while i < left.len() {
        temp[k] = left[i];
        i += 1;
        k += 1;
    }
    while j < right.len() {
        temp[k] = right[j];
        j += 1;
        k += 1;
    }
}
}

归并排序保证 O(n log n) 的最坏时间复杂度，且稳定，但需要额外 O(n) 空间。它是 Rust 标准库 sort（稳定排序）的核心基础。

3.3 堆排序

堆排序（Heap Sort）利用二叉堆的数据结构。首先构建最大堆，然后将堆顶（最大值）与末尾交换，再对剩余元素重新调整堆，重复此过程。

#![allow(unused)]
fn main() {
fn heap_sort(arr: &mut [i32]) {
    let n = arr.len();
    // 构建最大堆
    for i in (0..n / 2).rev() {
        heapify(arr, n, i);
    }
    // 逐个提取最大值
    for i in (1..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

fn heapify(arr: &mut [i32], n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if left < n && arr[left] > arr[largest] {
        largest = left;
    }
    if right < n && arr[right] > arr[largest] {
        largest = right;
    }
    if largest != i {
        arr.swap(i, largest);
        heapify(arr, n, largest);
    }
}
}

堆排序是原地排序且最坏时间复杂度为 O(n log n)，非常适合内存受限的场景。

四、非比较排序

非比较排序不通过元素间的直接比较来确定顺序，而是利用数据的特定特征（如数值范围），在特定条件下可以达到 O(n) 的时间复杂度。

4.1 计数排序

计数排序（Counting Sort）适用于数据范围较小且为整数的场景。它统计每个值出现的次数，然后按顺序输出。

#![allow(unused)]
fn main() {
fn counting_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }
    let max = *arr.iter().max().unwrap();
    let min = *arr.iter().min().unwrap();
    let range = (max - min + 1) as usize;

    let mut count = vec![0; range];
    for &num in arr.iter() {
        count[(num - min) as usize] += 1;
    }

    let mut idx = 0;
    for (i, &c) in count.iter().enumerate() {
        for _ in 0..c {
            arr[idx] = i as i32 + min;
            idx += 1;
        }
    }
}
}

4.2 桶排序

桶排序（Bucket Sort）将数据分到若干个有序的桶中，每个桶内再分别排序（通常用插入排序），最后按顺序合并。

#![allow(unused)]
fn main() {
fn bucket_sort(arr: &mut [f64]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }

    let mut buckets: Vec<Vec<f64>> = vec![vec![]; n];
    for &num in arr.iter() {
        let idx = (num * n as f64) as usize;
        let idx = idx.min(n - 1);
        buckets[idx].push(num);
    }

    for bucket in buckets.iter_mut() {
        bucket.sort_by(|a, b| a.partial_cmp(b).unwrap());
    }

    let mut idx = 0;
    for bucket in buckets.iter() {
        for &num in bucket.iter() {
            arr[idx] = num;
            idx += 1;
        }
    }
}
}

桶排序在数据均匀分布时效率极高，接近 O(n)。

4.3 基数排序

基数排序（Radix Sort）按位数从低到高（或从高到低）依次排序，每一位的排序使用稳定的计数排序。

#![allow(unused)]
fn main() {
fn radix_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }
    let max = *arr.iter().max().unwrap();
    let mut exp = 1;
    while max / exp > 0 {
        counting_sort_by_digit(arr, exp);
        exp *= 10;
    }
}

fn counting_sort_by_digit(arr: &mut [i32], exp: i32) {
    let n = arr.len();
    let mut output = vec![0; n];
    let mut count = [0; 10];

    for &num in arr.iter() {
        let digit = ((num / exp) % 10) as usize;
        count[digit] += 1;
    }
    for i in 1..10 {
        count[i] += count[i - 1];
    }
    for i in (0..n).rev() {
        let digit = ((arr[i] / exp) % 10) as usize;
        count[digit] -= 1;
        output[count[digit]] = arr[i];
    }
    arr.copy_from_slice(&output);
}
}

基数排序的时间复杂度为 O(d × (n + k))，其中 d 是最大位数，k 是基数（通常为 10）。

五、Rust 标准库排序

Rust 标准库为切片类型提供了两种高效的排序方法。

5.1 slice::sort — 稳定排序

#![allow(unused)]
fn main() {
let mut v = [3, 1, 4, 1, 5, 9, 2, 6];
v.sort();
println!("{:?}", v); // [1, 1, 2, 3, 4, 5, 6, 9]
}

sort 是稳定排序，基于 Timsort 算法（归并排序的优化变体），最坏时间复杂度为 O(n log n)。

5.2 slice::sort_unstable — 非稳定排序

#![allow(unused)]
fn main() {
let mut v = [3, 1, 4, 1, 5, 9, 2, 6];
v.sort_unstable();
println!("{:?}", v);
}

sort_unstable 基于模式 defeating 快速排序（Pattern-defeating Quicksort，pdqsort），平均性能通常优于稳定排序，且不分配额外内存。

5.3 自定义排序

#![allow(unused)]
fn main() {
let mut words = ["banana", "apple", "cherry"];
words.sort_by(|a, b| a.len().cmp(&b.len()));

let mut nums = [3, 1, 4, 1, 5];
nums.sort_by_key(|&x| -x); // 降序
}

5.4 对自定义类型排序

#![allow(unused)]
fn main() {
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Student {
    name: String,
    score: u32,
}

let mut students = vec![
    Student { name: "Alice".to_string(), score: 85 },
    Student { name: "Bob".to_string(), score: 92 },
];
students.sort(); // 需要实现 Ord trait
}

六、排序算法对比

七、总结与练习

本章小结

练习建议

1. 实现优化：为快速排序添加“三数取中“选基准和尾递归优化。
2. 混合排序：实现一个排序函数，对小数组使用插入排序，对大数组使用快速排序。
3. 链表排序：尝试对 LinkedList 实现归并排序。
4. 性能测试：使用 std::time::Instant 对比不同排序算法在随机数据、有序数据、逆序数据上的性能。
5. 稳定排序改造：修改快速排序的实现，使其成为稳定排序（提示：使用额外空间）。
6. 并行排序：利用 Rayon 库的 par_sort，体验并行排序带来的性能提升。