2.4 计数排序

非比较排序算法要解决的问题是寻找一种方法，既不需要对待排序序列中各元素进行比较，同时又能将序列中各元素置于其最终位置。本质上，非比较排序算法就是寻找一种能够完成待排序序列中各元素当前状态到其排序后最终状态的映射方法，这种映射方法既可能是较简单的线性映射，也可能是较复杂的非线性映射。

1954年，Harold H.Seward提出了计数排序算法，计数排序是一种非比较排序算法。计数排序利用元素自身特性和额外的存储空间来实现元素从无序状态变为有序状态，排序过程中不需要进行元素间的比较和交换，属于以空间换时间的排序算法。

2.4.1 计数排序的基本思想

计数排序的关键之处是建立输入数据与额外存储空间的映射，在数据密集且范围较小的情况下排序效率高，当数据分布范围广且间隔较大时空间效率较低。

计数排序的基本思想如下。

（1）排序前需要确定待排序元素中的最大值与最小值，根据二者的差值范围申请额外的存储空间。

（2）排序过程中，从头至尾扫描待排序序列，根据元素值定位到辅助存储空间的相应位置，将每个元素出现的次数记录到其中。

（3）通过对辅助空间进行数据统计就可以确定所有元素在有序序列中的最终位置。

设待排序的无序序列存放于数组array中，长度为length，计数排序的伪代码如表2-4所示。

2.4.2 计数排序过程分析

假定待排序的数据为｛101，109，107，103，108，102，103，110，107，103｝。实现不进行比较而进行排序的最朴素处理思路是假设已经找到了完成排序功能的映射方法，当待排序数据为101时，应将其置于排序结果的第1号位置；当待排序的元素为109时，应将其置于排序结果的第9号位置；其他待排序元素以此类推。在实际排序过程中，很难通过观察法直接获得这样的映射关系。因此，可以利用空间效率换取时间效率，在牺牲一定空间代价的前提下获得时间效率的提升也是值得的。将存储排序结果的空间扩大，并对问题进一步抽象，每个位置存储一种排序值，无排序值的位置保留，这样就解决了待排序元素值到排序后最终位置的第一次映射。为了解决待排序元素存在重复值的问题，需要通过在每个位置上对存储的排序值进行计数来实现。第一次映射获得了各排序值的中间位置和计数，最后通过对中间结果进行边读取边放置的方式完成各排序值和计数到排序结果中最终位置的映射。待排序序列中，最大值为110，最小值为101，需设置从101至110共10个“桶”来进行计数排序。

1．初始状态

初始时，统计待排序数据的数据范围，最大值max=110，最小值min=101，设置101~110共10个“桶”，将各个“桶”的计数初始化为0。

2．计数过程

第1个元素：取序列中第1个元素101，将［101］号“桶”的值+1，即101的出现次数增加1次，［101］=1，如图2-5中第1行所示。

第2个元素：取序列中第2个元素109，将［109］号“桶”的值+1，即109的出现次数增加1次，［109］=1，如图2-5中第2行所示。

第3个元素：取序列中第3个元素107，将［107］号“桶”的值+1，即［107］=1。

第4个元素：取序列中第4个元素103，将［103］号“桶”的值+1，即［103］=1。

第5个元素：取序列中第5个元素108，将［108］号“桶”的值+1，即［108］=1。

第6个元素：取序列中第6个元素102，将［102］号“桶”的值+1，即［102］=1。

第7个元素：取序列中第7个元素103，将［103］号“桶”的值+1，即［103］=2。

第8个元素：取序列中第8个元素110，将［110］号“桶”的值+1，即［110］=1。

第9个元素：取序列中第9个元素107，将［107］号“桶”的值+1，即［107］=2。

第10个元素：取序列中第10个元素103，将［103］号“桶”的值+1，即［103］=3。

至此，计数过程结束，各个“桶”内计数结果如图2-5中第10行所示，其中［104］、［105］和［106］无对应元素，值为0。

3．排序过程

排序过程需要遍历每个“桶”，根据“桶”中元素个数来生成排序后的序列。

第1号“桶”处理：第［101］号桶值为1，含义是值为101的元素有一个，将101放入排序结果数组的0号下标处，如图2-6中第1行所示。

