/* *From the art of computer programming:vol 3:Sorting and Searching *時間：2012年3月6日21:02:32 *作者：張超 *Email:uestczhangchao@gmail.com */#include <iostream> using namespace std; void Distribution_Counting(int array[], int arraylen) {int *tmp = new int[arraylen];int *count = NULL;int i,j;int minvalue=INT_MAX, maxvalue=INT_MIN;int valuescope;memset(tmp,0,sizeof(int)*arraylen);for (i=0; i<arraylen; i++){if (array[i]<minvalue){minvalue=array[i];}if (array[i]>maxvalue){maxvalue = array[i];}}valuescope = maxvalue-minvalue+1;count = new int[valuescope];memset(count,0,sizeof(int)*valuescope);//統計array內的數字在minvalue和maxvalue范圍的出現次數for (i=0; i<arraylen; i++){count[array[i]-minvalue]++;}//統計minvalue和maxvalue范圍內，不小于該范圍內某個數的出現頻數//count[i]對應小于value+i的數出現的次數for (i=1; i<valuescope; i++){count[i] = count[i] + count[i-1];}//依次輸出每個數字，輸出的順序為non-descending順序，并且保證是有序的for (j=arraylen-1;j>=0;j--){取出該關鍵字出現的次數i = count[array[j]-minvalue];tmp[i-1] = array[j];--count[array[j]-minvalue];}//將結果拷貝到array數組中for (i=0; i<arraylen; i++){array[i] = tmp[i];}delete []tmp;delete []count;}int main() {int data[] = {8,5,4,5,6,10};int size = sizeof(data)/sizeof(int);Distribution_Counting(data,size);for(int i=0; i<size;i++){cout <<" " << data[i] << " ";}cout << endl;return 0; }

轉載于:https://www.cnblogs.com/justinzhang/archive/2012/03/06/2382673.html

總結

以上是生活随笔為你收集整理的distribution counting—a sorting method from aocp的全部內容，希望文章能夠幫你解決所遇到的問題。

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