題目：某公司有幾萬名員工，請(qǐng)完成一個(gè)時(shí)間復(fù)雜度為O(n)的算法對(duì)該公司員工的年齡作排序，可使用O(1)的輔助空間。

分析：排序是面試時(shí)經(jīng)常被提及的一類題目，我們也熟悉其中很多種算法，諸如插入排序、歸并排序、冒泡排序，快速排序等等。這些排序的算法，要么是O(n2)的，要么是O(nlogn)的。可是這道題竟然要求是O(n)的，這里面到底有什么玄機(jī)呢？

題目特別強(qiáng)調(diào)是對(duì)一個(gè)公司的員工的年齡作排序。員工的數(shù)目雖然有幾萬人，但這幾萬員工的年齡卻只有幾十種可能。上班早的人一般也要等到將近二十歲才上班，一般人再晚到了六七十歲也不得不退休。

由于年齡總共只有幾十種可能，我們可以很方便地統(tǒng)計(jì)出每一個(gè)年齡里有多少名員工。舉個(gè)簡單的例子，假設(shè)總共有5個(gè)員工，他們的年齡分別是25、24、26、24、25。我們統(tǒng)計(jì)出他們的年齡，24歲的有兩個(gè)，25歲的也有兩個(gè)，26歲的一個(gè)。那么我們根據(jù)年齡排序的結(jié)果就是：24、24、25、25、26，即在表示年齡的數(shù)組里寫出兩個(gè)24、兩個(gè)25和一個(gè)26。

void?SortAges(int?ages[],?int?length) {if(ages?==?NULL?||?length?<=?0)return;const?int?oldestAge?=?99;int?timesOfAge[oldestAge?+?1];for(int?i?=?0;?i?<=?oldestAge;?++?i)timesOfAge[i]?=?0;for(int?i?=?0;?i?<?length;?++?i){int?age?=?ages[i];if(age?<?0?||?age?>?oldestAge)throw?new?std::exception("age?out?of?range.");++?timesOfAge[age];}int?index?=?0;for(int?i?=?0;?i?<=?oldestAge;?++?i){for(int?j?=?0;?j?<?timesOfAge[i];?++?j){ages[index]?=?i;++?index;}} }

在上面的代碼中，允許的范圍是0到99歲。數(shù)組timesOfAge用來統(tǒng)計(jì)每個(gè)年齡出現(xiàn)的次數(shù)。某個(gè)年齡出現(xiàn)了多少次，就在數(shù)組ages里設(shè)置幾次該年齡。這樣就相當(dāng)于給數(shù)組ages排序了。該方法用長度100的整數(shù)數(shù)組輔助空間換來了O(n)的時(shí)間效率。由于不管對(duì)多少人的年齡作排序，輔助數(shù)組的長度是固定的100個(gè)整數(shù)，因此它的空間復(fù)雜度是個(gè)常數(shù)，即O(1)。

轉(zhuǎn)載于:https://blog.51cto.com/10541556/1831301

總結(jié)

以上是生活随笔為你收集整理的算法复杂度为O(N) 的排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。