← 返回学习路线

SYSTEM

基数排序

Java基础基数排序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