隨筆 - 62 文章 - 96 trackbacks - 0

2007年4月

日

一

二

三

四

五

六

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

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

積分與排名

積分 - 235137
排名 - 108

閱讀排行榜

評(píng)論排行榜

計(jì)數(shù)排序

k為數(shù)組a中最大值，n為數(shù)組a的長(zhǎng)度。
countSort用于對(duì)整型數(shù)組排序，時(shí)間復(fù)雜度為O(k+n)。
當(dāng)k = O(n)時(shí)，時(shí)間復(fù)雜度變?yōu)镺(n)。
c[i]記錄a數(shù)組中數(shù)值大于或等于i的個(gè)數(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 閱讀(868) 評(píng)論(0) 編輯收藏引用所屬分類: C++之路

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

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

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