【Algorithm】排序算法 - 计数排序(Counting Sort)

Posted by 西维蜀黍 on 2019-08-05, Last Modified on 2021-09-21

计数排序(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