Counting sort — 计数排序

原理:

假设待排序对象为整数,且范围为1…1000;

举例:2,3,3,4

首先统计每个数字出现的次数,用c[i]表示。i表示数字,c[i]表示数字i出现的次数;

c[1] = 0;  c[2] = 1;  c[3] = 2;  c[4]=1;

然后从小到大,统计比每个数小的数一共有多少,用a[i]表示。i表示数字,a[i]=c[1]+c[2]+c[3]…+c[i]

a[2] = 1;a[3] = 3;a[4]=4;

接着算出每个数字的序数;遍历每个数字,算出其序数,将这个数字直接放在数组rank中,其对应的位置上;

for(int i = 1;i <= n;i ++) rank[– c[a[i]]] = a[i];

整个过程并没有一个数组专门来存所有待排列数字,只有一个数组rank来存储排列好的数字,所有一样大的数字之间的顺序取决于代码实现的过程。

《算法设计编程实验》中提到使用计数排序来实现后缀数组中rank数组的计算(这里的rank是后缀数组的rank),其实是笔误,那里用的是基数排序。

 

Leave a Reply

Your email address will not be published. Required fields are marked *