1.假设待排序数组如下

  let mut arr = [5, 3, 8, 4, 2, 7, 1];

数组需要设计为可变的，让arr传递到函数的时候能够被借出

2.冒泡排序法

2.1.原理

反复遍历列表，比较相邻的两个元素，如果顺序错误（如前者大于后者），就交换它们。每次遍历后，最大的元素会“冒泡”到列表末尾。重复此过程，直到没有需要交换的元素，列表即排序完成。 因为一趟遍历就会把最大的数排序到数组的末尾，所以一共需要arr.len()-1趟才能把所有数字排序好。 每一趟排序，需要比较的次数也是逐渐减少的，因为之前的每一趟排序后都会有一个排序好的数字。 时间复杂度通常为 O(n^2)，效率较低，适合小数据排序。

2.2.代码实现

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

2.3.测试

let mut arr = [5, 3, 8, 4, 2, 7, 1];
println!("排序前: {:?}", arr);
bubble_sort(&mut numbers);
println!("排序后: {:?}", arr);

// 排序前: [5, 3, 8, 4, 2, 7, 1]
// 排序后: [1, 2, 3, 4, 5, 7, 8]

3.快速排序法

3.1.原理

快速排序是一种高效的排序算法，基于分治法。其核心思想是从数组中选择一个基准元素（pivot），通过将数组分为两部分——小于基准的元素和大于或等于基准的元素——然后对这两部分递归排序，最终实现整个数组的有序排列。 当分区较为平衡时，时间复杂度为O(nlogn)。

3.2.分区方案

3.2.1.Hoare分区

1. 选择一个基准（通常是数组的某个元素，如最后一个）。
2. 使用两个指针：一个从数组的开头（左指针）开始向右移动，直到找到一个大于或等于基准的元素；另一个从数组的末尾（右指针）开始向左移动，直到找到一个小于或等于基准的元素。
3. 当左右指针都找到不符合条件的元素时，交换它们，然后继续移动指针，直到指针相遇或交叉；并且交换交叉索引和基准元素的位置。
4. 分区完成后，数组被分成两部分：左侧部分的所有元素小于或等于基准，右侧部分的所有元素大于或等于基准。

3.2.2.Lomuto分区

使用一个指针迭代数组，另一个指针跟踪小于基准的区域的边界。分区完成后，基准会被明确放置在其最终位置。

3.2.3.方案对比

Hoare方案的优点在于交换次数更少，平均情况下比Lomuto方案少三分之一的交换操作。这是因为Hoare方案只在发现逆序（即左侧元素大于基准，右侧元素小于基准）时才进行交换，而Lomuto方案可能会进行更多的交换。

3.3.代码实现

3.3.1.Hoare

use std::fmt::Debug;

fn main() {
    let mut numbers = [5, 3, 8, 4, 2, 7, 1];
    println!("排序前: {:?}", numbers);
    quick_sort(&mut numbers);
    println!("排序后: {:?}", numbers);  // [1, 2, 3, 4, 5, 7, 8]
}

fn quick_sort<T: PartialOrd + Debug>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let pivot_index = hoare_partition(arr);
    let (left, right) = arr.split_at_mut(pivot_index);
    quick_sort(left);
    quick_sort(right);
}

/// Hoare 分区函数
fn hoare_partition<T: PartialOrd + Debug>(arr: &mut [T]) -> usize {
    // let pivot_index = arr.len() / 2; // 选择中间元素作为基准
    // arr.swap(pivot_index, arr.len() - 1); // 将基准移到末尾（可选，便于统一逻辑）
    let pivot_index = arr.len() - 1;

    let mut i = 0;
    let mut j = arr.len() - 1;

    loop {
        // 从左找第一个 > 基准的元素
        while i < j && arr[i] <= arr[pivot_index] {
            i += 1;
        }

        // 从右找第一个 < 基准的元素
        while i < j && arr[j] >= arr[pivot_index] {
            j -= 1;
        }

        if i >= j {
            break;
        }

        // 交换不符合条件的元素
        // println!("[交换前] i={}, j={}, 数组: {:?}", i, j, arr); // 打印交换前的数组
        arr.swap(i, j);
        // println!("[交换后] i={}, j={}, 数组: {:?}", i, j, arr); // 打印交换后的数组
    }

    // 将基准放到最终位置
    // println!("[基准归位前] 数组: {:?}", arr); // 打印最终数组
    arr.swap(i, pivot_index);
    // println!("[基准归位] 最终数组: {:?}", arr); // 打印最终数组
    i
}

