当前位置： 首页 > article >正文

数据结构与算法面试专题——桶排序

article 2025/2/27 20:35:26

引入

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序与之前提到的排序的本质区别，就是它是不基于比较的排序。 桶排序是一种基于分治思想的排序算法，它将数据分布到有限数量的桶中，每个桶再分别排序，最后按顺序合并。

实现原理

  1. 确定桶的数量和范围：根据数据的取值范围和数据量，计算需要的桶的数量。每个桶代表一个特定的区间范围。

  2. 分配数据到桶：遍历待排序的数据，根据每个数据的值将其分配到相应的桶中。

  3. 对每个桶进行排序：可以使用其他排序算法（如插入排序、快速排序等）对每个桶中的数据进行排序。

  4. 收集结果：按照桶的顺序，将所有桶中的数据依次取出，合并到一个数组中，得到最终的有序结果。

优点

  • 高效：对于数据分布均匀的情况，桶排序的时间复杂度接近 O(n)。

  • 稳定：桶排序是稳定的排序算法，能保持相等元素的原始相对顺序。

桶排序的时间复杂度为什么是 O(n) 呢？
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。
当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

缺点

  • 数据分布要求高：如果数据分布不均匀，可能导致部分桶过载，影响整体效率。

  • 空间消耗大：需要额外的空间存储桶，对于大规模数据，空间复杂度可能较高。

应用场景

  • 数据分布均匀且范围明确：当待排序数据分布均匀且范围已知时，桶排序能充分利用数据特性，实现高效排序。

  • 高效内部排序算法可用：若桶内排序可选用计数排序、基数排序等线性时间复杂度的排序算法，桶排序的整体效率将显著提升。

  • 对稳定性有要求：在需要保持相等元素原始相对顺序的场景中，桶排序的稳定性使其成为理想选择。

桶排序看起来很优秀，那它是不是可以替代我们之前讲的排序算法呢？
答案当然是否定的。实际上，桶排序对要排序数据的要求是非常苛刻的。

首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

下面我们重点看桶排序思想下的排序：计数排序 & 基数排序

注意：

  1. 桶排序思想下的排序都是不基于比较的排序
  2. 时间复杂度为O(N)，额外空间负载度O(M)
  3. 应用范围有限，需要样本的数据状况满足桶的划分

计数排序（Counting Sort）

计数排序计数排序其实是桶排序的一种特殊情况，适用于整数或有限范围内的数据排序。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

代码示例

下面是一个简单的计数排序案例

public void countSort(int[] arr) {
    // 如果数组为空或长度小于2，无需排序，直接返回
    if (arr == null || arr.length < 2) {
        return;
    }

    // 找出数组中的最大值，用于确定计数桶的大小
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }

    // 创建计数桶，索引代表数字，值代表该数字在数组中的出现次数
    int[] bucket = new int[max + 1];

    // 遍历数组，统计每个数字的出现次数
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++; // 例如，如果数组中有数字5，那么bucket[5]会增加1
    }

    // 根据计数桶中的计数，将数字按顺序重新放回原数组
    int i = 0; // 用于跟踪原数组中的当前位置
    for (int j = 0; j < bucket.length; j++) {
        // 当前数字为j，出现次数为bucket[j]
        while (bucket[j]-- > 0) {
            arr[i++] = j; // 将数字j放入原数组的正确位置
        }
    }
}

 当然，我们还可以如下实现：

// 计数排序，适用于非负整数数组
public void countingSort(int[] a, int n) {
    if (n <= 1) return; // 如果数组长度小于等于1，无需排序
    
    // 查找数组中数据的范围
    int max = a[0];
    for (int i = 1; i < n; ++i) {
        if (max < a[i]) { // 找到数组中的最大值
            max = a[i];
        }
    }
    
    // 申请一个计数数组 c，下标大小从 0 到 max
    int[] c = new int[max + 1];
    for (int i = 0; i <= max; ++i) {
        c[i] = 0; // 初始化计数数组为0
    }
    
    // 计算每个元素的个数，放入计数数组 c 中
    for (int i = 0; i < n; ++i) {
        c[a[i]]++; // 统计每个元素出现的次数
    }
    
    // 依次累加，得到当前元素排序后的位置
    for (int i = 1; i <= max; ++i) {
        c[i] = c[i-1] + c[i]; // 累加，得到每个元素的累计个数
    }
    
    // 创建临时数组 r，存储排序之后的结果
    int[] r = new int[n];
    
    // 根据计数数组计算排序的关键步骤
    for (int i = n - 1; i >= 0; --i) { // 逆序遍历原数组
        int index = c[a[i]] - 1; // 获取当前元素在临时数组中的位置
        r[index] = a[i]; // 将元素放入临时数组
        c[a[i]]--; // 减少计数，确保相同元素的位置正确
    }
    
    // 将临时数组的结果拷贝回原数组
    for (int i = 0; i < n; ++i) {
        a[i] = r[i]; // 更新原数组为排序后的结果
    }
}

