1、序言

這是《漫談經(jīng)典排序算法系列》第五篇，給出了三種線性時(shí)間排序，分別是計(jì)數(shù)排序、基數(shù)排序、桶排序。

各種排序算法的解析請(qǐng)參考如下：

 

《漫談經(jīng)典排序算法:一、從簡(jiǎn)單選擇排序到堆排序的深度解析》

《漫談經(jīng)典排序算法:二、各種插入排序解析及性能比較》

《漫談經(jīng)典排序算法:三、冒泡排序 && 快速排序》

《漫談經(jīng)典排序算法:四、歸并排序》

《漫談經(jīng)典排序算法:五、線性時(shí)間排序(計(jì)數(shù)、基數(shù)、桶排序)》

《漫談經(jīng)典排序算法:六、各種排序算法總結(jié)》

注：為了敘述方便，本文以及源代碼中均不考慮A[0],默認(rèn)下標(biāo)從1開(kāi)始。

2、計(jì)數(shù)排序

          2.1 引出

            前面四篇博客中，所有的排序算法都存在比較，都可以稱(chēng)為”比較排序“。比較排序的下界為o（nlogn）。那么有沒(méi)有時(shí)間復(fù)雜度為o（n）的線性時(shí)間排序算法呢？計(jì)數(shù)排序便是很基礎(chǔ)的一種線性時(shí)間排序，它是基數(shù)排序的基礎(chǔ)?；舅枷胧牵簩?duì)每一個(gè)元素x，確定小于x的元素個(gè)數(shù)，就可以把x直接放到它在有序序列中的位置上。過(guò)程描述：假設(shè)待排序序列a中值的范圍[0,k],其中k表示待排序序列中的最大值。首先用一個(gè)輔助數(shù)組count記錄各個(gè)值在a中出現(xiàn)的次數(shù)，比如count[i]表示i在a中的個(gè)數(shù)。然后依次改變count中元素值，使count[i]表示a中不大于i的元素個(gè)數(shù)。然后從后往前掃描a數(shù)組，a中的元素根據(jù)count中的信息直接放到輔助數(shù)組b中。最后把有序序列b復(fù)制到a。

          2.2 代碼

[cpp] view plaincopy?

1. #include<stdio.h>  
2. #include<stdlib.h>  
3.   
4. //計(jì)數(shù)排序,n為數(shù)組a的記錄個(gè)數(shù)，k為記錄中最大值  
5. void countingSort(int *a,int n,int k)  
6. {  
7.     int i;  
8.     int *count=(int *)malloc(sizeof(int)*(k+1));  
9.     int *b=(int *)malloc(sizeof(int)*(n+1));  
10.     //初始化計(jì)數(shù)數(shù)組count  
11.     for(i=0;i<=k;i++)  
12.         *(count+i)=0;  
13.     //計(jì)算等于a[i]的記錄個(gè)數(shù)  
14.     for(i=1;i<=n;i++)  
15.         (*(count+a[i]))++;  
16.     //計(jì)算小于等于a[i]的記錄個(gè)數(shù)  
17.     for(i=1;i<=k;i++)  
18.         *(count+i) += *(count+i-1);  
19.     //掃描a數(shù)組，把各個(gè)元素放在有序序列中相應(yīng)的位置上  
20.     for(i=n;i>=1;i--){  
21.         *(b + *(count + a[i]))=a[i];  
22.         (*(count+a[i]))--;   
23.     }  
24.     for(i=1;i<=n;i++)  
25.         a[i]=*(b+i);  
26.     free(count);  
27.     free(b);  
28. }  
29.   
30. void main()  
31. {  
32.     int i;  
33.     int a[7]={0,3,5,8,9,1,2};//不考慮a[0]  
34.     countingSort(a,6,9);  
35.     for(i=1;i<=6;i++)  
36.         printf("%-4d",a[i]);  
37.     printf("\n");  
38. }  

          2.3 效率分析

