排序算法

冒泡排序

/// Sort a slice using bucket sort algorithm.
///
/// Time complexity is `O(n + k)` on average, where `n` is the number of elements,
/// `k` is the number of buckets used in process.
///
/// Space complexity is `O(n + k)`, as it sorts not in-place.
pub fn bucket_sort(arr: &[usize]) -> Vec<usize> {
    if arr.is_empty() {
        return vec![];
    }

    let max = *arr.iter().max().unwrap();
    let len = arr.len();
    let mut buckets = vec![vec![]; len + 1];

    for x in arr {
        buckets[len * *x / max].push(*x);
    }

    for bucket in buckets.iter_mut() {
        super::insertion_sort(bucket);
    }

    let mut result = vec![];
    for bucket in buckets {
        for x in bucket {
            result.push(x);
        }
    }

    result
}

桶排序

/// Sort a slice using bucket sort algorithm.
///
/// Time complexity is `O(n + k)` on average, where `n` is the number of elements,
/// `k` is the number of buckets used in process.
///
/// Space complexity is `O(n + k)`, as it sorts not in-place.
/// 插入排序，用于对各个桶内部进行排序
fn insertion_sort(arr: &mut [usize]) {
    for i in 1..arr.len() {
        let mut j = i;
        while j > 0 && arr[j - 1] > arr[j] {
            arr.swap(j - 1, j);
            j -= 1;
        }
    }
}

/// 桶排序函数
pub fn bucket_sort(arr: &[usize]) -> Vec<usize> {
    if arr.is_empty() {
        return vec![];
    }

    let max = *arr.iter().max().unwrap();
    
    // 如果最大值为 0，说明数组中所有元素都是 0，直接返回即可
    if max == 0 {
        return arr.to_vec();
    }

    let len = arr.len();
    // 创建 len + 1 个桶，防止 len * max / max = len 时越界
    let mut buckets = vec![vec![]; len + 1];

    for &x in arr {
        // 计算当前元素应该放入哪个桶
        let index = len * x / max;
        buckets[index].push(x);
    }

    // 对每个桶进行排序
    for bucket in buckets.iter_mut() {
        insertion_sort(bucket);
    }

    // 收集排序后的结果
    let mut result = Vec::with_capacity(len);
    for bucket in buckets {
        for x in bucket {
            result.push(x);
        }
    }

    result
}

快速排序

pub fn quick_sort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }
    
    // 获取分区点的索引
    let pivot_index = partition(arr);
    
    // 递归对分区点左侧和右侧的子数组进行排序
    // 注意：pivot_index 处的元素已经处于正确的位置，不需要参与后续排序
    quick_sort(&mut arr[0..pivot_index]);
    quick_sort(&mut arr[pivot_index + 1..]);
}

/// 分区函数（Lomuto 分区方案）
/// 选择数组的最后一个元素作为基准值（pivot），并将小于等于基准值的元素移到左边
fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let len = arr.len();
    let pivot_index = len - 1;
    let mut i = 0; // 记录小于等于基准值的元素的边界索引

    for j in 0..pivot_index {
        if arr[j] <= arr[pivot_index] {
            arr.swap(i, j);
            i += 1;
        }
    }
    
    // 将基准值交换到其最终的正确位置
    arr.swap(i, pivot_index);
    i
}

归并排序

参考资料 图解排序算法：归并排序 通过图文理解归并排序的分治拆分与有序合并过程 cnblogs.com/chengxiao/p/6194356.html

pub fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
    let len = arr.len();
    if len <= 1 {
        return;
    }

    let mid = len / 2;
    
    // 分治：递归排序左半部分和右半部分
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);

    // 合并：将两个有序子切片合并
    merge(arr, mid);
}

/// 辅助合并函数
fn merge<T: Ord + Clone>(arr: &mut [T], mid: usize) {
    // 拷贝左右两部分数据，用于合并时的比较
    let left = arr[..mid].to_vec();
    let right = arr[mid..].to_vec();

    let mut l = 0; // 左侧数组的索引
    let mut r = 0; // 右侧数组的索引
    let mut i = 0; // 原数组的索引

    // 比较并合并
    while l < left.len() && r < right.len() {
        if left[l] <= right[r] {
            arr[i] = left[l].clone();
            l += 1;
        } else {
            arr[i] = right[r].clone();
            r += 1;
        }
        i += 1;
    }

    // 将左侧剩余的元素复制回原数组
    while l < left.len() {
        arr[i] = left[l].clone();
        l += 1;
        i += 1;
    }

    // 将右侧剩余的元素复制回原数组
    while r < right.len() {
        arr[i] = right[r].clone();
        r += 1;
        i += 1;
    }
}

堆排序

参考资料 图解排序算法：堆排序 通过图文理解堆排序的建堆、调整与排序过程 cnblogs.com/chengxiao/p/6129630.html

pub fn heap_sort<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    if n <= 1 {
        return;
    }

    // Step 1: 构建最大堆（从最后一个非叶子节点开始往上调整）
    // 最后一个非叶子节点的索引为 n / 2 - 1
    for i in (0..n / 2).rev() {
        heapify(arr, n, i);
    }

    // Step 2: 依次将堆顶元素（最大值）交换到数组末尾，并重新调整堆
    for i in (1..n).rev() {
        arr.swap(0, i); // 将当前最大值移到未排序部分的末尾
        heapify(arr, i, 0); // 重新调整剩余部分使其满足最大堆
    }
}

/// 辅助函数：调整堆（下滤操作，使以 i 为根的子树满足最大堆性质）
/// n 是当前有效堆的大小，i 是需要调整的节点索引
fn heapify<T: Ord>(arr: &mut [T], n: usize, mut i: usize) {
    loop {
        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);
            i = largest; // 更新 i，继续循环（代替递归，避免栈溢出）
        } else {
            break; // 已经满足最大堆性质，退出
        }
    }
}