0%

基数排序

发表于 分类于

文章字数：265,阅读全文大约需要1分钟

基数排序适用于整形排序，将数据按照位数切割成不同的数字，按照权重依次桶排序。

解析

第一次排序，位数最大的在后面，小的在前面。
第二次排序十位上的大的向后
第三次百位大的向后
…
越在后面进行的排序作用就越大，因为可以推翻之前的排序结果。位数越靠前代表的值也越大，所以从个位开始到最高位。

本质上是桶排序的增强版，不需要那么多的桶。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public static void sort(int[] arr){
    int length = arr.length;

    //最大值
    int max = arr[0];
    for(int i = 0;i < length;i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    //当前排序位置
    int location = 1;

    //桶列表
    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();

    //长度为10 装入余数0-9的数据
    for(int i = 0; i < 10; i++){
        bucketList.add(new ArrayList());
    }

    while(true)
    {
        //判断是否排完
        int dd = (int)Math.pow(10，(location - 1));
        if(max < dd){
            break;
        }

        //数据入桶
        for(int i = 0; i < length; i++)
        {
            //计算余数 放入相应的桶
            int number = ((arr[i] / dd) % 10);
            bucketList.get(number).add(arr[i]);
        }

        //写回数组
        int nn = 0;
        for (int i=0;i<10;i++){
            int size = bucketList.get(i).size();
            for(int ii = 0;ii < size;ii ++){
                arr[nn++] = bucketList.get(i).get(ii);
            }
            bucketList.get(i).clear();
        }
        location++;
    }
}