SYSTEM
基数排序
src/content/notes/system/基数排序.md 基数排序
基数排序(Radix Sort):又叫桶排序和箱排序,借助多关键字排序的思想对单逻辑关键字进行排序的方法
计数排序其实是桶排序的一种特殊情况,当要排序的 n 个数据,所处的范围并不大的时候,比如最大值是 k,我们就可以把数据划分成 k 个桶,每个桶内的数据值都是相同的,省掉了桶内排序的时间
按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前
解释:先排低位再排高位,可以说明在高位相等的情况下低位是递增的,如果高位也是递增,则数据有序
实现思路:
- 获得最大数的位数,可以通过将最大数变为 String 类型,再求长度
- 将所有待比较数值(正整数)统一为同样的数位长度,位数较短的数前面补零
- 从最低位开始,依次进行一次排序
- 从最低位排序一直到最高位(个位 → 十位 → 百位 → … →最高位)排序完成以后,数列就变成一个有序序列
public class BucketSort {
public static void main(String[] args) {
int[] arr = new int[]{576, 22, 26, 548, 1, 3, 843, 536, 735, 43, 3, 912, 88};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void bucketSort(int[] arr) {
// 桶的个数固定为10个(个位是0~9),数组长度为了防止所有的数在同一行
int[][] bucket = new int[10][arr.length];
//记录每个桶中的有多少个元素
int[] elementCounts = new int[10];
//获取数组的最大元素
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
max = max > arr[i] ? max : arr[i];
}
String maxEle = Integer.toString(max);
//将数组中的元素放入桶中,最大数的位数相当于需要几次放入桶中
for (int i = 0, step = 1; i < maxEle.length(); i++, step *= 10) {
for (int j = 0; j < arr.length; j++) {
//获取最后一位的数据,也就是索引
int index = (arr[j] / step) % 10;
//放入具体位置
bucket[index][elementCounts[index]] = arr[j];
//存储每个桶的数量
elementCounts[index]++;
}
//收集回数组
for (int j = 0, index = 0; j < 10; j++) {
//先进先出
int position = 0;
//桶中有元素就取出
while (elementCounts[j] > 0) {
arr[index] = bucket[j][position];
elementCounts[j]--;
position++;
index++;
}
}
}
}
}
空间换时间
推荐视频:https://www.bilibili.com/video/BV1b7411N798?p=86
参考文章:https://www.toutiao.com/a6593273307280179715/?iid=6593273307280179715