桶排序 Bucket Sort

前文介绍的几种排序算法都是基于比较元素之间的关系 (comparison based), 这对于像字符串或者其它自定义数据类型也是有效的, 只需要实现 PartialOrd 即可, 具有通用性.

桶排序是基于元素的数值大小, 而不是比较关系 (non-comparison based), 这类算法只适合整数和定长的字符串.

桶排序也是一种线性排序方法. 它将元素分配到多个桶中, 然后对每个桶单独进行排序.

桶排序的步骤

  1. 根据原数组中元素的数值范围, 将数组分成 m 个桶, 每个桶将存放一定数值区间的元素, 而且这些数值区间有序不重叠
  2. 按顺序遍历数组, 将元素按数值大小放到目标桶中, 每个桶会存放相近或者相同的元素
  3. 使用插入排序等算法对每个桶排序
  4. 按照桶的顺序, 将每个桶中的元素依次存储到原数组

bucket sort

桶排序的实现

#![allow(unused)]
fn main() {
use crate::shell_sort::shell_sort;

/// 桶排序, 使用插入排序来处理每个桶.
#[allow(clippy::cast_sign_loss)]
pub fn bucket_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }

    // 对于插入排序来说, 元素的个数在这个范围内的效率比较高.
    let bucket_elements: usize = 72;
    let min_num: i32 = arr.iter().min().copied().unwrap_or_default();
    let max_num: i32 = arr.iter().max().copied().unwrap_or_default();
    // 计算数值范围.
    let range: i32 = max_num - min_num;
    // 计算桶的个数, 我们假设元素的数值是均匀分布的.
    // 这样的话就可以确定每个桶要存储的数值范围.
    // 尽可能把数值相近的元素放在一起.
    let bucket_count: usize = range as usize / bucket_elements + 1;
    // 创建一系列的桶.
    let mut buckets: Vec<Vec<i32>> = vec![vec![]; bucket_count];

    // 遍历数组, 将元素分配到每个桶中.
    // 这里是按数组的原有顺序插入到桶中的, 有相同数值的元素也会依照原先的顺序放置到同一个桶.
    for &num in arr.iter() {
        // 计算这个元素值处于哪个数值段, 并确定该放到哪个桶.
        let bucket_index: usize = (num - min_num) as usize / bucket_elements;
        buckets[bucket_index].push(num);
    }

    // 对每一个桶单独排序, 按照假设, 每个桶中的元素个数都比较少,
    // 使用插入排序可以发挥它的优势.
    // 并且插入排序是稳定排序, 所以该桶排序算法也是稳定排序.
    let mut index: usize = 0;
    for mut bucket in buckets {
        insertion_sort(&mut bucket);
        // 将这个桶中的元素合并到原先的数组中.
        arr[index..(index + bucket.len())].copy_from_slice(&bucket);
        index += bucket.len();

/// 其思路是, 先将前 i 个元素调整为增序的, 随着 i 从 0 增大到 n, 整个序列就变得是增序了.
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    let len = arr.len();
    for i in 1..len {
        for j in (1..=i).rev() {
            if arr[j - 1] > arr[j] {
                arr.swap(j - 1, j);
            } else {
                break;
            }
        }
    }
}
}

桶排序的特点

  • 如果给每个桶做排序是的算法是稳定排序的, 那么桶排序算法就是稳定排序
  • 时间复杂度是 O(n), 空间复杂度是 O(n + m)
  • 比快速排序还要快

使用希尔排序

上面的代码中, 我们使用插入排序来给每个桶排序, 这次我们换成希尔排序. 后者可以支持排序更多的元素, 依然保持较好的性能.

#![allow(unused)]
fn main() {
}

/// 桶排序的另一种实现, 使用希尔排序来处理每个桶.
#[allow(clippy::cast_sign_loss)]
pub fn shell_bucket_sort(arr: &mut [i32]) {
    if arr.is_empty() {
        return;
    }

    // 对于希尔排序来说, 元素的个数在这个范围内的效率比较高.
    let bucket_elements: usize = 72 * 2;

    let min_num: i32 = arr.iter().min().copied().unwrap_or_default();
    let max_num: i32 = arr.iter().max().copied().unwrap_or_default();
    let range: i32 = max_num - min_num;
    let bucket_count: usize = range as usize / bucket_elements + 1;
    let mut buckets: Vec<Vec<i32>> = vec![vec![]; bucket_count];

    for &num in arr.iter() {
        let bucket_index: usize = (num - min_num) as usize / bucket_elements;
        buckets[bucket_index].push(num);
    }
    let mut index: usize = 0;
    for mut bucket in buckets {
        shell_sort(&mut bucket);
        arr[index..(index + bucket.len())].copy_from_slice(&bucket);
        index += bucket.len();

/// Shell sort is a simple extension to insertion sort that allows exchanging
/// elements that far apart.
///
/// It produces partially sorted array (h-sorted array).
pub fn shell_sort<T>(arr: &mut [T])
where
    T: PartialOrd,
{
    const FACTOR: usize = 3;
    let len = arr.len();

    // 计算第一个 gap 的值, 大概是 len/3
    let mut h = 1;
    while h < len / FACTOR {
        h = FACTOR * h + 1;
    }

    while h >= 1 {
        // 使用插入排序, 将 `arr[0..h]` 排序好
        for i in h..len {
            let mut j = i;
            while j >= h && arr[j - h] > arr[j] {
                arr.swap(j - h, j);
                j -= h;
            }
        }

        h /= FACTOR;
    }
}
}