從代碼來(lái)看，計(jì)數(shù)排序有5個(gè)for循環(huán)，其中三個(gè)時(shí)間是n，兩個(gè)時(shí)間是k。所以總時(shí)間T(3n+2k),時(shí)間復(fù)雜度o（n+k），不管是在最壞還是最佳情況下，此時(shí)間復(fù)雜度不變.此外，計(jì)數(shù)排序是穩(wěn)定的，輔助空間n+k,這個(gè)空間是比較大的，計(jì)數(shù)排序?qū)Υ判蛐蛄杏屑s束條件(如前面我們假設(shè)待排序序列a中值的范圍[0,k],其中k表示待排序序列中的最大值)，元素值需是非負(fù)數(shù)，k太大的話會(huì)大大降低效率。這里要注意的是 “掃描a數(shù)組把各個(gè)元素放在有序序列相應(yīng)的位置上” 這步為什么要從后往前掃描a數(shù)組呢？大家想一想計(jì)數(shù)排序的過(guò)程就知道，因?yàn)閺那皰呙鑼?dǎo)致計(jì)數(shù)排序不穩(wěn)定，前面說(shuō)了，計(jì)數(shù)排序是基數(shù)排序的基礎(chǔ)，所以它的穩(wěn)定性直接影響到基數(shù)排序的穩(wěn)定。

3、基數(shù)排序

          3.1 引出

            在計(jì)數(shù)排序中，當(dāng)k很大時(shí)，時(shí)間和空間的開(kāi)銷(xiāo)都會(huì)增大（可以想一下對(duì)序列{8888,1234,9999}用計(jì)數(shù)排序，此時(shí)不但浪費(fèi)很多空間，而且時(shí)間方面還不如比較排序）。于是可以把待排序記錄分解成個(gè)位(第一位)、十位(第二位)....然后分別以第一位、第二位...對(duì)整個(gè)序列進(jìn)行計(jì)數(shù)排序。這樣的話分解出來(lái)的每一位不超過(guò)9，即用計(jì)數(shù)排序序列中最大值是9.

          3.2 代碼

[cpp] view plaincopy?

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. #include<math.h>  
4.   
5.   
6. //計(jì)數(shù)排序,n為數(shù)組a的記錄個(gè)數(shù)，k為記錄中最大值，按第d位排序  
7. void countingSort(int *a,int n,int k,int d)  
8. {  
9.     int i;  
10.     int *count=(int *)malloc(sizeof(int)*(k+1));  
11.     int *b=(int *)malloc(sizeof(int)*(n+1));  
12.     //初始化計(jì)數(shù)數(shù)組count  
13.     for(i=0;i<=k;i++)  
14.         *(count+i)=0;  
15.     //計(jì)算等于a[i]在d位(a[i]/(int)pow(10,d-1)%10)的記錄個(gè)數(shù)  
16.     for(i=1;i<=n;i++)  
17.         (*(count+a[i]/(int)pow(10,d-1)%10))++;  
18.   
19.     //計(jì)算小于等于a[i]在d位(a[i]/(int)pow(10,d-1)%10)的記錄個(gè)數(shù)  
20.     for(i=1;i<=k;i++)  
21.         *(count+i) += *(count+i-1);  
22.     //掃描a數(shù)組，把各個(gè)元素放在有序序列中相應(yīng)的位置上  
23.     for(i=n;i>=1;i--){  
24.         *(b + *(count + a[i]/(int)pow(10,d-1)%10))=a[i];  
25.         (*(count+a[i]/(int)pow(10,d-1)%10))--;   
26.     }  
27.     for(i=1;i<=n;i++)  
28.         a[i]=*(b+i);  
29.     free(count);  
30.     free(b);  
31. }  
32.   
33.   
34. //基數(shù)排序,n為數(shù)組a的記錄個(gè)數(shù)，每一個(gè)記錄中有d位數(shù)字  
35. void radixSort(int *a,int n,int d)  
36. {  
37.     int i;  
38.     for(i=1;i<=d;i++){  
39.         countingSort(a,6,9,i);  
40.     }  
41. }  
42.   
43. void main()  
44. {  
45.     int i;  
46.     int a[7]={0,114,118,152,114,111,132};//不考慮a[0]  
47.     radixSort(a,6,3);  
48.     for(i=1;i<=6;i++)  
49.         printf("%-4d",a[i]);  
50.     printf("\n");  
51. }  

          3.3 效率分析

