[toc]

前言

声明：参考来源互联网，有任何争议可以留言。站在前人的肩上，我们才能看的更远。

本教程纯手打，致力于最实用教程，不需要什么奖励，只希望多多转发支持。
欢迎来我公众号，希望可以结识你，也可以催更，微信搜索：JavaPub

有任何问题都可以来谈谈！

计数排序 是比较容易的排序算法，但是对数量级较小的整数排序很实用。

1. 计数排序(Counting Sort)

1.1. 计数排序(Counting Sort)

计数排序是一个 非基于比较 的排序算法，该算法于 1954 年由 Harold H. Seward 提出。它的优势在于在对 一定范围 内的 整数排序 时，它的复杂度为 Ο(n+k)（其中 k 是整数的范围），快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当 O(k)>O(n*log(n)) 的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是 O(n*log(n)), 如 归并排序，堆排序）

例如：计数排序是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

• 计数排序是一个简单的排序算法，看下边原理很容易理解。

2. 原理

2.1. 步骤

• 算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1

如果有疑问，看下边一个例子

2.2. 实例题目

题目：数组里有 20 个随机数，取值范围为从 0 到 10，要求用最快的速度把这 20 个整数从小到大进行排序。

无论是 [归并排序]()，[冒泡排序]() 还是 [快速排序]() 等等，都是基于元素之间的 比较 来进行排序的。但是有一种特殊的排序算法叫 计数排序 ，这种排序算法不是基于元素比较，而是利用 数组下标 来确定元素的正确位置。

通过 计数排序 特性分析题目，我们知道整数的取值范围是从 0 到 10，那么这些整数的值肯定是在 0 到 10 这 11 个数里面。于是我们可以建立一个长度为 11 的数组，数组下标从 0 到 10，元素初始值全为 0，如下所示：

先假设 20 个随机整数的值是：9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9

• 让我们先遍历这个无序的随机数组，每一个整数按照其值对号入座，对应数组下标的元素进行 加 1 操作。

比如第一个整数是 9，那么数组下标为 9 的元素加 1：

• 第二个整数是 3，那么数组下标为 3 的元素加 1：

• 继续遍历数列并修改数组 ……

最终，数列遍历完毕时，数组的状态如下：

数组中的每一个值，代表了数列中对应整数的出现次数。

有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10

这就是计数排序的基本过程，它 适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些 O(nlogn)的排序，例如快速排序、归并排序。

3. 代码

3.1. 代码

@Test
public void sortJavaPub(){int [] array = {2,1,5,3,4};
    //1. 得到数列的最大值
    int max = array[0];
    for (int i = 1; i < array.length; i++) {if (array[i] > max)
            max = array[i];
    }
    //2. 根据数列的最大值确定统计数组的长度
    int[] coutArray = new int[max + 1];
    //3. 遍历数列，填充统计数组
    for(int i = 0; i < array.length; i++)
        coutArray[array[i]]++;

    //4. 遍历统计数组，输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for (int i = 0; i < coutArray.length; i++) {for (int j = 0; j < coutArray[i]; j++) {sortedArray[index++] = i;
        }
    }
    System.out.println(Arrays.toString(sortedArray));
}

返回结果：

[1, 2, 3, 4, 5]

4. 扩展阅读

4.1. 局限性

1. 当数列最大最小值差距过大时，并不适用于计数排序

比如给定 20 个随机整数，范围在 0 到 1 亿之间，此时如果使用计数排序的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。

2. 当数列元素不是整数时，并不适用于计数排序

如果数列中的元素都是小数，比如 3.1415，或是 0.00000001 这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。