目錄 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ?1、計數排序介紹

? ? ? ?2、流程圖

? ? ? ?3、代碼實現

? ? ? ?4、性能分析

? ? ? ?5、參考資料

內容 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ?1、計數排序介紹 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ?什么是計數排序？

? ? ?計數排序是一種特殊的排序算法，之前介紹的排序算法需要對數進行兩兩比較，效率下界為θ(nlgn); ? 而計數排序不需要對數進行比較就可以進行排序；很神奇吧，只需要對待排序數組進行遍歷就可以排序，效率為Θ（n）。。哈哈，那么神奇，下面開講！！！！

? ? ? 限制：計數排序只能對非負整數（0，1，2，3...N）進行排序

? ? ? 排序思想：計數排序的基本思想就是對每一個輸入元素 x，確定出小于 x 的元素個數。有了這一信息，就可以把 x 直接放到它在最終輸出數組中的位置上。例如：有 10 個年齡不同的人，統計出有 8 個人的年齡比 A 小，那 A 的年齡就排在第 9 位，用這個方法可以得到其他每個人的位置，也就排好了序。

? ? ? ?2、流程圖 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? 排序算法步驟：

? ? ? ? 1）統計數組中每個值為 X 的元素出現的次數，存入數組 C 的第X 項

? ? ? ? 2）累加元素出現次數（計算不超過 X包括X 的元素的個數）

? ? ? ? 3) 將元素X依次放入到適當的位置

? ? ? 排序偽碼：

? ? ? ? ?CountSort(A,n,k) //A-待排序數組；n-排序數組元素個數；k-大于等于待排序數組元素最大值的某個整數? ? 步驟一流程圖?1）統計數組中每個值為 X 的元素出現的次數，存入數組 C 的第X 項

?

? ? 步驟二 流程圖 2）累加元素出現次數（計算不超過 X包括X 的元素的個數）

? ?步驟三流程圖 3）將元素X依次放入到適當的位置

? ? ? ?3、代碼實現（c++） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

1 #include <iostream> 2 #include <vector> 3 #include <time.h> 4 using namespace std; 5 6 #define N 10 //排序數組大小 7 #define K 100 //排序數組范圍0～K 8 9 void CountSort(vector<int> &A) 10 { 11 //找出待排序數組最大、最小值 12 int min,max; 13 min=max=A[0]; 14 for (int i=1;i<A.size();i++) 15 { 16 if (A[i]<min) min=A[i]; 17 else if (A[i]>max) max=A[i]; 18 } 19 //定義數組B存放排好的數 20 vector<int> B(A.size()); 21 //定義數組C，大小為（max-min+1）,C[i]為A中值為i的個數 22 vector<int> C(max-min+1); 23 for (int i=0;i<max-min+1;i++) C[i]=0;//初始為0 24 for(int i=0;i<A.size();i++) C[A[i]-min]++;//計數 25 for (int i=1;i<max-min+1;i++) C[i]+=C[i-1];//累加 26 for (int i=A.size()-1;i>=0;i--) 27 { 28 B[C[A[i]-min]-1]=A[i];//A中值倒序取出放到B中合適位置，并在C計數中減1 29 //因數組下標從0開始，所以減1 30 C[A[i]-min]--; 31 } 32 A.assign(B.begin(),B.end());//B賦給A 33 } 34 ////打印數組 35 void print_element(vector<int> A) 36 { 37 int len=A.size(); 38 for (int i=0;i<len;i++) 39 { 40 std::cout<<A[i]<<" "; 41 } 42 std::cout<<std::endl; 43 } 44 // 隨機參數排序數組,產生數組范圍0～k的整數 45 void Random(vector<int> &a,int n,int k) 46 { 47 int i=0; 48 srand( (unsigned)time( NULL ) ); 49 while(i<n) 50 { 51 a[i++]=rand()%k; 52 } 53 } 54 55 int main() 56 { 57 vector<int > vec_int(N); 58 Random(vec_int,N,K); 59 cout<<"源數組： "; 60 print_element(vec_int); 61 CountSort(vec_int); 62 cout<<"以排序數組： "; 63 print_element(vec_int); 64 65 system("PAUSE"); 66 return 0; 67 }

? ? ? ?4、性能分析 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? 分析性能好的快速排序和本節介紹的計數排序的效率【排序數組取值為0～100的整數，數組大小分別取100，1000，10000，100000測試】

數組大小N	快速排序（ms）	計數排序(ms)
100	0.153012	0.236982
1000	6.00759	4.61228
10000	58.4422	16.0187
100000	4176.58	169.768

?

? ? ? ? ?分析：當數組元素個數較大時，計數排序效率相當高！

? ? ? ? ?注意：當排序數組元素個數較少時效率會降低，并且數組范圍較大時內存消耗會相對增多。

? ? ? ? ?何時使用計數排序：

? ? ? ? ? 結： ?1）待排序數組為非負整數

? ? ? ? ? ? ? ? ? 2） and 數組范圍小，元素個數較多

? ? ? ?5、參考資料 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ?【1】http://blog.csdn.net/xyd0512/article/details/8261816

? ? ? ? ?【2】http://www.cnblogs.com/gaochundong/p/sorting_in_linear_time.html

? ? ? ? ?【3】http://www.cnblogs.com/xiao-cheng/archive/2011/10/05/2199657.html

轉載于:https://www.cnblogs.com/zhoutaotao/p/3997219.html

總結

以上是生活随笔為你收集整理的算法导论-排序（四）计数排序（线性时间排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。