计数排序java

叁歲伎倆 2022-06-06 08:10 109阅读 0赞

*  计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
 *  桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
 *  当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序， 排序的速度快于任何比较排序算法
 *  主流程：
    
    1.找出待排序的数组中最大和最小的元素
    
    2.统计数组中每个值为i的元素出现的次数，存入辅助数组help的第i项
    
    3.对所有的计数累加，获得元素的排位，从0开始遍历help, help\[i+1\]=help\[i\] + help\[i-1\]
    
    4.反向填充目标数组：将每个元素i放在新数组的第help(i)项
    
    java代码：

/* * Created by susq on 2017-9-21. */
    public class CountSort {
    
        public static int[] countSort2(int[] arr) {
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            // 找出最大最小值
            for (int anArr : arr) {
                max = Math.max(max, anArr);
                min = Math.min(min, anArr);
            }
            int[] help = new int[max-min+1];
            // n - min: 就是排序后在新数组中它该在的位置（ 原值-min -> 新位置 ，当前值：次数）
            // 每出现一次，该位置的值+1， 记录出现的次数
            for (int anArr1 : arr) {
                int mapPos = anArr1 - min;
                help[mapPos]++;
            }
            // 累加：累加的结果是，出现在这个值前面的元素的个数
            for (int i=1; i<help.length; i++) {
                help[i] = help[i-1] + help[i];
            }
            int res[] = new int[arr.length];
    
            for (int i=0; i<arr.length; i++) {
                int pos = --help[arr[i]-min];  //从help取得下标，help中的值应该-1才是下标
                res[pos] = arr[i];
            }
            return res;
        }
    
        public static void main(String[] args) {
            int [] arr = new int[] {
       1,5,3,3,2,4};
            int[] res = countSort2(arr);
            Arrays.stream(res).forEach(System.out::println);
        }
    }