9.桶排序、排序总结相关题目分析 总览
笔记思维导图链接
参考左程云体系算法课程笔记
参考慕课网算法体系课程笔记
常见题目汇总：
题1：计数排序
题意
- 假设有n个样本数，数的范围是0-200，对这n个数进行排序
题解
- 范围小，故可以用计数排序，只需要准备200个桶，0-199，每个桶放一种样本数据，从小到大顺序
- 遍历一遍，将数据放到这200个桶类，再将200个桶依次倒出，就是最终排序的结果
代码实现
package class08;
public class Code03_CountSort {
// only for 0~200 value
public static void countSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 1. 找出样本的最大值，确定需要多少个桶
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
// 2. 每个样本对应创建一个桶，统计每个样本的次数
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
// 3. 将桶按照顺序，依次导出样本，即最终排序结果
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}
}
复杂度分析
- 入桶，是O(n), 出桶也是O(n),故总的时间复杂度为O(n)
题2：基数排序
题意
- 数据非负，且为10进制。
- 例如最大数是321三位，将这些数进行排序
题解
- 先确定最大数是几位数，确定要处理几轮的入桶出桶操作
- 比如最大位是321，先处理个位数，按照个数数先排序，再处理十位、按照十位数值排序，最后处理第三位百位，最终排序的结果就是有序的
- 对于每次的入桶出桶可以优化，无需每次都要准备10个桶，装0-9种数，可以只准备两个辅助count，help
- count，统计每个数出现的次数，类似计数排序，count[2]表示2出现的次数
- count’，统计前几个数一共出现的次数，count’[2]表示0，1，2一共出现的次数
- help数组处理最后从右往左遍历要处理的数，count’[2]出现5次，表明最后一个数应该出现在4位置，放置后，减一次，用来处理下个该位是2的数
- 每轮将help的结果交给原数组arr，每轮arr就排好序了
代码实现
package class08;
public class Code04_RadixSort {
// only for no-negative value
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
// 1. 获取最大数的位数
public static 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) {
res++;
max /= 10;
}
return res;
}
// arr[L..R]排序 , 最大值的十进制位的位数digit
public static 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++) { // 有多少位就进出几次
// 代码优化，省去10个桶，用两个数组count，count'来处理每次的进出操作
// 用count统计当前位的数，出现的次数，类似计数排序
int[] count = new int[radix]; // count[0..9]
for (i = L; i <= R; i++) { // 遍历要处理的每个数
// 103 1 3
// 209 1 9
j = getDigit(arr[i], d); // 找出当前位的数
count[j]++;
}
// 处理count'数组，统计每个数应该占多少位，即count'[2]表示0，1，2一共出现的次数
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
// 从右往左遍历，例如103，3一共出现了5次，则，103应该放在4位置
for (i = R; i >= L; i--) {
j = getDigit(arr[i], d);
help[count[j] - 1] = arr[i]; // count[j]出现的次数，表明要占j个位置，最后一个位置是j- 1
count[j]--;
}
// 对数组按照当前位进行排序，就是help数组最终放置的数的顺序
for (i = L, j = 0; i <= R; i++, j++) {
arr[i] = help[j];
}
}
}
// 获取第d位数的值
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
}