假设输入数组为 [3, 6, 4, 1, 3, 4, 1, 4]，经过计数排序后：

  • 最大值为6，计数桶大小为7（索引0-6）。

  • 计数桶统计结果为：

    • bucket[0] = 0

    • bucket[1] = 2

    • bucket[2] = 0

    • bucket[3] = 2

    • bucket[4] = 3

    • bucket[5] = 0

    • bucket[6] = 1

  • 重建数组时，按顺序将数字放入原数组：

    • 1出现2次，写入索引0和1。

    • 3出现2次，写入索引2和3。

    • 4出现3次，写入索引4、5和6。

    • 6出现1次，写入索引7。

  • 排序后的数组为 [1, 1, 3, 3, 4, 4, 4, 6]。

实现原理

  1. 确定数据范围：找到待排序数据的最大值和最小值，确定数据的范围。

  2. 创建计数数组：创建一个计数数组，用于统计每个数据出现的次数。

  3. 统计次数：遍历待排序数据，统计每个数据在计数数组中的出现次数。

  4. 重建排序结果：根据计数数组中的次数，从大到小或从小到大重建排序结果。

优点

线性时间复杂度：计数排序的时间复杂度为 O(n + k)，其中 n 是数据量，k 是数据的范围。

稳定：计数排序是稳定的排序算法，能保持相等元素的原始相对顺序。

缺点

适用范围有限：计数排序只适用于整数或有限范围内的数据，不适用于负数和浮点数。

空间复杂度高：需要额外的空间存储计数数组，当数据范围较大时，空间复杂度较高。

应用场景

整数排序：适用于整数数据的排序，尤其是数据范围较小的情况。

字符串排序：可以用于固定长度的字符串排序，通过字符位来排序。

基数排序（Radix Sort）

基数排序是一种非比较型整数排序算法，它按照数字的每一位进行比较和交换。基数排序的核心思想是将待排序数组分成若干个段，然后对每个段进行局部排序。

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

代码示例

// 该基数排序方法仅适用于非负数
public void radixSort(int[] arr) {
    // 如果数组为空或长度小于2，无需排序，直接返回
    if (arr == null || arr.length < 2) {
        return;
    }
    // 调用基数排序的辅助方法，传入起始索引、结束索引和最大位数
    radixSort(arr, 0, arr.length - 1, maxbits(arr));
}

// 计算数组中最大值的位数
public int maxbits(int[] arr) {
    int max = Integer.MIN_VALUE; // 初始化最大值
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]); // 找出数组中的最大值
    }
    int res = 0; // 记录最大值的位数
    while (max != 0) { // 通过不断除以10来统计位数
        res++;
        max /= 10;
    }
    return res; // 返回最大值的位数
}

