隨筆 - 62 文章 - 96 trackbacks - 0

2025年8月

日

一

二

三

四

五

六

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

校內(nèi)網(wǎng)

積分與排名

積分 - 236541
排名 - 108

閱讀排行榜

評論排行榜

計數(shù)排序

k為數(shù)組a中最大值，n為數(shù)組a的長度。
countSort用于對整型數(shù)組排序，時間復(fù)雜度為O(k+n)。
當(dāng)k = O(n)時，時間復(fù)雜度變?yōu)镺(n)。
c[i]記錄a數(shù)組中數(shù)值大于或等于i的個數(shù)

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 閱讀(881) 評論(0) 編輯收藏引用所屬分類: C++之路

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

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理