vlambda博客
学习文章列表

不学不知道，算法真奇妙。又到了将“算法”刻到骨子里的时刻。这一讲我们开始算法基础篇之数据排序的第三讲——“计数排序”。

1、前言

第一讲中，数据排序算法的时间复杂度为O(n²)。到第二讲时，数据排序算法的时间复杂度已经优化到了O(nlogn)。既然还有第三讲，那应该意味着我们还能再继续优化。没错，本讲要介绍的“计数排序”就是时间复杂度为O(n+m)的排序算法，这里优化的时间是通过牺牲空间O(m)来换取的，同时，该算法还有一定的场景限制。

2、计数排序

不同于之前的排序算法都要进行元素的比较，计数排序是一种分配类的排序算法。简单来说就是一种简单的数据元素（非负整数）与数组下标的映射。如对数组a={9,8,5,6,6,3,6,2,1,1}进行计数排序。首先遍历得到数组的最大值9和最小值1，由此得到最大值和最小值的差值sub = 9-1 = 8，并据此生成至少容量为8的整型数组。我们新建数组b。接着，遍历原数组a，针对a[0]中对应的值9，在数组b中更新b[9]++，即原数组中的数据成了计数数组中的下标。以此类推，比如对于数组a中的a[3],a[4],a[6]中的数据都是“6”，遍历的时候则分别对b[6]进行“增1”操作，最终b[6]=3。上述分配的结果可以参看下图：

如何体现最终的排序效果呢？遍历数组b，根据数组中的数据确定输出对应元素的下标的次数。如对升序，我们从b[0]开始遍历，b[0]=0，对“0”输出0次；接下来是b[1]，b[1]=2，输出两次下标“1”，此时生成的输出内容为：“1,1”。接着是b[2]，b[2]=1，输出依次下标"2"，此时生成的输出内容为：“1,1,2”。依次类推，最后输出的结果即为:“1,1,2,3,5,6,6,6,8,9”。也就是a数组的升序排列了。实际场景中，通常会根据原始数组中的最小值来做偏移，以达到节省空间的目的，而空间的大小通常利用memset开辟为(“最大值”-“最小值”+1)的的区间范围，详情请通过阅读以下代码加以理解：

#include<bits/stdc++.h>using namespace std;
const int N = 10010,INF = 1e8;
int a[N],b[N],n;
int main(){ srand((unsigned)time(NULL)); n = rand()%10+10; //这里生成的数据控制在10到30，方便对比 //为方便描述，这里数据从下标为0开始存储 int maxa = -INF , mina = INF;  printf("待排序数组：\n");  for(int i=0;i<n;++i){ a[i] = rand()%20+10; printf("%d ",a[i]); maxa = max(maxa,a[i]);//获取最大值  mina = min(mina,a[i]);//获取最小值  }  int range = maxa - mina;//计算极差 //开始计数排序  memset(b,0,range+1);//生成数组，注意生成的大小应该是range+1  for(int i=0;i<n;++i){ //注意这里是分配操作，为控制数组区间，这里需要减去最小值进行偏移。 b[a[i]-mina]++;  }   printf("\n\n计数数组结果(下标偏移量为%d)：\n",mina); for(int i=0;i<=range;++i){ printf("b[%d]=%d ",i,b[i]); }   printf("\n\n计数排序结果：\n"); for(int i=0;i<=range;++i){ for(int j=1;j<=b[i];++j)//对应下标i输出的次数  printf("%d ",i+mina);//输出下标要加上偏移值  }  return 0; }

执行效果如下：

3、算法思想应用

下面这道题是NOIP2006普及组真题，选至一本通第1184题《明明随机数》。

**************************************************

【题目描述】

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

【输入】

有2行，第1行为1个正整数，表示所生成的随机数的个数：N；

第2行有N个用空格隔开的正整数，为所产生的随机数。

【输出】

也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

【输入样例】

10
20 40 32 67 40 20 89 300 400 15

【输出样例】

8
15 20 32 40 67 89 300 400

**************************************************

分析：考虑N是1000以内的随机自然数，涉及的是非负整数类型且在较小范围内的排序问题，因此考虑用计数数组来快速实现。建立计数数组a，对输入的元素依此映射到计数数组对应的下标中，因为涉及到“去重”并需统计随机数的个数，因此这里利用计数数组中的值是否不为0来判断是否对该数组元素进行计数并统计随机数个数。参考代码如下：

#include<bits/stdc++.h>using namespace std;
const int N = 1005;int a[N],n,t,res;
int main() { scanf("%d",&n); for(int i=1; i<=n; ++i) { scanf("%d",&t); if(!a[t]) a[t] = 1 , res++;//更新计数数组并累计随机数  } printf("%d\n",res);//输出随机数个数  for(int i=1; i<=1000; ++i) { if(a[i]) printf("%d ",i);//升序输出  } return 0;}

4、小结

计数排序的算法思想总让人联想到“表驱动法”，这是我在程序员圣经《代码大全》里学到的第一个非常非常有用的方法，在之前的工作中屡有应用，有兴趣的同学也可以提前了解下。今天元旦，新的flag立起来。还有，面对烦恼和茫然，大声说：管它呢，我总要活下去。这一讲就先到这里，谢谢大家的时间。