// 对数组的子数组进行基数排序
// arr: 待排序数组
// L: 子数组的起始索引
// R: 子数组的结束索引
// digit: 数组中最大值的位数
public void radixSort(int[] arr, int L, int R, int digit) {
    final int radix = 10; // 基数为10，因为使用十进制
    int i = 0, j = 0;
    // 辅助数组，用于存储排序过程中的中间结果
    int[] help = new int[R - L + 1];
    // 根据数字的位数循环处理每一位
    for (int d = 1; d <= digit; d++) { // d 表示当前处理的是第几位（从低位到高位）
        int[] count = new int[radix]; // 计数数组，统计当前位各个数字的出现次数
        // 统计当前位各个数字的出现次数
        for (i = L; i <= R; i++) {
            j = getDigit(arr[i], d); // 获取当前数字的第d位数字
            count[j]++;
        }
        // 计算计数数组的前缀和，用于确定每个数字的位置
        for (i = 1; i < radix; i++) {
            count[i] = count[i] + count[i - 1];
        }
        // 将数字按照当前位的大小放入辅助数组
        for (i = R; i >= L; i--) { // 从右到左遍历原数组，保证排序的稳定性
            j = getDigit(arr[i], d); // 获取当前数字的第d位数字
            help[count[j] - 1] = arr[i]; // 将数字放入辅助数组的正确位置
            count[j]--; // 减少计数，确保相同位的数字顺序正确
        }
        // 将辅助数组中的有序数字复制回原数组
        for (i = L, j = 0; i <= R; i++, j++) {
            arr[i] = help[j];
        }
    }
}

// 获取数字x的第d位上的数字
public int getDigit(int x, int d) {
    return ((x / ((int) Math.pow(10, d - 1))) % 10); // 例如，x=123，d=2，返回 2
}

实现原理

  1. 确定最大位数：找到待排序数据中的最大值，确定最大位数。

  2. 按位排序：从最低位开始，按照每一位对数组进行排序。可以使用计数排序或桶排序作为子排序算法。

  3. 合并结果：按照位数顺序，逐步合并排序结果，最终得到完全排序的数组。

优点

线性时间复杂度：基数排序的时间复杂度为 O(d * (n + k))，其中 d 是数字中的最大位数，n 是数组的长度，k 是每一位的取值范围。

稳定：基数排序是稳定的排序算法，前一位的排序结果在下一位排序中不会改变。

缺点

空间复杂度高：需要额外的空间来存储中间结果，空间复杂度较高，尤其在处理大数据时。

适用范围有限：基数排序适合数值或字符串等可以按位操作的数据，不适合复杂数据类型。

应用场景

大规模整数排序：适用于大规模的整数数据排序，尤其是位数不多且取值范围有限的情况。

字符串排序：可以用于固定长度的字符串排序，通过字符位来排序。

图像处理中的颜色排序：基数排序可用于按色彩通道分量进行排序。

排序算法总结

时间复杂度

额外空间复杂度

稳定性

选择排序

O(N^2)

O(1)

无

冒泡排序

O(N^2)

O(1)

有

插入排序

O(N^2)

O(1)

有

归并排序

O(N* logN)

O(N)

有

随机快排

O(N* logN)

O(logN)

无

堆排序

O(N* logN)

O(1)

无

计数排序

O(N)

O(M)

有

基数排序

O(N)

O(N)

有

  1. 不基于比较的排序，对样本数据有严格要求，不易改写
  2. 基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
  3. 基于比较的排序，时间复杂度的极限是O(N*logN)
  4. 时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
  5. 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并


http://www.kler.cn/a/563600.html

相关文章：

  • Remainder Problem CF1207F
  • 【PHP】Zend JIT（Just-In-Time）编译
  • 第2章_保护您的第一个应用程序
  • 深度学习中卷积层（Conv）、BN层（Batch Normalization）和 ReLU层（Rectified Linear Unit）的详细介绍
  • 初识XML
  • Unity XR-XR Interaction Toolkit开发使用方法（七）组件配置（XR Ray Interactor）
  • C++ STL（一）std::vector std::array
  • 玩机日记 15 使用Lucky申请半永久的ssl证书，并且替换阿里云的自签名证书
  • 集合与反射
  • 算法平台的开源框架
  • PDF处理控件Aspose.PDF教程：使用 Python 将 PDF 转换为 TIFF
  • 网页五子棋——项目测试
  • HarmonyOS Design 介绍
  • 基于ffmpeg+openGL ES实现的视频编辑工具-添加背景音乐（十）
  • vue+element-dialog：修改关闭icon / 遮罩层不能挡住弹窗 / 遮罩层不能遮挡元素
  • miqiu的分布式（三）：JVM本地锁失效的三大典型场景
  • Java集合设计模式面试题
  • 5 分钟用满血 DeepSeek R1 搭建个人 AI 知识库（含本地部署）
  • 十一、大数据治理平台总体功能架构
  • leetcode 541. 反转字符串 II 简单