C＋不知算法系列之细聊计数排序算法如何巧用计数

1. 前言

是较简单的排序算法，其是利用数组索引号有序的原理。

如对如下的中的数据(元素)排序：

使用的基本思路如下：

创建一个。数组的大小由原始数组的最大值决定，如原始数组的最大值为，则排序数组的长度为 。为什么排序数组的长度需要如此设置，后文将做解释。

读取原始数组中的，以此作为的，此数据出现的次数为排序数组的值。

这也解释了为什么排序数组的长度必须是原始数组中最大值加。因为必须能为原始数组中的提供索引号。

然后输出中的值不为 的索引号。

编码实现：

输出结果：

通过上文简述可知：

计数排序的时间复杂度为，时间复杂度还算可观。

但是空间复杂度也是。相比较如冒泡、选择……排序算法，计数排序算法是以空间换取时间。

2. 两个问题

2.1 排序数组的长度

计数排序利用数组索引号的有序而对数据排序，所以，需要把原无序数组中的映射到排序数组的索引号上。于是，对排序数组的长度就会有一个最小值的约束，至少等于无序数组中的最大值加一。

如下面的无序数组：

为了保证无序数组中的数据能映射到对应的索引号，则排序数组长度至少应该为 。

而实际需要映射的数据只有 个，会导致排序数组空间浪费巨大，这也是计数排序缺点所在。

如下图所示：

如何解决此问题？

可以在创建排序数组时：

找到原始无序数组中的最大值和最小值。如上文无序数组的最大值为 ，最小值为。

指定排序数组的长度为：，即排序数组的长度为：。

无序数组到排序数组的映射规则：。

反之在遍历排序数组时：。

编码实现：

输出结果：

2.2 重复问题

如果无序数组中有重复数据，根据计数排序算法的映射原理，显然，相同数据会映射到排序数组的同一个位置。排序数组通过计数器方案对相同数据进行计数。这也是计数排序算法名称的由来。

如下图所示：无序数组中的 个 和 个映射到了排序数组的同一个位置，排序数组的值记录了重复数据的多少。

编码实现：

输出结果：

此处只能对重复的数据计数，但无法得知重复数据的原始顺序。故，理论而言，计数排序算法是不稳定的。

有没有方案能输出时保留重复数据的原始先后顺序？

答案是：改造排序数组中的值，数组中的映射位置不再存储此索引号对应数据的个数，而是存储此索引号之前所有数据的个数。

然后逆向遍历原始无序数组。用其值做为排序数组的索引号，找出存储在排序数组中的值然后减一，便知道此数据应该排在有序位置的第几位。

为什么要逆向遍历？

原因很简单，在映射时，是正向遍历，则无序数组中的第 个 一定是先映射到排序数组的索引号为 的位置，最后的一个 是后映射到排序数组索引号为 的位置。拿出来时，应该要遵循先进后出原则。

编码实现：

输出结果：

3. 完整的代码及应用

3.1 完整代码

上文对计数排序的实现流程做了分步讲解，综合基本思想以及其问题解决方案。下面是完整的代码。

3.2 应用

的试卷中有一道与计数排序算法有关的程序题。

题目描述：

(计数排序)计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将对以内的整数，从小到大排序。例如有三对整数，那么排序之后应该是。输入第一行为，接下来行，第行有两个数和，分别表示第 对整数的第一关键字和第二关键字。从小到大排序后输出。数据范围。提示：应先对第二关键字排序，再对第一关键字排序。数组存储第二关键字排序的结果，数组存储双关键字排序的结果。

试补全程序：

处应填(  )

A、

B、

C、

D、

2） 处应填（   ）

A、

B、

C、

D、

3） 处应填（   ）

A.

B.  ++cnt[a[i] * maxs + b[i]]

C.

D.

4） 处应填（   ）

A、

B、

C、

D、

5） 处应填（   ）

A、

B、

C、

D、

4. 总结

计数排序、桶排序以及基数排序是类似的排序算法。相比较计数排序时数组纵向长度的不可控，基数排序使用二维数组对数据排序，且把数组的大小限定在的 之间，空间大小可控的。但是，从时间复杂度上讲，计数排序更胜一筹。