算法基础：排序算法：计数排序

计数排序也被称为桶排序或者箱排序，都是它和常规的桶排序还是有较为明显的区别，在这篇文章中还是使用计数排序的称呼。计数排序可以进一步将排序的时间复杂度降低到O(n)，而且也可以是稳定的排序，理解起来也很容易，实现简单。它算是空间换时间策略的代表之一，空间消耗过大，受排序序列的影响极大，能够排序的场合受限，这些也都是计数排序的阿喀琉斯之踵（或许类比失当，计数排序也很难称得上是排序之中的阿喀琉斯）。

算法思路

• 计数排序在理解上大概是比冒泡排序还要简单的排序，它的做法就是根据待排序的内容生成一大块连续的空间，能够保存待排序的最大值-最小值的范围，然后巧妙的将值作为下标进行保存，而该下标的元素中保持记录重复的次数，然后输出的时候根据顺序进行输出，有计数值的按照计数值进行输出即可，有重复的根据计数值进行递减。

算法要点

简单的计数排序模拟几乎没有什么要点：

• 额外空间：预备一个大的空间，能将输入的范围都保存进去
• 循环计数：对于待排序的元素进行循环，将带排序的元素的值作为下标，在额外空间的数组中进行计数
• 结果输出：对额外空间的数组进行循环，有计数值的递减输出即可。

模拟实现

void count_sort(int* arr, int num, int* count) { for (int i=0; i<num; i++) { count[arr[i]]++; } } 

结果验证

加上打印和调用的示例代码，可以使用如下方式进行验证

#include  #include  #include  #define MAX_ARRAY_LENGTH 10000 void count_sort(int* arr, int num, int* count) { for (int i=0; i<num; i++) { count[arr[i]]++; } } void print_array(int* count) { for (int i=0; i<MAX_ARRAY_LENGTH; i++) { for (int j=count[i]; j>0; j--) { printf("%d ",i); } } printf("\n"); } int main() { int n = 0; while (scanf("%d",&n) != EOF) { int count[MAX_ARRAY_LENGTH] = { 0 }; int* array = (int *)malloc(sizeof(int)*n); memset(array,0,sizeof(int)*n); for (int i=0; i<n; i++) { scanf("%d",&array[i]); } count_sort(array,n,count); print_array(count); free(array); array= NULL; } } 

执行结果示例

9
9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9

注：此处算法的稳定性并未得到实现，算法本身是能够实现稳定性的，实际上为了保证稳定性，应该倒序出数或者引入新的空间，但是此处只是模拟排序的介绍，并未做过多延伸。

算法限制

计数排序在有限的范围内使用效果较好，但是很明显的有如下限制：

• 因为利用连续空间，可能造成极大浪费空间而且范围受限，比如上述例子只能排序10000之内的正整数
• 直接不作处理的话无法排序小数和负数
• 受数据影响非常之大，比如1000万个1-100的数字排序，效果会非常好，但是极端来看1 1000000000的两个序列的排序，效率会非常之差