算法练习(5)-计数排序法及优化

菩提树下的杨过

发布于 2021-03-27 16:51:42

3640

发布于 2021-03-27 16:51:42

日常开发中，会遇到一些特定的排序场景：“待排序的值”范围很明细，比如：基金的星级排名，客服的好评星级排名，一般星级排名也就从1星到5星。这种情况下，有一个经典的“下标计数排序法”，可以用O(n)的时间复杂度完成排序：

    static void sort0() {
        int[] arr = new int[]{5, 4, 4, 1, 2, 3};
        int[] indexCountArr = new int[6];

        //下标计数排序
        for (int i = 0; i < arr.length; i++) {
            indexCountArr[arr[i]] += 1;
        }
        //排完后，indexCountArr的值:[0, 1, 1, 1, 2, 1]
        System.out.println("indexCountArr=>" + Arrays.toString(indexCountArr));
        
        //排序结果输出
        for (int i = 0; i < indexCountArr.length; i++) {
            for (int j = 0; j < indexCountArr[i]; j++) {
                System.out.print(i + "\t");
            }
        }
        System.out.println("\n");
    }

输出：

indexCountArr=>[0, 1, 1, 1, 2, 1] 1 2 3 4 4 5

但这是一个不稳定的排序算法，而且输出结果只有值，如果是一个复杂的对象，比如下面这样：

    static class EmpScore {
        public String empNo;
        public int score;

        public EmpScore(String empNo, int score) {
            this.empNo = empNo;
            this.score = score;
        }

        @Override
        public String toString() {
            return empNo + ":" + score;
        }
    }

    public static void main(String[] args) {
        EmpScore[] arr = new EmpScore[]{
                new EmpScore("S01", 5),
                new EmpScore("S02", 4),
                new EmpScore("S03", 4),
                new EmpScore("S04", 1),
                new EmpScore("S05", 2),
                new EmpScore("S06", 3)
        };

        //todo 待排序
    }

按score评分星级排序后，如果希望S02仍然在S03前面，可以参考下面这样：(大致思路是在每个"桶"的位置，引入了一个顺序结构的List)

    static void sort1(EmpScore[] arr) {
        //排序过程(下标计数排序)
        Map<Integer, List<EmpScore>> scoreMap = new HashMap<>(arr.length);
        int[] indexCountArr = new int[6];
        for (int i = 0; i < arr.length; i++) {
            indexCountArr[arr[i].score] += 1;
            List<EmpScore> list;
            if (scoreMap.containsKey(arr[i].score)) {
                list = scoreMap.get(arr[i].score);
            } else {
                list = new ArrayList<>();
            }
            list.add(arr[i]);
            scoreMap.put(arr[i].score, list);
        }
        //排完后，indexCountArr的值:[0, 1, 1, 1, 2, 1]
        System.out.println("indexCountArr=>" + Arrays.toString(indexCountArr));

        //输出结果
        List<EmpScore> sortedList = new ArrayList<>(arr.length);
        for (int i = 1; i < indexCountArr.length; i++) {
            sortedList.addAll(scoreMap.get(i));
        }
        System.out.println(sortedList.toString() + "\n");
    }

输出：

indexCountArr=>[0, 1, 1, 1, 2, 1] [S04:1, S05:2, S06:3, S02:4, S03:4, S01:5]

如果不想额外引入List，还可以这样做：

static void sort2(EmpScore[] arr) {
    int[] indexCountArr = new int[6];
    for (int i = 0; i < arr.length; i++) {
        indexCountArr[arr[i].score] += 1;
    }
    //关键点1
    for (int i = 1; i < arr.length; i++) {
        indexCountArr[i] += indexCountArr[i - 1];
    }

    //排完后，indexCountArr的值:[0, 1, 2, 3, 5, 6]
    System.out.println("indexCountArr=>" + Arrays.toString(indexCountArr));

    EmpScore[] sorted = new EmpScore[arr.length];
    //关键点2
    for (int i = arr.length - 1; i >= 0; i--) {
        sorted[indexCountArr[arr[i].score] - 1] = arr[i];
        indexCountArr[arr[i].score] -= 1;
    }

    System.out.println(Arrays.toString(sorted));
}

结果不变，具体过程，大家可以拿张纸，自己画一画，还是蛮有技巧的，算是一种比较tricky的解法吧。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-03-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

list