第一轮 [5, 3, 8, 4, 2, 7, 1]

基准数是最后一位 1 i从左边找大于1的数，那就是i=0是5；j从左边找到小于1的数，一直找到j=0，还没有找到；所以会走到 i < j 会跳出while循环，所以会走到if i >= j 这一行判断来，所以break了。最后把基准数和i的位置交换，为什么要交换，是因为i是从左一直找大于1的数的，j是从右找小于1的数，那么遇到i >= j的场景说明是两侧都遍历过了再没有符合arr[i]和arr[j]交换的元素也就是两侧都是小于1或者大于1的；而且i所在的数肯定是大于基准的，所以要和基准交换。 结果是 [1, 3, 8, 4, 2, 7, 5]；此时 新基准索引i的值:0

第二轮 [1, 3, 8, 4, 2, 7, 5]

基准数还是最后一位 5 i从左边找大于5的是i=2，是8，j从右边找小于5的是j=4，是2；i < j，满足交换的条件，变成[1, 3, 2, 4, 8, 7, 5] 继续寻找，i走到i=4，8的位置上时，j走到j=3，4的位置上，但此时 i > j，不满足交换条件，break了。 再交换基准和索引i的位置，因为索引i的位置肯定了是大于5的数，所以8和5交换，变成 [1, 3, 2, 4, 5, 7, 8] ；此时新基准索引i的值:4

第三轮 [1, 3, 2, 4] 和 [5, 7, 8]

后面递归排序就行。。。

3.3.2.Lomuto

fn main() {
    let mut numbers = [5, 3, 8, 4, 2, 7, 1];
    println!("排序前: {:?}", numbers);
    quick_sort(&mut numbers);
    println!("排序后: {:?}", numbers); // [1, 2, 3, 4, 5, 7, 8]
}

fn quick_sort<T: PartialOrd>(arr: &mut [T]) {
    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<T: PartialOrd>(arr: &mut [T]) -> usize {
    let pivot_index = arr.len() - 1; // 选择最后一个元素作为基准
    let mut i = 0; // i 是“小于基准”的区域的边界

    for j in 0..pivot_index {
        if arr[j] <= arr[pivot_index] {
            arr.swap(i, j); // 将较小元素交换到左侧
            i += 1;
        }
    }

    arr.swap(i, pivot_index); // 将基准放到正确位置
    i // 返回基准的索引
}

变量的含义

1. i：表示“小于等于基准”区域的右边界（初始为 0）。所有索引 < i 的元素均满足 ≤ 基准。 j：遍历数组的指针，从 0 到 pivotindex - 1（基准前的元素）
2. 遍历处理
1. 当 arr[j] <= 基准时将 `arr[j]` 交换到 `i` 的位置，扩展“小于等于基准”的区域。`i += 1`，右移边界，确保下一符合条件元素能继续填充到正确位置。
2. 当 arr[j] > 基准时不交换，保留在右侧，等待后续处理
3. 遍历完成后，将基准交换到 i 的位置，形成分区：[≤基准] + [基准] + [>基准]
4. 最后递归处理

4.总结

冒泡排序是经典的入门排序算法，适合学习使用；快速排序中Lomuto分区方案很容易理解，实现起来简单，更直观，但效率稍低；Hoare速度更快（交换次数少），效率更高，但实现细节更复杂。