排序算法

冒泡排序

/// 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
}