线性时间排序算法——计数排序（Counting Sort）

计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件，在这两个条件下，计数排序的复杂性为O(n)。 1. 输入的线性表的元素属于有限偏序集S； 2. 设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。 计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出 序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值 时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。 假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序算法可以描述如下： 1. 扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)； 2. 扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。 具体的实现如下。 注意：在以下的讨论中，为了方便，我们假设线性表是用数组来实现的，并且假设线性表的元素类型TElement为整型，其值在1..k之间，线性表的长度为n，且k=O(n)。这些假设对计数排序算法没有实质的影响，但是可以使以下介绍的算法看起来容易理解。 在下面的计数排序算法中，我们假设L为输入的长度为n的线性表，输出的排序结果存放在线性表R中。算法中还用到一个辅助表tmp用于对输入元素进行计数。 Type TElement=1..k; TList=array [1..maxlength] of TElement; TPosition=integer; procedure Counting_Sort(var L,R:TList); var i,j:integer; tmp:TList; begin 1 for i:=1 to k do tmp[i]:=0; 2 for j:=1 to n do inc(tmp[L[j]]);    //执行完上面的循环后，tmp[i]的值是L中等于i的元素的个数 3 for i:=2 to k do tmp[i]:=tmp[i]+tmp[i-1];    //执行完上面的循环后，tmp[i]的值是L中小于等于i的元素的个数 4 for j:=n downto 1 do  //注意这里的downto保证了排序的稳定性    begin 5   R[tmp[L[j]]]:=L[j];//L[j]存放在输出数组R的第tmp[L[j]]个位置上 6   dec(tmp[L[j]]); //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数    end; end; 图1所示的是Counting_Sort作用于一个输入数组L[1..8]上的过程，其中L的每一个元素都是不大于k=6的正整数。 　　图1 计数排序算法演示 容易理解，算法的第(l)行是对数组 tmp初始化。第(2)行检查每个输入元素。如果输入元素的键值为i，则tmp[i]增1。因此，在第(2)行执行结束后，tmp[i]中存放着值等于i 的输入元素个数，i=1,2,..,k。算法的第(3)行，对每个i=1,2,..,i，统计值小于或等于i的输入元素个数。最后在(4)-(8)行中， 将每个元素L[j]存放到输出数组R中相应的最终位置上。 如果所有n个元素的值都不相同，则共有tmp[L[j]]个元素的键值小于 或等于L[j]，而小于L[j]的元素有tmp[L[j]]-1个，因此tmp[L[j]]就是L[j]在输出数组R中的正确位置。当输入元素有相同的值 时，每将一个L[j]存放到数组R时，tmp[L[j]]就减1，使下个值等于L[j]的元素存放在输出数组R中存放元素L[j]的前一个位置上。 计数排序算法的计算时间复杂性很容易分析。其中，第(1)行需要O(k)时间；第(2)行需要O(n)时间，第(3)行需要O(k)时间；第 (4)-(8)行的for循环需要O(n)时间。这样，整个算法所需的计算间为O(n+k)。当k=O(n)时，算法的计算时间复杂性为O(n)。 我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而 它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。 如果k=n2,n3,..，就得不到线性时间的上界。 此外，我们还看到，由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法，但显然不是原地置换排序算法。