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

引入

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

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

实现原理

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

优点

高效：对于数据分布均匀的情况，桶排序的时间复杂度接近 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大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

代码示例

下面是一个简单的计数排序案例，仅适用于数字范围在0到200之间的数组

// 该计数排序方法仅适用于数字范围在0到200之间的数组
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 到 maxint[] 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]; // 更新原数组为排序后的结果}
}

实现原理

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

优点

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

实现原理

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

优点

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