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

引入

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独举行排序。桶内排完序之后，再把每个桶里的数据按照次序依次取出，组成的序列就是有序的了。
桶排序与之前提到的排序的本质区别，就是它是不基于比较的排序。 桶排序是一种基于分治思想的排序算法，它将数据分布到有限数目的桶中，每个桶再分别排序，最后按次序归并。
实现原理

• 确定桶的数目和范围：根据数据的取值范围和数据量，计算必要的桶的数目。每个桶代表一个特定的区间范围。
  
• 分配数据到桶：遍历待排序的数据，根据每个数据的值将其分配到相应的桶中。
  
• 对每个桶举行排序：可以使用其他排序算法（如插入排序、快速排序等）对每个桶中的数据举行排序。
  
• 收集结果：按照桶的次序，将所有桶中的数据依次取出，归并到一个数组中，得到最终的有序结果。
  

优点

• 高效：对于数据分布均匀的情况，桶排序的时间复杂度靠近 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) 的排序算法了。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
  下面我们重点看桶排序思想下的排序：计数排序 & 基数排序
   注意：
  

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

  计数排序（Counting Sort）

计数排序计数排序其实是桶排序的一种特殊情况，适用于整数或有限范围内的数据排序。当要排序的 n 个数据，所处的范围并不大的时间，好比最大值是 k，我们就可以把数据分别成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
计数排序只能用在数据范围不大的场景中，假如数据范围k比要排序的数据n大许多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，假如要排序的数据是其他范例的，要将其在不改变相对巨细的情况下，转化为非负整数。
代码示例

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

1. public void countSort(int[] arr) {
2.     // 如果数组为空或长度小于2，无需排序，直接返回
3.     if (arr == null || arr.length < 2) {
4.         return;
5.     }
7.     // 找出数组中的最大值，用于确定计数桶的大小
8.     int max = Integer.MIN_VALUE;
9.     for (int i = 0; i < arr.length; i++) {
10.         max = Math.max(max, arr[i]);
11.     }
13.     // 创建计数桶，索引代表数字，值代表该数字在数组中的出现次数
14.     int[] bucket = new int[max + 1];
16.     // 遍历数组，统计每个数字的出现次数
17.     for (int i = 0; i < arr.length; i++) {
18.         bucket[arr[i]]++; // 例如，如果数组中有数字5，那么bucket[5]会增加1
19.     }
21.     // 根据计数桶中的计数，将数字按顺序重新放回原数组
22.     int i = 0; // 用于跟踪原数组中的当前位置
23.     for (int j = 0; j < bucket.length; j++) {
24.         // 当前数字为j，出现次数为bucket[j]
25.         while (bucket[j]-- > 0) {
26.             arr[i++] = j; // 将数字j放入原数组的正确位置
27.         }
28.     }
29. }

复制代码

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

1. // 计数排序，适用于非负整数数组
2. public void countingSort(int[] a, int n) {
3.     if (n <= 1) return; // 如果数组长度小于等于1，无需排序
4.    
5.     // 查找数组中数据的范围
6.     int max = a[0];
7.     for (int i = 1; i < n; ++i) {
8.         if (max < a[i]) { // 找到数组中的最大值
9.             max = a[i];
10.         }
11.     }
12.    
13.     // 申请一个计数数组 c，下标大小从 0 到 max
14.     int[] c = new int[max + 1];
15.     for (int i = 0; i <= max; ++i) {
16.         c[i] = 0; // 初始化计数数组为0
17.     }
18.    
19.     // 计算每个元素的个数，放入计数数组 c 中
20.     for (int i = 0; i < n; ++i) {
21.         c[a[i]]++; // 统计每个元素出现的次数
22.     }
23.    
24.     // 依次累加，得到当前元素排序后的位置
25.     for (int i = 1; i <= max; ++i) {
26.         c[i] = c[i-1] + c[i]; // 累加，得到每个元素的累计个数
27.     }
28.    
29.     // 创建临时数组 r，存储排序之后的结果
30.     int[] r = new int[n];
31.    
32.     // 根据计数数组计算排序的关键步骤
33.     for (int i = n - 1; i >= 0; --i) { // 逆序遍历原数组
34.         int index = c[a[i]] - 1; // 获取当前元素在临时数组中的位置
35.         r[index] = a[i]; // 将元素放入临时数组
36.         c[a[i]]--; // 减少计数，确保相同元素的位置正确
37.     }
38.    
39.     // 将临时数组的结果拷贝回原数组
40.     for (int i = 0; i < n; ++i) {
41.         a[i] = r[i]; // 更新原数组为排序后的结果
42.     }
43. }

复制代码

假设输入数组为 [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]。
  

实现原理