基數(shù)排序時(shí)間T(n)=d*(2k+3n),其中d是記錄值的位數(shù)，(2k+3n)是每一趟計(jì)數(shù)排序時(shí)間，上文分析過(guò)了，k不超過(guò)9，d的值一般也很小，k、d都可以看成是一個(gè)很小的常數(shù)，所以時(shí)間復(fù)雜度o（n）。最壞最佳情況并不改變時(shí)間復(fù)雜度。基數(shù)排序是穩(wěn)定的。輔助空間同計(jì)數(shù)排序k+n.

4、桶排序

          4.1 引出

            同計(jì)數(shù)排序一樣，桶排序也對(duì)待排序序列作了假設(shè)，桶排序假設(shè)序列由一個(gè)隨機(jī)過(guò)程產(chǎn)生，該過(guò)程將元素均勻而獨(dú)立地分布在區(qū)間[0,1)上?；舅枷胧牵喊褏^(qū)間[0,1)劃分成n個(gè)相同大小的子區(qū)間，稱(chēng)為桶。將n個(gè)記錄分布到各個(gè)桶中去。如果有多于一個(gè)記錄分到同一個(gè)桶中，需要進(jìn)行桶內(nèi)排序。最后依次把各個(gè)桶中的記錄列出來(lái)記得到有序序列。

          4.2 代碼

[cpp] view plaincopy?

1. #include<stdio.h>  
2. #include<stdlib.h>  
3.   
4. //桶排序  
5. void bucketSort(double* a,int n)  
6. {  
7.     //鏈表結(jié)點(diǎn)描述  
8.     typedef struct Node{  
9.         double key;  
10.         struct Node * next;   
11.     }Node;  
12.     //輔助數(shù)組元素描述  
13.     typedef struct{  
14.          Node * next;  
15.     }Head;  
16.     int i,j;  
17.     Head head[10]={NULL};  
18.     Node * p;  
19.     Node * q;  
20.     Node * node;  
21.     for(i=1;i<=n;i++){  
22.         node=(Node*)malloc(sizeof(Node));  
23.         node->key=a[i];  
24.         node->next=NULL;  
25.         p = q =head[(int)(a[i]*10)].next;  
26.         if(p == NULL){  
27.             head[(int)(a[i]*10)].next=node;  
28.             continue;  
29.         }  
30.         while(p){  
31.             if(node->key < p->key)  
32.                 break;  
33.             q=p;  
34.             p=p->next;  
35.         }  
36.         if(p == NULL){  
37.             q->next=node;  
38.         }else{  
39.             node->next=p;  
40.             q->next=node;  
41.         }  
42.     }  
43.     j=1;  
44.     for(i=0;i<10;i++){  
45.         p=head[i].next;  
46.         while(p){  
47.             a[j++]=p->key;  
48.             p=p->next;  
49.         }  
50.     }  
51. }  
52.   
53. void main()  
54. {  
55.     int i;  
56.     double a[13]={0,0.13,0.25,0.18,0.29,0.81,0.52,0.52,0.83,0.52,0.69,0.13,0.16};//不考慮a[0]  
57.     bucketSort(a,12);  
58.     for(i=1;i<=12;i++)  
59.         printf("%-6.2f",a[i]);  
60.     printf("\n");  
61. }  

          4.3 效率分析

當(dāng)記錄在桶中分布均勻時(shí)，即每個(gè)桶只有一個(gè)元素，此時(shí)時(shí)間復(fù)雜度o（n）。因此桶排序適合對(duì)很少重復(fù)的記錄排序。輔助空間2n。桶排序是穩(wěn)定的排序，實(shí)現(xiàn)比較復(fù)雜。

5、附錄

      參考書(shū)籍:  《算法導(dǎo)論》