线性时间排序

以下几种排序算法的时间复杂度为O(n)，因为它们使用的是基于数字本身的排序。

(1) 桶排序!

基本思想：设计 M 个桶，根据元素本身进行分配。因为 M 个桶是按顺序排列的，所以分配元素之后元素也会按顺序排列。

待排序的数据范围不太大时可以考虑这样排序（比如1~1000可以考虑，而1~100000就必须用快速排序）。

下面假设每个数都位于区间[1, M]。

int cnt[M]; memset(cnt,0,sizeof(cnt)); for (int i=0; i<N; i++)  cnt[a]++; // 从cnt[0]开始挨个列举就行了。例如 for (int i=0; i<M; i++)  while ((cnt--)>0)   cout<<i<<" ";

(2) 计数排序

基本思想：对于序列中的每一元素 x,确定序列中小于 x 的元素的个数。下面假设每个数都位于区间[1, m]。

int a[N], b[N], cnt[M]; …… memset(cnt,0,sizeof(cnt)); for (int i=0;i<n;i++) cnt[a]++; for (int i=1;i<M;i++) cnt+=cnt[i-1]; for (int i=n-1;i>0;i--) { b[cnt[a]] = a;  cnt[a]--; } // 输出结果 for (int i=0;i<n;i++) cout<<b<<' ';

(3) 基数排序*

基本思想：对 n 个元素依次按 k,k-1,...1位上的数字进行桶排序。

int tmp[N], cnt[10]; int n; int maxbit(int *data, int n)   {							// 辅助函数，求数据的最大位数
int d = 1;							// 保存最大的位数
int p =10;   for (int i = 0;i < n; i++)    while (data >= p)     p *= 10, d++;  return d; }   void radixsort(int *data, int n)							// 基数排序
{	int d = maxbit(data,n);  int i,j,k;  int radix = 1;   for (i = 1; i<= d;i++)						// 进行d次排序
	{   for (j = 0;j < 10;j++)     cnt[j] = 0;						// 每次分配前清空计数器
	for (j = 0;j < n; j++)   {     k = (data[j]/radix)%10;						// 统计每个桶中的记录数
	cnt[k]++;   }   for (j = 1;j < 10;j++)    cnt[j] = cnt[j-1] + cnt[j];						// 将tmp中的位置依次分配给每个桶
		for (j = n-1;j >= 0;j--)					// 将所有桶中记录依次收集到tmp中
		{  k = (data[j]/radix)%10;  cnt[k]--;  tmp[cnt[k]] = data[j]; } for (j = 0;j < n;j++)     data[j] = tmp[j];  radix = radix*10;					// 将临时数组的内容复制到data中
} }