1、问题引入
之前的堆排序、快速排序都是基于输入元素间的比较，这类排序叫做比较排序，对于n个元素的比较排序可以证明其在最坏情况下都要用O（nlgn）次比较来进行排序，本节中将讨论三种以线性时间运行的算法：计数排序、基数排序、桶排序，这些算法都用非比较的一些操作来确定排序顺序。
2、算法讨论
2.1 计数排序
计数排序假设n个输入元素中的每一个都是介于0到k之间的整数（k为某个整数），其基本思想是：对于每一个输入元素x，确定出小于x的元素个数。有了这一信息，就可以吧x直接放到它在最终输出数组中的位置上，例如，如果有17个元素小于x，则x就属于第18个输出位置。
在计数排序中，假定输入数组是A[1...n]，length[A]=n.另外还需要两个数组：存放排序结果的B[1...n],以及提供临时存储区的C[0...k]。
具体实现代码如下：
View Code
1 #include<stdio.h>
2 #include<malloc.h>
3 void countingsort(int a[],int b[],int n,int k);
4 void countingsort(int a[],int b[],int n,int k)
5 {
6 int i;
7 int *c=(int*)malloc(sizeof(int)*(k+1));
8 //利用三个for循环实现c[i]的初始化
9 for(i=0;i<=k;i++)
10 c[i]=0;
11 for(i=0;i<n;i++)
12 c[a[i]]+=1;
13 for(i=1;i<=k;i++)
14 c[i]=c[i]+c[i-1];
15 //for(i=0;i<=k;i++)
16 // printf("%d ",c[i]);
17
18 for(int j=n-1;j>=0;j--)//注意a[],b[]数组下标开始顺序
19 {
20 b[c[a[j]]-1]=a[j];
21 c[a[j]]-=1;
22 }
23 }
24 void main()
25 {
26 int k=5,n=8;
27 int a[8]={2,5,3,0,2,3,0,3};
28 int b[8];
29
30 printf("before sort:\n");
31 for(int j=0;j<8;j++)
32 printf("%d ",a[j]);
33 countingsort(a,b,n,k);
34 printf("after sort:\n");
35 for(int i=0;i<8;i++)
36 printf("%d ",b[i]);
37 }
2.2 基数排序
基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法，例如关键字是数值，且其值都在0《k《999之间，则可以把每一个十进制数字看成一个关键字，即认为k由3个关键字（k1,k2,k3)组成，其中k1为个位数，k2为十位数，k3为百位数，例如三位的数值排序，可以设radix（=10）个队列，d=3；按照LSD进行排序，只要从最低位关键字起，按照关键字的不同值将序列中记录“分配”到RADIX队列后再“收集”，如此重复d次，这种方法就是基数排序。其中“基”是指radix的取值。
本次实现中采用链队列：
基本算法过程如下：
具体算法如上图所示，下面给出具体实现代码：
View Code
1 #include"queue.h"
2 #include<stdio.h>
3 #define keysize 3//关键字位数为3
4 #define radix 10//基数为10
5 void radixsort(int r[],int n);
6 void distribute(int r[],linkqueue b[],int j,int n);
7 void collect(int r[],linkqueue b[]);
8 void radixsort(int r[],int n)
9 {
10 int i;
11 linkqueue b[radix];
12 for(i=0;i<radix;i++)
13 initqueue(b[i]);
14 for(i=keysize-1;i>=0;i--)
15 {
16 distribute(r,b,i,n);
17 collect(r,b);
18 }
19 }
20 void distribute(int r[],linkqueue b[],int j,int n)
21 {
22 int i,k,t;
23 j=keysize-j;
24 for(i=0;i<n;i++)
25 {
26 k=r[i];
27 for(t=1;t<j;t++)k=k/10;
28 k=k%10;
29 enqueue(b[k],r[i]);
30 }
31 }
32 void collect(int r[],linkqueue b[])
33 {
34 int e,i=0,j;
35 for(j=0;j<radix;j++)
36 while(!queueempty(b[j]))
37 {
38 dequeue(b[j],e);
39 r[i++]=e;
40 }
41 }
42 void main()
43 {
44 int i,n=7;
45 int r[7]={329,457,657,839,436,720,355};
46 radixsort(r,n);
47 for(i=0;i<7;i++)
48 printf("%d ",r[i]);
49 }
2.3 桶排序
当桶排序的输入符合均匀分布时，即可以以线性期望时间运行。与计数排序类似，桶排序也对输入作了某种假设，因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则假设输入由一个随机过程产生，该过程将元素均匀而独立的分布在区间[0,1)上。
桶排序的思想就死把区间[0,1）划分成n个相同大小的子区间，或称桶。然后，将n个输入数分布到各个桶中去。因为输入数均匀且独立分布在[0,1)上，所以，一般不会有很多数落在一个桶中的情况。为了得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。
在桶排序算法的代码中，假设输入的是一个含n个元素的数组A，且每个元素满足0《A[i]<1.另外，还需要一个辅助数组B[0..n-1]来存放链表（桶），并且可以用某种机制来维护这些表。
具体的实现代如下：
View Code
1 #include<stdio.h>
2 #include<stdlib.h>
3 struct keyNum
4 {
5 double key;//关键字
6 struct keyNum *next;
7 };
8 struct keyNum*hash[100];
9 struct keyNum* insertHash(struct keyNum*,double);//关键字插入链表
10 void print(struct keyNum*);//打印链表
11 void main()
12 {
13 int i,k,n=10,num=10;//n表示划分的桶的个数,num表示输入元素个数。
14 double a[10]={0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68 };
15 struct keyNum *head=NULL;
16 for(i=0;i<num;i++)
17 hash[i]=NULL;
18
19 for(i=0;i<num;i++)
20 {
21 k=int(a[i]*10);
22 hash[k]=insertHash(hash[k],a[i]);//将关键字k插入到哈希值为m的链表中
23 }
24 printf("排序前为：\n");
25 for(i=0;i<num;i++)
26 printf(" %f",a[i]);
27 printf("\n");
28
29 printf("排序结果为：\n");
30 for(i=0;i<num;i++)
31 print(hash[i]);
32 }
33 struct keyNum * insertHash(struct keyNum*head,double m)
34 {
35 struct keyNum *p0,*p1,*p2,*temp;
36 temp=(struct keyNum*)malloc(sizeof(struct keyNum));
37 temp->key=m;
38 p1=head;
39 p0=temp;//要插入的节点（值为m);
40 if(head==NULL)//1，原来的链表为空，插入到head后
41 {
42 head=p0;
43 p0->next=NULL;
44 }
45 else//原来的链表不为空
46 {
47 while((p0->key>p1->key)&&(p1->next!=NULL))//移动到适当位置
48 {
49 p2=p1;
50 p1=p1->next;
51 }
52 if(p0->key<=p1->key)
53 {
54 if(head==p1)head=p0;//2，插入到第一个节点之前
55 else p2->next=p0;//3,插入到p2指向的节点之后
56 p0->next=p1;
57 }
58 else//4,插入到结尾处
59 {
60 p1->next=p0;
61 p0->next=NULL;
62 }
63 }
64 return(head);
65 }
66
67 void print(struct keyNum*head)//打印链表head
68 {
69 struct keyNum*p;
70 p=head;
71 if(head!=NULL)
72 {
73 do
74 {
75 printf(" %f",p->key);
76 p=p->next;
77 }while(p!=NULL);
78 }
79 else{}
80 }
3、小结
具体的代码实现参见算法就可以很容易完成，不过没有给出具体的时间复杂度分析。。
4、参考文献：
（1）算法导论
（2）数据结构