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