计数排序

算法描述(Pascal AAuto语言描述)

算法介绍

计数排序法是一种简单的排序方法，这种排序算法对一个待排序的数组进行排序，并将排序结果放到另一个新的数组中。计数排序算法针对待排序数组中的每个记录，扫描待排序的数组一趟，统计待排序数组中有多少个记录的值比该记录的值小。假设针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序数组中的合适的存放位置即为c。

假设有三个数组：

数组 A：待排序数组（非空，数据个数n）

数组 B：排序后的数组

数组 count：纪录A中某个数据在表B中的位置，初始值为0

对于A中某个数据Xi（0<=i<n），与表中各个数据Xj（0<=i<n）进行比较，记录下比Xi小的值的个数到count[i]。但是，我们发现，数据与自身的比较是多余的，而且当Xi与Xj比较后，就没有必要再比较Xj和Xi了。在此基础上我们对之前的操作方式进行一些变化。我们对A中的数据Xi与Xj进行比较，所不同的是Xj的j的范围为 i<j<=n ，即每个Xi只和其后的数据进行比较。在比较过程中，如果Xi > Xj ，则count[i] = count[i]+1；否则，count[j]=count[j]+1 。当算法完毕的时候，count数组中就记录了A中的各个数据在B中的实际位置。算法过程如下所示：

n 0 1 2 3 /*数组的索引位置*/

A 21 32 17 21 /*数组中的数据*/

C [0] [0] [0] [0] /*count的初始值*/

算法开始i=0，j取值{1 ，2，3}。

（1）X0<X1 ，所以count[1]+1

n 0 1 2 3 /*数组的索引位置*/

A 21 32 17 21 /*数组中的数据*/

C [0] [1] [0] [0] /*count的值*/

（2）X0>X2 ，所以count[0]+1

n 0 1 2 3 /*数组的索引位置*/

A 21 32 17 21 /*数组中的数据*/

C [1] [1] [0] [0] /*count的值*/

（3）X0=X3 ，所以count[3]+1

n 0 1 2 3 /*数组的索引位置*/

A 21 32 17 21 /*数组中的数据*/

C [1] [1] [0] [1] /*count的值*/

接下来i=1 ，j取值{2，3}

…….

如此继续直至算法完毕，则

n 0 1 2 3 /*数组的索引位置*/

A 21 32 17 21 /*数组中的数据*/

C [1] [3] [0] [2] /*count的初始值*/

接下来的要做的只是按count中的值将A中的数据放到B中相应的位置上了，即 B[count[i]] = A[i]，则数组B中数据为

B [17] [21] [21] [32]

至此计数排序算法完成。

在上述过程中，我们看到，对于待排序数组中的相同数据，在排序后其先后顺序保持不变，也就是说以上原理的排序算法是一个稳定的排序算法。

算法复杂度：

上述计数排序算法包含两重循环，假设数组A中的数据个数为n，那么在程序执行过程中，第二层循环控制变量j的执行次数随着第一层循环控制变量i的变化依次为n-1 ， n-2，n-3，…….，0 ，这是一个差值为1的n项等差数列，所以第二层循环的执行次数为(n-1+0)*n/2,即n*（n-1）/2，所以该算法的时间复杂度为O（n2）。

学习建议及练习任务：

按照上述计数排序的原理，实现一个计数降序排序，要求排序的算法是稳定的。

计数排序

计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件：

1、输入的线性表的元素属于有限偏序集S；

2、设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

在这两个条件下，计数排序的复杂性为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}；则计数排序算法可以描述如下：

扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；

扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。

具体的实现如下：

void Counting_Sort(int a[], int b[], int l, int k)

...{

int* c = new int[k];

memset(c, 0, k * sizeof(int));

for (int j = 0; j < l; j++) c[a[j]]++;

for (int j = 1; j < k; j++) c[j] += c[j - 1];

for (int j = l - 1; j >= 0; j--)

...{

b[c[a[j]] - 1] = a[j];

c[a[j]]--;

}

delete []c;

}

其中a为输入，b为输出，l为元素个数，k为元素最大值。

我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到线性时间的上界。此外，我们还看到，由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法。

算法描述

Pascal

var

i,j,n:longint;

a,b:array[0..1000] of longint;

begin

read(n);

for i:=1 to n do

begin

read(a[i]);

b[a[i]]:=b[a[i]]+1;

end;

for i:=0 to 1000 do

if b[i]>0 then

for j:=1 to b[i] do

write(i,' ');

end.

AAuto语言描述

io.open();//打开控制台

/*

*-------------------------------------------------------

* 计数排序

**------------------------------------------------------

*/

/*

假设n个0到k之间的整数。

对于每一个输入元素x，确定出小于x的元素个数lt，则x可直接放于输出位置lt+1上。

*/

//计数排序算法

counting_sort = function( array ,k){

array_sorted ={};

count ={};

for(i=0;k ){

count[i] = 0;

}

for(i=1;#array;1){

count[ array[i] ] = count[ array[i] ] + 1; //count[n] 包含等于n的个数

}

//统计位置

for(i=1;k;1){

count[i] += count[i-1]; //count[i] 包含小于等于i的个数

}

var n;

for(i=#array;1;-1){

n = array[i]

array_sorted[ count[n] ] = n;

count[n]--;//防止相同的元素n再次出现，将计数减一

}

return array_sorted;

}

io.print("----------------")

io.print("计数排序( 线性时间排序 )")

io.print("----------------")

array ={12;3;22;7;6;23;26};

//取出最大的数

var max = math.max( table.unpack(array) ) ;

//排序

array = counting_sort(array,max )

//输出结果

for(i=1;#array;1){

io.print( array[i] )

}

execute("pause") //按任意键继续

io.close();//关闭控制台