前面的文章已经介绍了几种排序算法，如插入排序（直接插入排序，折半插入排序，希尔排序）、交换排序（冒泡排序，快速排序）、选择排序（简单选择排序，堆排序）、2-路归并排序（可以参考前一篇文章：各种内部排序算法的实现）等，这些排序算法都有一个共同的特点，就是基于比较。

本文将介绍三种非比较的排序算法：计数排序，基数排序，桶排序。它们将突破比较排序的Ω(nlgn)下界，以线性时间运行。

一、比较排序算法的时间下界

所谓的比较排序是指通过比较来决定元素间的相对次序。

“定理：对于含n个元素的一个输入序列，任何比较排序算法在最坏情况下，都需要做Ω(nlgn)次比较。”
也就是说，比较排序算法的运行速度不会快于nlgn，这就是基于比较的排序算法的时间下界。

通过决策树（Decision-Tree）可以证明这个定理，关于决策树的定义以及证明过程在这里就不赘述了。读者可以自己去查找资料，这里推荐大家看一看麻省理工学院公开课：算法导论的《MIT公开课：线性时间排序》。

根据上面的定理，我们知道任何比较排序算法的运行时间不会快于nlgn。那么我们是否可以突破这个限制呢？当然可以，接下来我们将介绍三种线性时间的排序算法，它们都不是通过比较来排序的，因此，下界Ω(nlgn)对它们不适用。

二、计数排序（Counting Sort）

计数排序的基本思想就是对每一个输入元素x，确定小于x的元素的个数，这样就可以把x直接放在它在最终输出数组的位置上，例如：

算法的步骤大致如下：

①.找出待排序的数组中最大和最小的元素

②.统计数组中每个值为i的元素出现的次数，存入数组C的第i项

③.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

④.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

C++代码如下：

/************************************************************************* 
  > File Name: CountingSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include 
using namespace std; 
 
/* 
 *计数排序：A和B为待排和目标数组，k为数组中最大值,len为数组长度 
 */ 
void CountingSort(int A[], int B[], int k, int len) 
{ 
  int C[k+1]; 
  for(int i=0; inext = ist; 
    } 
  } 
 
  for(int i=0; ivalue; 
      p = p->next; 
    } 
  } 
} 
 
/* 输出数组 */ 
void print(int A[], int len) 
{ 
  for(int i=0; i