Algorithm

【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

FEATURED TAGS
algorithm algorithm-problem architectural-pattern architecture aws c# cache-system codis concurrent-control data-format data-structure database debug design design-pattern distributed-system django docker engineering engingeering freebsd git golang grafana hackintosh hardware hexo http hugo ios iot java java-ee javascript kafka kubernetes linux lock macos markdown microservices mysql nas network network-programming nginx node.js npm oop openwrt operating-system operating-systems padavan performance programming prometheus protobuf python redis router security shell software-testing spring sql truenas ubuntu vmware vpn windows wmware wordpress zookeeper
FRIENDS

TOC