Algorithm

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

Posted by 西维蜀黍 on 2019-08-05, Last Modified on 2023-08-27

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

FEATURED TAGS
algorithm algorithmproblem architecturalpattern architecture aws c# cachesystem codis concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper
FRIENDS

TOC