桶排序 — 计数排序和基数排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了桶排序 — 计数排序和基数排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

计数排序
int类型数组，其中存的是员工的年龄。比如说16 - 150。对于这样的数据来讲，数据状况是受限的。此时如果将数组从小到大进行排序，该如果实现？
这个实现很简单，实现一个统计数组范围从 0 ~ 150，新数组下标对应着老数组的值，新数组的值对应着老数组相同值的个数，遍历新数组找到个数不为0的元素，按顺序放回到老数组即可。整体时间复杂度O(N)。

public void countSort(int[] arr) {
            int max = Integer.MIN_VALUE;
            //选出最大值
            for (int i = 0; i < arr.length; i++) {
                Math.max(max, arr[i]);
            }
            //数组长度取年龄最大值 + 1
            int[] count = new int[max + 1];

            for (int j = 0; j < arr.length; j++) {
                count[arr[j]]++;
            }

            int i = 0;
            for (int k = 0; k < count.length; k++) {
                while (count[k]-- > 0) {
                    arr[i++] = k;
                }
            }
        }

这种排序称为计数排序，计数排序所用的思想是桶排序的思想，桶就是容器的意思，题中的年龄就是桶。

这样来看，从排序特征上来分大致可分为两类：不基于比较的排序和比较排序。其中桶排序就是不基于比较的一个。
计数排序不是基于比较，根据年龄，放入不同的桶中，最后从桶中获取，一个比较行为都没有。
不基于比较的排序，一定是数据范围比较特殊。所以，不基于比较的排序的扩展性相较于基于比较的排序来讲，可扩展性比较小，因为基于比较的排序实现了一个对数器之后，所有的基于比较的排序都可以用，而不基于比较的不可以。需要根据具体的样本特征来具体的分析。

基数排序
基数排序对数据范围的约束大概在非负的，用十进制表示的数（负的找到最小值，数组整体加成正数也行）。
假设int[] {103，13，27，25，17，9}。
先将数组中最大值103找出来，算出十进制的位数（几次能将10除完），得出是3。
将其余元素不满3位的高位补0，补充之后是{103，013，027，025，017，009}。
准备0 ~ 9一共10个桶，数组从左往右，根据个位数放进对应下标的桶中。
桶排序 — 计数排序和基数排序
放入后，从0桶开始，依次倒出并清空桶（根据个位数排序）。

根据十位数大小，再次放入桶中。

再次倒出桶中元素，并清空桶。

第三次，将百位数放入桶中后再次倒出。

倒出后，数组有序{009，013，017，025，027，103}
代码实现：
代码中，没有使用队列的方式来创建桶，而是用了另一种方式。文章来源地址https://www.toymoban.com/news/detail-465329.html

 public static void RadixSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            radixSort(arr, 0, arr.length - 1, maxbits(arr));
        }

        // L。。。R进行排序
        public static void radixSort(int[] arr, int L, int R, int digit) {
            final int radix = 10;
            int i = 0, j = 0;
            // 有多少个数准备多少个辅助空间
            int[] help = new int[R - L + 1];
            for (int l = 1; l < digit; l++) {
                int[] count = new int[radix];

                for (i = L; i <= R; i++) {
                    j = getDigit(arr[i], l);
                    //统计每个数字出现的次数
                    count[j]++;
                }
                //求出所有次数的前缀和
                for (i = 1; i < radix; i++) {
                    count[i] = count[i] + count[i - 1];
                }
                //从尾向前遍历
                for (i = R; i >= L; i--) {
                    //再次获取当前数的各位十位百位数。
                    j = getDigit(arr[i], l);
                    //count[j] 代表  <= arr[i]的数当前一共出现了 count[j]次
                    //count[j] - 1，代表了当前arr[i]在help数组中的位置
                    //因为是从右向前遍历，所以代表当前数要落在<= arr[i]的那些count[j]中的最右边 
                    help[count[j] - 1] = arr[i];
                    //对应位置数量 - 1
                    count[j]--;
                }

            }
        }

        public static int maxbits(int[] arr) {

            int max = Integer.MIN_VALUE;
            //找到数组中最大值
            for (int i = 0; i < arr.length; i++) {
                Math.max(max, arr[i]);
            }
            int res = 0;
            //根据最大值/10，找到十进制位数
            while (max != 0) {
                res++;
                max /= 10;
            }
            return res;
        }

        //d = 1,2,3 求出x的个位十位百位
        public static int getDigit(int x, int d) {
            return ((x / ((int) Math.pow(10, d - 1))) % 10);
        }