【Algorithm】排序算法 - 计数排序（Counting Sort）

计数排序（Counting Sort）

计数排序是一种非基于比较的排序算法，计数排序的时间复杂度为 O(n + m)，m 指的是数据量，说的简单点，计数排序算法的时间复杂度约等于 O(n)，快于任何比较型的排序算法。

图解计数

以下以[ 3，5，8，2，5，4 ]这组数字来演示。

首先，我们找到这组数字中最大的数，也就是 8，我们就创建一个最大下标为 8 的空数组 arr 。

遍历数据，以将数据的出现次数填入arr中对应的下标位置中（该数据的值等于arr中对应的下标）。

遍历 arr ，将数据依次取出即可。

代码实现

public static void sort(int[] arr) {
    //找出数组中的最大值
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    //初始化计数数组
    int[] countArr = new int[max + 1];

    //计数
    for (int i = 0; i < arr.length; i++) {
        countArr[arr[i]]++;
        arr[i] = 0;
    }
    
    //排序
    int index = 0;
    for (int i = 0; i < countArr.length; i++) {
        if (countArr[i] > 0) {
            arr[index++] = i;
        }
    }
}

Reference

• 这或许是东半球讲十大排序算法最好的一篇文章 - https://cxyxiaowu.com/articles/2019/06/11/1560233679033.html
• https://www.geeksforgeeks.org/counting-sort/