计数排序和桶排序的实现

计数排序

应用范围

• 局限于在一定范围内的整数类型进行排序

实现原理

• 获取最大最小值 （优化范围太大）
• 创建和原数组大小相同的结果数组容器 (收集排序后的容器)
• 根据最值间距创建对应大小的统计数组
• 遍历原数组然后对应下标++ （构建统计数组）
• 将统计数组转化为统计和数组 (实现稳定排序)
• 逆序遍历原数组填充结果数组，并给匹配的统计和数组的下标减1

实现代码如下

    /**
     * 计数排序 -> 对一定范围内的整数进行排序
     * 思路：
     * - 获取数组中的最大值
     * - 构造0 -> 最大值的数组
     * - 遍历数字是多少对应下标+1
     * - 遍历数组，数字多少则输出多少次对应下标
     * <p>
     * 优化：
     * - 考虑值的最小值，需要获取最大值和最小值的一段间距充当统计数组的大小
     * - 对分数段相同的如何进行稳定排序？
     * - 对统计数组进行改造，对应下标的值改为前面所有值的和，这么做是为了值的具体排名，
     * 然后在元素进行遍历的时候就可以通过对该值-1来分辨相同元素前后了
     * <p>
     * <p>
     * 时间复杂度是 ： O(n+m) -> n: 原数据大小 m: 最值直接的间距
     * 空间复杂度： 不考虑结果容器为O(m)
     *
     * @param arr
     */
    public static void countingSort(int[] arr) {
        int[] result = new int[arr.length];
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = max < arr[i] ? arr[i] : max;
            min = min > arr[i] ? arr[i] : min;
        }
        //获取间距
        int space = max - min;

        int[] tmp = new int[space + 1];

        for (int i : arr) {
            tmp[i - min]++;
        }
        //对统计数组进行变形,目标是为方便获取相同数据的顺序
        for (int i = 0; i < tmp.length - 1; i++) {
            tmp[i + 1] += tmp[i];
        }
        //遍历原数据
        for (int i : arr) {
            //填充到结果数组tmp[i-min] -> 表示排序位置
            result[tmp[i - min] - 1] = i;
            //设置之后统计数-1，确定后面相同元素的位置
            tmp[i - min]--;
        }
        System.out.println(Arrays.toString(result));
    }

桶排序

时间复杂度 O（n），当桶分配不均匀时会降低到 O(nlogn) ，空间复杂度O (n)

• 为了优化计数排序的整数，以及范围问题，将容器化分到多个区间桶中
• 桶中元素各自排序
• 按顺序遍历即可

    public static void bucketSort(double[] arr) {
        //获取最大值最小值
        double max = arr[0];
        double min = arr[0];
        for (double v : arr) {
            max = max < v ? v : max;
            min = min > v ? v : min;
        }

        //计算区间跨度
        double d = max - min;

        //桶数量，默认为原数组数量
        int bucketNum = arr.length;

        //初始化桶
        ArrayList<LinkedList<Double>> bucketList = Lists.newArrayList();

        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(Lists.newLinkedList());
        }

        //将元素放入对应桶中
        for (double v : arr) {
            //根据比例获取桶编号，索引从0开始，所以为bucketNum-1
            int num = (int) ((v - min) / d * (bucketNum - 1));
            //加入桶
            bucketList.get(num).add(v);
        }

        //对桶进行依次排序
        for (int i = 0; i < bucketNum; i++) {
            Collections.sort(bucketList.get(i));
        }

        //顺序遍历

        for (LinkedList<Double> doubles : bucketList) {
            for (Double aDouble : doubles) {
                System.out.print(aDouble + " ");
            }
        }
    }