• 确定数据范围：找到待排序数据的最大值和最小值，确定数据的范围。
  
• 创建计数数组：创建一个计数数组，用于统计每个数据出现的次数。
  
• 统计次数：遍历待排序数据，统计每个数据在计数数组中的出现次数。
  
• 重建排序结果：根据计数数组中的次数，从大到小或从小到大重建排序结果。
  

优点

线性时间复杂度：计数排序的时间复杂度为 O(n + k)，其中 n 是数据量，k 是数据的范围。
稳固：计数排序是稳固的排序算法，能保持相等元素的原始相对次序。
缺点

适用范围有限：计数排序只适用于整数或有限范围内的数据，不适用于负数和浮点数。
空间复杂度高：必要额外的空间存储计数数组，当数据范围较大时，空间复杂度较高。
应用场景

整数排序：适用于整数数据的排序，尤其是数据范围较小的情况。
字符串排序：可以用于固定长度的字符串排序，通过字符位来排序。
基数排序（Radix Sort）

基数排序是一种非比较型整数排序算法，它按照数字的每一位举行比较和交换。基数排序的核心思想是将待排序数组分成若干个段，然后对每个段举行局部排序。
基数排序对要排序的数据是有要求的，必要可以分割出独立的“位”来比较，而且位之间有递进的关系，假如 a 数据的高位比 b 数据大，那剩下的低位就不消比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
代码示例

1. // 该基数排序方法仅适用于非负数
2. public void radixSort(int[] arr) {
3.     // 如果数组为空或长度小于2，无需排序，直接返回
4.     if (arr == null || arr.length < 2) {
5.         return;
6.     }
7.     // 调用基数排序的辅助方法，传入起始索引、结束索引和最大位数
8.     radixSort(arr, 0, arr.length - 1, maxbits(arr));
9. }
11. // 计算数组中最大值的位数
12. public int maxbits(int[] arr) {
13.     int max = Integer.MIN_VALUE; // 初始化最大值
14.     for (int i = 0; i < arr.length; i++) {
15.         max = Math.max(max, arr[i]); // 找出数组中的最大值
16.     }
17.     int res = 0; // 记录最大值的位数
18.     while (max != 0) { // 通过不断除以10来统计位数
19.         res++;
20.         max /= 10;
21.     }
22.     return res; // 返回最大值的位数
23. }
25. // 对数组的子数组进行基数排序
26. // arr: 待排序数组
27. // L: 子数组的起始索引
28. // R: 子数组的结束索引
29. // digit: 数组中最大值的位数
30. public void radixSort(int[] arr, int L, int R, int digit) {
31.     final int radix = 10; // 基数为10，因为使用十进制
32.     int i = 0, j = 0;
33.     // 辅助数组，用于存储排序过程中的中间结果
34.     int[] help = new int[R - L + 1];
35.     // 根据数字的位数循环处理每一位
36.     for (int d = 1; d <= digit; d++) { // d 表示当前处理的是第几位（从低位到高位）
37.         int[] count = new int[radix]; // 计数数组，统计当前位各个数字的出现次数
38.         // 统计当前位各个数字的出现次数
39.         for (i = L; i <= R; i++) {
40.             j = getDigit(arr[i], d); // 获取当前数字的第d位数字
41.             count[j]++;
42.         }
43.         // 计算计数数组的前缀和，用于确定每个数字的位置
44.         for (i = 1; i < radix; i++) {
45.             count[i] = count[i] + count[i - 1];
46.         }
47.         // 将数字按照当前位的大小放入辅助数组
48.         for (i = R; i >= L; i--) { // 从右到左遍历原数组，保证排序的稳定性
49.             j = getDigit(arr[i], d); // 获取当前数字的第d位数字
50.             help[count[j] - 1] = arr[i]; // 将数字放入辅助数组的正确位置
51.             count[j]--; // 减少计数，确保相同位的数字顺序正确
52.         }
53.         // 将辅助数组中的有序数字复制回原数组
54.         for (i = L, j = 0; i <= R; i++, j++) {
55.             arr[i] = help[j];
56.         }
57.     }
58. }
60. // 获取数字x的第d位上的数字
61. public int getDigit(int x, int d) {
62.     return ((x / ((int) Math.pow(10, d - 1))) % 10); // 例如，x=123，d=2，返回 2
63. }

复制代码

实现原理

• 确定最大位数：找到待排序数据中的最大值，确定最大位数。
  
• 按位排序：从最低位开始，按照每一位对数组举行排序。可以使用计数排序或桶排序作为子排序算法。
  
• 归并结果：按照位数次序，逐步归并排序结果，最终得到完全排序的数组。
  

优点

线性时间复杂度：基数排序的时间复杂度为 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)
  有
  

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。