一种基于动态交换的计数排序算法
2015-08-08兰洋，尤磊
兰 洋，尤 磊
(1. 信阳师范学院 计算机与信息技术学院, 河南 信阳 464000;2. 中国林业科学研究院 资源信息研究所, 北京 100091)
0 引言
经典的排序算法多注重研究按照元素的升降序排序，然而对元素先计数，再按照计数的大小升降序排序研究的较少.在实际应用中，在一定的数据范围内或在大量数据中先统计元素出现次数，再按照出现次数进行排序是计算机应用中经常遇到的问题.比如词频统计[1]、Google即搜即得功能[2]、用户行为分析[3]、互联网推荐系统[4-5]、关联分析中挖掘频繁1—项集[6-9]、数据流挖掘热门元素[10]等.上述应用都存在如下共性：参与运算的数据量大、数据具有未知性、无法预知重复性.由于一些应用的数据具有实时性、不可再现性等，因此，对这类数据的排序算法应实时高效.
文献[11]将计数排序(Counting sort)定义为一种对整数计数排序的一种算法，其辅助数组的第i个元素是待排序数组中等于i的元素的个数，并由此进行排序.文献[12-13]在排序算法中统计元素出现的次数，目的是缩小排序的范围或减少排序元素的个数.少有文献对元素按照出现次数进行排序的算法进行详细描述.
基于此，本文提出一种基于动态交换策略的计数排序算法.该算法采用容器的数据结构动态保存参与运算的数据，并根据元素的计数情况动态调整元素所在的位置，从而使用更少的时间查询到出现次数多的元素，提高了算法的效率.
1 计数排序的定义
首先给出本文中计数排序的定义：定义A={a1,a2,…,ak}是数据集中出现的k个各不相同元素的集合，B={b1,b2,…,bn}是由A中元素形成的多重集，即bi=bj,i≠j.实际应用中，集合A的元素不一定都在集合B中出现，可设C={c1,c2,…,cm}是多重集合B中不同元素的集合，则ci∈A,C⊆A.现需要统计C中每个元素在B中出现的次数，并由此对C中元素进行降序(或升序)排列.
集合A是所有待排序元素值的集合，取值范围取决于具体的应用，且容量是未知的.多重集合B是待排序元素的集合，是具体的应用数据.集合C是本次排序元素值的集合，满足C⊂A或C=A.
在多重集合B元素确定的情况下，可以使用先统计B中不同元素出现的次数，再按照次数排序的策略.然而这种方法却难以适用到B中元素是动态变化的情况.
2 算法描述
采用实时计数和动态换位的策略，在算法运行过程中，让计数值大的元素向前移动，使得出现次数越多，位置越靠前，从而减少了查询热门元素的时间，提高了算法运行效率.
本文使用C++中的容器对象存储元素，首先给出算法在C++的部分定义代码：
struct element
{
string elementValue; //元素值
int Count; //元素出现的次数
};
typedef vector
VecElement CurrentVec;//排序结果的容器实例
为了便于描述，将排序结果的容器简称为排序容器，采用计数降序的方式对元素排列.排序算法描述如下：
算法逐一将集合B中的元素加入到排序容器中，在加入过程中，首先在排序容器中搜索是否存在与当前元素值相同的数据，若存在，则将该元素的计数值加1；接着与排序容器的前一个元素的计数值比较，如果当前元素的计数值大于前一个元素的计数，则将当前元素与前一个元素交换位置；然后继续与前一个元素进行比较直到当前元素的计数小于等于排序容器前一个元素的计数值或到达第一个元素为止.
算法的伪代码表示如下：
算法2.1 Procedure ReadElemet(B)
输入：待计数降序排列的多重集合B
输出：已计数降序排列的排序容器
1. foreachB[I]
2.InsertElement(B[I]);
算法2.2 Procedure InsertElement(Value)
输入：当前读入的元素
输出：将元素Value放到容器的合适位置
1.n=CurrentVec.size(); //容器的长度
2. bool FindValue=false;
3. forI=0 ton
4. {
5. If (CurrentVec[I].elementValue==Value)
6. {//在容器中寻找到相同值元素
7. CurrentVec[I].Count++;
8.J=I;
9. while(J>0 and CurrentVec[J].Count>CurrentVec[J-1].Count)
10. {
11. Swap(CurrentVec[J],CurrentVec[J-1]);
12.J=J-1;
13. }
14. FindValue=true;
15. Break;
16. }
17. }
18. If (FindValue=false)//容器中没找到相同元素
19.{//将元素增加到尾部
20. element elementValue;
21. elementValue.elementValue=Value
22. elementValue.Count=1;
23. CurrentVec.push_back(elementValue);
24.}
算法2.2的流程图如图1所示.
图1 算法2.2的流程图
通过执行算法2.2的动态交换策略，使得容器中元素间的关系满足CurrentVec[i].Count>=CurrentVec[i+1].Count，确保了排序容器中元素计数值的降序排列.
算法在每步执行过程中，只需要考虑当前元素与排序容器中已经存在的元素，无须考虑后续元素是否存在以及重复，这使得算法具有扩展性.同时，这种根据计数大小动态交换的策略使得算法在对每一个元素运算完成后，排序容器中的元素排列顺序已经是按照计数值的有序排列，我们称之为排序的实时性，这种处理方式对流数据的处理方式是比较适用的.
实际应用中，有可能只需要对集合B中的部分元素进行计数排序(如在入侵检测中，忽略白名单中的IP地址)，对算法略加修改就可实现目的.事实上，排序容器中的元素就是集合C中的元素，两者是等价的.
3 算法的复杂度分析
算法2.2通过在排序容器中查找当前元素是否存在，再确定元素在容器中合适的位置.查找运算是通过比较运算来实现的，所以本算法以元素之间的比较运算作为基本运算.
设集合C={c1,c2,…,ck}，每个元素出现的次数n1,n2,…,nk，且n1≥n2≥…≥nk，则n1+n2+…+nk=|B|=n.因算法具有排序的实时性，所以，出现次数多的元素总是位于容器较靠前的位置.
下面按照集合B中元素是否是均匀分布对算法的时间复杂度进行讨论：
1)集合B中元素均匀分布
若集合B中元素是按照元素所占比例均匀分布，即对于集合B的任意一个连续子集D={bi,bi+1,…,bj}(j≥i+1)，D中出现的每一个元素与|D|的比例与B中出现的每一个元素与|B|的比例相等.此时，算法在运行时元素在排序容器的位置相对稳定.
考虑到算法排序实时性的特点，算法对每一个元素运算完成后,排序容器的序列就是对当前已参与运算元素的计数排序的结果,且出现次数多的元素总是位于容器较靠前的位置，则在均匀分布的情况下，排序容器中的元素排列顺序基本上是c1,c2,…,ck的次序.每次处理c1元素的比较次数是1,每次处理c2元素的比较次数是2.同理，每次处理ck元素的比较次数是k.算法共需要的比较次数是n1+2n2+…+knk≤kn,即在B中元素均匀分布的情况下，算法时间复杂度小于O(kn).
2)集合B中元素非均匀分布
若B中元素非均匀分布，则存在着一些元素聚集出现也就是连续出现.在最坏情况下，每一个连续出现的元素都是当前排序容器中的最后一个元素.设连续元素为D={bi,bi+1,…,bj}(j≥i+1).此时，对于bi，需查找到排序容器的尾部，比较次数是k.若此时排序容器的最后一个元素与倒数第二个元素交换，则bi+1的比较次数是k-1；若排序容器的最后一个元素与倒数第二个元素未交换，则bi+1的比较次数仍是k；以此类推.考虑到每个元素在集合B中共出现的次数，算法结束时，排序容器中每个元素最多的比较次数为该元素共出现的次数与排序容器中元素个数的乘积.对于C={c1,c2,…,ck}，每个元素出现的次数为n1,n2,…,nk且n1≥n2≥…≥nk，则有运算c1元素至多比较的次数是n1k，即有算法共需要的比较次数至多为n1k+n2k+…+nkk=kn.因此在B中元素非均匀分布的情况下，算法是时间复杂度至多为O(kn).
若k的值远小于n的值，算法的时间复杂度可近似认为是O(n).若k=n，此时有B=C，无须执行计数排序算法.算法运行时需使用一个空间来交换数据，其空间复杂度是O(k+1)=O(k).
4 实验
本文在型号ThinkCenterM8500t、内存8 GB、处理器I7-4770的台式机上，采用VC2010开发环境，以某一个超市购物篮数据集[14]、UCI的Adult数据集[15]为测试数据，分别采用本文提出的算法与先统计元素出现次数(按顺序在容器中查找元素，若存在则计数加1，否则在容器尾部增加此元素并将其计数值赋值为1)，再使用快速排序算法两种方法开展实验.
超市购物篮数据集中有20个不同商品的7 007个交易数据.交易次数最多的商品有602次，次数最少的商品有74次.分别记录算法不同记录条数下的运行时间.两种算法的运行时间如图2所示.
Adult数据集来源于美国人口普查数据的一部分，共有14个属性，包括年龄、教育程度等字段；在32 561条的数据中共有408个不同的元素，其中出现次数最多的元素是0(在资产收益与资产流失字段中)，共60 891次；出现次数最小的元素是出现次数为1的元素.
图2 超市数据集算法运行时间比较图
图3 Adult数据集算法运行时间比较图
与超市数据集的实验方式相同，对Adult数据集也采用上述两种算法，分别在记录数10 000条、20 000条、所有记录(32 561条)开展实验，两种算法在不同记录条数下的运行时间如图3所示.
从实验结果可以看出，本文提出算法的性能明显优于先统计再快速排序的算法.先统计再排序算法的运算时间主要消耗在统计元素出现的次数上，参与运算的元素个数是第3部分集合C的元素个数n；快速排序的运算元素个数是集合B的元素个数k.一般情况下，k的值远小于n的值，提高统计元素算法的效率就提高了算法的效率.本文算法的动态交换策略在将元素移动到合适位置的同时也为查找元素提供了便利，从而有效地提高了算法的运行效率.
5 小结
按照元素出现次数对元素进行排序在很多方面都有应用，但却少见有对这种应用的具体描述算法，本文提出了一种基于动态交换的计数排序算法.该算法具有输入输出的实时性，即只需要对原始数据扫描一次；在完成当前数据的运算后，排序容器中的数据都是有序的.通过对算法的时间与空间复杂度的分析以及实验表明，该算法运行效率高，具有实用性.
