数据结构-排序

    //基数排序

    /**
     * 辅助函数:
     * 创建桶函数creatBuckets
     * 获取位数函数getMaxDigits
     * 获取指定位函数getDigit
     * @param arr
     */
    public static void radixSort(int[] arr){
        if (arr==null||arr.length==0){
            return;
        }
        //获取最大值以及位数
        int maxVal = Arrays.stream(arr).max().getAsInt();
        int maxDigits=getMaxDigits(maxVal);
        //创建桶集合
        List> buckets = creatBuckets(10);
        //根据个位,十位,等递增循环的分配元素到桶中,再重新取出,再分配
        for (int digit=1;digit<=maxDigits;digit++){
            //分配元素到桶中
            for (int num:arr){
                //取出指定数位的值
                int bucketIndex = getDigit(num, digit);
                buckets.get(bucketIndex).add(num);
            }
            //一个数位分配完毕,重新取出元素
            int index=0;
            for (List bucket:buckets){
                for (int num:bucket){
                    arr[index++]=num;
                }
                //清空每个桶
                bucket.clear();
            }
        }
    }
    //根据大小创建桶
    public static List> creatBuckets(int size){
        List> buckets =new ArrayList<>();
        for (int i=0;i());
        }
        return buckets;
    }
    //获取这个数有几位
    public static int getMaxDigits(int num){
        int digits=0;
        while (num>0){
            num/=10;
            digits++;
        }
        return digits;
    }
    /**
     *
     * @param num 数字
     * @param digit 目标位1表示个位,2表示十位,以此类推
     * @return 获取数字在其指定位上的数字
     */
    public static int getDigit(int num,int digit){
        //对数取10的余数得到的就是个位上的值,获取地n位的值就应该让此数除以10的n-1次方
        return (num/(int)Math.pow(10,digit-1))%10;
    }
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

    public static void bucketSort(int[] arr){
        //1.初始化桶,找到最大最小值
        int minValue=Integer.MIN_VALUE;
        int maxValue=Integer.MAX_VALUE;
        for (int num:arr){
            minValue=Math.min(minValue,num);
            maxValue=Math.max(maxValue,num);
        }
        //2.初始化桶,创建桶的集合
        int bucketSize=(maxValue-minValue)/arr.length-1;
        ArrayList> buckets = new ArrayList<>(bucketSize);
        //初始化桶集合
        for (int i=0;i());
        }
        //3.分配元素到桶
        for (int num:arr){
            //计算元素所属桶的索引
            int bucketIndex=(num-minValue)/bucketSize;
            //将元素添加到对应的桶中
            buckets.get(bucketIndex).add(num);
        }
        //4.对每个桶进行排序
        for (ArrayList bucket:buckets){
            Integer[] array = (Integer[]) bucket.toArray();
            int[] array1 = Arrays.stream(array).mapToInt(Integer::intValue).toArray();
            //选择排序
            insertSort(array1);
        }
        //5.合并桶内元素
        int index = 0;
        for (ArrayList bucket:buckets){
            for (int num:bucket){
                arr[index++]=num;
            }
        }
    }
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

    public static void countSort(int[] arr){
        //获取数组最大和最小值
        int maxVal = Arrays.stream(arr).max().getAsInt();
        int minVal = Arrays.stream(arr).min().getAsInt();
        //初始化数组
        int range = maxVal - minVal + 1;
        int[] count = new int[range];
        //统计每个元素出现次数
        for (int num:arr){
            count[num-minVal]++;
        }
        //计算前驱元素累计次数
        for (int i=1;i=0;i--){
            int num=arr[i];
            //元素减去偏移量是在count数组的下标,对应count[countIndex]是,小于countIndex值的累加量
            int countIndex = num - minVal;
            //在最终排序序列中的下标是count[countIndex]-1;
            resultSort[--count[countIndex]]=num;
        }
        //将排序结果复制回原来的数组中
        System.arraycopy(resultSort,0,arr,0,arr.length);
    }
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