第2号“桶”处理：第［102］号桶值为1，将102放入排序结果数组的1号下标处，如图2-6中第2行所示。

第3号“桶”处理：第［103］号桶值为3，将103放入排序结果数组的2、3、4号下标处，如图2-6中第3行所示。

第4、5、6号“桶”处理：第［104］、［105］和［106］号桶值为0，无对应元素信息，直接略过。

第7号“桶”处理：第［107］号桶值为2，将107放入排序结果数组的5、6号下标处，如图2-6中第4行所示。

第8、9、10号“桶”处理：第［108］、［109］和［110］号桶值均为1，将108、109和110分别放入排序结果数组的7、8、9号下标处，如图2-6中第5、6、7行所示。

至此，所有“桶”均处理完毕，排序过程结束，如图2-6第8行所示，排序结果为｛101，102，103，103，103，107，107，108，109，110｝。

需要注意的是，当待排序数据分布范围广且呈稀疏状态时，使用计数排序会存在空间浪费等问题，可以采用基于单链表存储的“链式桶”或使用散列算法与结构体配合的方式来完成排序。

2.4.3 计数排序代码分析

实现计数排序主体功能的是counting_sort（）函数，main（）函数用于测试排序的效果。Counting_sort（）函数可实现对部分序列进行原地升序排序，包括6个参数：data［］为待排序数组，start为排序区间的起始下标，len为待排序区间的长度，counts［］为直接分配辅助空间数组（非动态申请，由调用方作为输入参数提供），min为排序区间的最小值，max为排序区间的最大值。

用counting_sort（）函数进行计数排序时，必须借助辅助数组counts［］实现。①将各个“桶”的计数清零，将用于统计待排序数据出现频率的辅助数组counts［］指定范围清零。②从头至尾处理待排序区间的每一个元素data［i］，处理过程中利用num-min完成数据到“桶”下标间的映射。③利用二重循环实现从辅助数组counts［］的计数到原数组data［］的反向映射，进行原地升序排列。外循环处理counts［］中的所有元素，若counts［i］>0则反复利用i+min实现反向映射。

在主函数中，需要统计待排序序列的数据范围后才能进行计数排序。

实现代码如下。

测试数据及运行结果如下。

①数据总数及各数据：

    10
    101 109 107 103 108 102 103 110 107 103

    1 8

③运行结果：

    101 102 103 103 107 107 108 109 110 103

2.4.4 统计句子中字母出现的次数

用键盘输入一段英文字符（以#结束），统计输入序列中每个英文字母的出现次数（区分大小写）。

本题是计数排序的典型应用，解题思路如下。

（1）分析问题所求，确定解决问题所需的数据空间。本题需要统计的英文字母在区分大小写的情况下共计52个，设置52个“桶”即可。

（2）直接定义静态辅助数组char_counts［52］，并将计数初始化为0。

（3）循环读入字符，若字符是大写字母［A~Z］则利用idx=chtmp-'A'实现映射，是小写字母［a~z］则需要使用idx=chtmp-'a'+26实现到char_counts［26~51］高半部分的映射。

（4）输出统计信息时需要进行反向映射，利用（char）（'A'+idx）和（char）（'a'+idx-26）实现字符的反向映射。

解决本题的关键是将大、小写两部分数据映射到同一空间。

（1）数组char_counts［］共52个元素，下标0~25存储大写字母［A~Z］的出现次数，下标26~51存储小写字母［a~z］的出现次数。

（2）大写字母和下标间转换为ch-'A'，若字母为A，则其对应的下标为0（'A'-'A'=0），小写字母和下标间的转换为ch-'a'。

（3）小写字母'a'与大写字母'A'间下标差为26，小写字母到下标的映射关系需要将26考虑到其中。

实现代码如下。

测试数据如下。

    In computer science,counting sort is an algorithm for sorting a collection of
    objects according to keys that are small integers.IT OPERATES BY COUNTING THE
    NUMBER OF OBJECTS THAT HAVE EACH DISTINCT KEY VALUE,           AND USING ARITHMETIC ON
    THOSE   COUNTS   TO  DETERMINE    THE  POSITIONS   OF  EACH   KEY  VALUE   IN  THE  OUTPUT
    SEQUENCE.#

统计结果如表2-5所示。