為什么80%的碼農都做不了架構師？>>> ??

假設n個輸入元素中每一個均介于0~k之間，k為最大值，這里k為整數。如果k=O(n), 則計數排序的運行時間為θ(n)。

計數排序的核心思想是：對于每個元素x，統(tǒng)計出小于等于x元素的個數，利用該信息，就可以確定每個元素x在最終數組中的位置。比如小于等于x的元素個數有17個，則該元素的最終位置在17-1=16.

計數排序的偽代碼如下:

其中數組A為輸入數組，數組B為排序后輸出數組，k為數組A元素中最大值，偽代碼中少個數組長度的參數，自行加上。

line 4~5 統(tǒng)計數組A中每個元素A[j]出現次數.

line 7~8 統(tǒng)計數組A中小于等于i(<0i<k)的元素個數.

line 10~12 根據小于等于A[j]的個數直接定位A中每個元素的位置，因為可能有相同元素，所以每次同時遞減 小于等于A[j]的個數.

根據偽代碼很同意得出計數排序的運行時間為θ(n)。

計數排序一個重要的特性就是它是穩(wěn)定的: 相同值元素在最終數組中的相對次序同他們在輸入數組中相同。

下面是數組A[] = {2,5,3,0,2,3,0,3}數組排序的全過程示意圖:

個人代碼如下:

/************************************************************************/ /*?author:?alex?????????????????????????????????????????????????????????*/ /*?time:?1/9?2014??????????????????????????????????????????????????????*/ /************************************************************************/ #include?<iostream> using?namespace?std;int?count_sort(int?array_src[],?int?array_dst[],?int?max_num_k,?int?array_length); void?print_array(int?array[],?int?length);int?main(void) {int?array_src[]?=?{2,5,3,0,2,3,0,3};int?array_length?=?sizeof(array_src)/sizeof(array_src[0]);int?max_num_of_array_src?=?5;?//?get?max?from?array_src.int?*array_dst?=?(int?*)malloc(array_length*sizeof(int));if(NULL?==?array_dst){cout?<<?"array_dst?malloc?error?!"?<<?endl;return?-1;}memset(array_dst,?0,?array_length*sizeof(int));cout?<<?"Before?count?sort?:?"?<<?endl;print_array(array_src,?array_length);count_sort(array_src,?array_dst,?max_num_of_array_src,?array_length);cout?<<?"After?count?sort?:?"?<<?endl;print_array(array_dst,?array_length);free(array_dst);array_dst?=?NULL;return?0; }int?count_sort(int?array_src[],?int?array_dst[],?int?max_num_k,?int?array_length) {int?i?=?0,?j?=?0;int?*p_count_array?=?(int?*)malloc((max_num_k+1)*sizeof(int));if(NULL?==?p_count_array){cout?<<?"p_count_array?malloc?error?!"?<<?endl;return?-1;}memset(p_count_array,?0?,?(max_num_k+1)*sizeof(int));for(j?=?0;?j?<?array_length;?j++){//p_count_array?contain?the?numbers?of?items?that?equal?to?array[j]p_count_array[array_src[j]]?=?p_count_array[array_src[j]]?+?1;}for(i?=?1;?i?<=?max_num_k;?i++){//p_count_array?contain?the?numbers?of?items?that?less?and?equal?to?ip_count_array[i]?=?p_count_array[i]?+?p_count_array[i-1];}for(j?=?array_length-1;?j?>=0;?j--){//because?numbers?of?items?that?less?and?equal?to?array_src[j]?is?p_count_array[array_src[j]],?//so?we?can?confirm?the?position?of?array_src[j],?locate?array_src[j]?to?//array_dst[p_count_array[array_src[j]]?-1],?and?subtract?p_count_array[array_src[j]],?then//the?less?or?same?items?(if?any)?locate?before?witch.?for?example?if?array_src[j]?=?3,//and?p_count_array[array_src[j]]?is?2(mean?less?and?equal?to?3?exist?2?items),?so?we?can//locate?3?to?position?2-1=1,?the?last?less?or?equal?items?locate?before?it.array_dst[p_count_array[array_src[j]]-1]?=?array_src[j];p_count_array[array_src[j]]?=?p_count_array[array_src[j]]?-?1;}free(p_count_array);p_count_array?=?NULL;return?0; }void?print_array(int?array[],?int?length) {int?i?=?0;for(i=0;?i<length;?i++){cout?<<?array[i]?<<?"?";}cout?<<?endl?<<?endl; }

為了方便代碼實現，本文下標從0下表開始，同算法導論書中表述略有出處。如有任何問題，歡迎各位指正。

因為統(tǒng)計計數對數據限制過多，要求最大數比總個數小，時間，空間復雜度才可控，所以實際項目中試用很少。

reference :

算法導論英文版第三版

轉載于:https://my.oschina.net/amince/blog/308919

總結

以上是生活随笔為你收集整理的counting sort (计数排序) algorithm的全部內容，希望文章能夠幫你解決所遇到的問題。

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