青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 62 文章 - 96 trackbacks - 0

2007年4月

日

一

二

三

四

五

六

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

校內網

積分與排名

積分 - 236984
排名 - 108

閱讀排行榜

評論排行榜

計數排序

k為數組a中最大值，n為數組a的長度。
countSort用于對整型數組排序，時間復雜度為O(k+n)。
當k = O(n)時，時間復雜度變為O(n)。
c[i]記錄a數組中數值大于或等于i的個數

int countSort(int * a, int k, int n)

{

int i;

int * c = new int [k+1], * b = new int [n];

for(i = 0; i <= k; i++)

c[i] = 0;

for(i = 0; i < n; i++)

c[a[i]]++;

for(i = 1; i <= k; i++)

c[i] += c[i-1];

for(i = n - 1; i >= 0; i--)

{

b[c[a[i]]-1] = a[i];

c[a[i]]--;

}

for(i = 0; i < n; i++)

a[i] = b[i];

delete [] b;

delete [] c;

return 0;

}

posted on 2007-04-03 00:57 beyonlin 閱讀(883) 評論(0) 編輯收藏引用所屬分類: C++之路

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 一道算法題引發的動態內存管理的思考再談子集樹位運算求子集樹字符串hash函數優先隊列用法計數排序《C++ Primer》之讀書筆記七插入排序泛型算法《C++ Primer》之讀書筆記六《C++ Primer》之讀書筆記五

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

最新隨筆

積分與排名

最新評論

閱讀排行榜

評論排行榜