数据结构与算法之排序算法-(计数,桶,基数排序)-三、基数排序

稳定性：稳定

时间复杂度：O(n * k)

额外空间复杂度：O(n * k)

① 基数排序

???? 算法思想：

基数排序的基本思想：基数排序的算法思想是，将整数按照位数分别切割成不同的数字。

当每次将数组中的数据按位数分割结束后，分别放入以位数为单位的"桶"中。

然后遍历桶，按照顺序将元素取出，再重新进行分割，入桶等操作，直到分割位数的次数达到了数组中位数最高的元素的限制，排序结束。

???? 代码示例：

        public static int[] radioSort(int[] arr) {
        if(arr == null || arr.length < 2) return arr;
        int n = arr.length;
        int max = arr[0];
        // 找出最大值,计算最大值是几位数
        for (int i = 1; i < n; i++) {
            if(max < arr[i]) max = arr[i];
        }
        int num = 1;
        while (max / 10 > 0) {
            num++;
            max = max / 10;
        }
        // 创建10个桶
        ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10);
        for (int i = 0; i < 10; i++) {
            bucketList.add(new LinkedList<Integer>());
        }
        // 进行排序
        for (int i = 1; i <= num; i++) {
            for (int j = 0; j < n; j++) {
                int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;
                bucketList.get(radio).add(arr[j]);
            }
            int k = 0;
            for (int j = 0; j < 10; j++) {
                for (Integer t : bucketList.get(j)) {
                    arr[k++] = t;
                }
            }
        }
        return arr;
    }

那么这篇关于计数排序，桶排序，基数排序的文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