之前講了三種常用的經(jīng)典排序。排序算法還有很多，例如選擇排序、計(jì)數(shù)排序、基數(shù)排序、插入排序、歸并排序和堆排序等等。堆排序是基于二叉樹(shù)的排序，以后再說(shuō)吧。先分享一個(gè)超酷的排序算法的視頻。
再來(lái)看一個(gè)具體的例子《小哼買(mǎi)書(shū)》來(lái)看看三個(gè)排序在應(yīng)用上的區(qū)別和局限性。 小哼的學(xué)校要建立一個(gè)圖書(shū)角，老師派小哼去找一些同學(xué)做調(diào)查，看看同學(xué)們都喜歡讀哪些書(shū)。小哼讓每個(gè)同學(xué)寫(xiě)出一個(gè)自己最想讀的書(shū)的 ISBN 號(hào)（你知道嗎？每本書(shū)都有唯一的 ISBN 號(hào)，不信話(huà)你去找本書(shū)翻到背面看看）。當(dāng)然有一些好書(shū)會(huì)有很多同學(xué)都喜歡，這樣就會(huì)收集到很多重復(fù)的 ISBN 號(hào)。小哼需要去掉其中重復(fù)的 ISBN 號(hào)，即每個(gè) ISBN 號(hào)只保留一個(gè)，也就說(shuō)同樣的書(shū)只買(mǎi)一本（學(xué)校真是夠摳門(mén)的）。然后再把這些 ISBN 號(hào)從小到大排序，小哼將按照排序好的 ISBN 號(hào)去書(shū)店去買(mǎi)書(shū)。請(qǐng)你協(xié)助小哼完成“去重”與“排序”的工作。
http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/z.1.png" alt="picturez.1" />
輸入有 2 行，第 1 行為一個(gè)正整數(shù)，表示有 n 個(gè)同學(xué)參與調(diào)查（n<=100）。第 2 行有 n 個(gè)用空格隔開(kāi)的正整數(shù)，為每本圖書(shū)的 ISBN 號(hào)（假設(shè)圖書(shū)的 ISBN 號(hào)在 1~1000 之間）。
輸出也是 2 行，第 1 行為一個(gè)正整數(shù)k，表示需要買(mǎi)多少本書(shū)。第 2 行為 k 個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大已排好序的需要購(gòu)買(mǎi)的圖書(shū) ISBN 號(hào)。 例如輸入
102040326740208930040015則輸出
8152032406789300400最后，程序運(yùn)行的時(shí)間限制為：1秒。
解決這個(gè)問(wèn)題的方法大致有兩種，第一種方法：先將這 n 個(gè)圖書(shū)的 ISBN 號(hào)去重，再進(jìn)行從小到大排序并輸出。第二種方法：先從小到大排序，輸出的時(shí)候再去重。這兩種方法都可以。
先來(lái)看第一種方法。通過(guò)第一節(jié)的學(xué)習(xí)我們發(fā)現(xiàn)桶排序稍加改動(dòng)正好可以起到去重的效果，因此我們可以使用桶排序的方法來(lái)解決此問(wèn)題。
#include <stdio.h>
int main()
{
int a[1001],n,i,t;
for(i=1;i<=1000;i++)
a[i]=0; //初始化
scanf("%d",&n); //讀入n
for(i=1;i<=n;i++) //循環(huán)讀入n個(gè)圖書(shū)的ISBN號(hào)
{
scanf("%d",&t); //把每一個(gè)ISBN號(hào)讀到變量t中
a[t]=1; //標(biāo)記出現(xiàn)過(guò)的ISBN號(hào)
}
for(i=1;i<=1000;i++) //依次判斷1~1000這個(gè)1000個(gè)桶
{
if(a[i]==1)//如果這個(gè)ISBN號(hào)出現(xiàn)過(guò)則打印出來(lái)
printf("%d ",i);
}
getchar();getchar();
return 0;
}
這種方法的時(shí)間復(fù)雜度是就是桶排序的時(shí)間復(fù)雜度為 O(N+M)。
第二種方法我們需要先排序再去重。排序我們可以用冒泡排序或者快速排序。
20 40 32 67 40 20 89 300 400 15
將這 10 個(gè)數(shù)從小到大排序之后為 15 20 20 32 40 40 67 89 300 400。
接下來(lái)，要在輸出的時(shí)候去掉重復(fù)的。因?yàn)槲覀円呀?jīng)排好序，因此相同的數(shù)都會(huì)緊挨在一起。只要在輸出的時(shí)候，預(yù)先判斷一下當(dāng)前這個(gè)數(shù) a 與前面一個(gè)數(shù) a[i-1]是否相同。如果相同則表示這個(gè)數(shù)之前已經(jīng)輸出過(guò)了，不同再次輸出。不同則表示這個(gè)數(shù)是第一次出現(xiàn)需要，則需要輸出這個(gè)數(shù)。
#include <stdio.h>
int main()
{
int a[101],n,i,j,t;
scanf("%d",&n); //讀入n
for(i=1;i<=n;i++) //循環(huán)讀入n個(gè)圖書(shū)ISBN號(hào)
{
scanf("%d",&a[i]);
}
//開(kāi)始冒泡排序
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j]>a[j+1])
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
printf("%d ",a[1]); //輸出第1個(gè)數(shù)
for(i=2;i<=n;i++) //從2循環(huán)到n
{
if( a[i] != a[i-1] ) //如果當(dāng)前這個(gè)數(shù)是第一次出現(xiàn)則輸出
printf("%d ",a[i]);
}
getchar();getchar();
return 0;
}
這種方法的時(shí)間復(fù)雜度由兩部分組成，一部分是冒泡排序時(shí)間復(fù)雜度是 O(N2)，另一部分是讀入和輸出都是 O(N)，因此整個(gè)算法的時(shí)間復(fù)雜度是 O(2N+N2)。相對(duì)于 N2 來(lái)說(shuō)，2N 可以忽略（我們通常忽略低階），最終該方法的時(shí)間復(fù)雜度是 O(N2)。
接下來(lái)我們還需要看下數(shù)據(jù)范圍。每個(gè)圖書(shū) ISBN 號(hào)都是 1~1000 之間的整數(shù)，并且參加調(diào)查的同學(xué)人數(shù)不超過(guò) 100，即 n<=100。之前已經(jīng)說(shuō)過(guò)，在粗略計(jì)算時(shí)間復(fù)雜度的時(shí)候，我們通常認(rèn)為計(jì)算機(jī)每秒鐘大約運(yùn)行 10 億次（當(dāng)然實(shí)際情況要更快）。因此以上兩種方法都可以在 1 秒鐘內(nèi)計(jì)算出解。如果題目圖書(shū) ISBN 號(hào)范圍不是在 1~1000 之間，而是 -2147483648~2147483647 之間的話(huà)，那么第一種方法就不可行了，因?yàn)槟銦o(wú)法申請(qǐng)出這么大數(shù)組來(lái)標(biāo)記每一個(gè) ISBN 號(hào)是否出現(xiàn)過(guò)。另外如果 n 的范圍不是小于等于 100 而是小于等于 10 萬(wàn)，那么第二種方法的排序部分也不能使用冒泡排序。因?yàn)轭}目要求的時(shí)間限制是 1 秒，使用冒泡排序?qū)?10 萬(wàn)個(gè)數(shù)的排序，計(jì)算機(jī)需要運(yùn)行 100 億次，需要 10 秒鐘，需要替換為快速排序，快速排序只需要 100000×log2100000≈100000×17≈170 萬(wàn)次，這還不到 0.0017 秒。是不是很神奇，同樣的問(wèn)題使用不同的算法竟然有如此之大的時(shí)間差距，這就是算法的魅力！
我們來(lái)回顧一下本章三種排序算法的時(shí)間復(fù)雜度。桶排序是最快的，它的時(shí)間復(fù)雜度是 O(N+M)；冒泡排序是 O(N2)；快速排序是 O(NlogN)。
【一周一算法】小哼買(mǎi)書(shū)
http://bbs.ahalei.com/thread-4443-1-1.html
(出處: 啊哈磊_編程從這里起步)
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多