現在來看一個具體的例子“小哼買書”(根據全國青少年信息學奧林匹克聯賽 NOIP2006 普及組第一題改編),來實踐一下 章所學的三種排序算法。

Paste_Image.png

小哼的學校要建立一個圖書角,老師派小哼去找一些同學做調查,看看同學們都喜歡讀哪些書。小哼讓每個同學寫出一個自己最想讀的書的 ISBN 號(你知道嗎?每 書都有唯一的 ISBN 號,不信的話你去找 書翻到背面看看)。當然有一些好書會有很多同學都喜歡,這樣就會收集到很多重復的ISBN號。小哼需要去掉其中重復的ISBN號,即每個ISBN號只保留一個,也就說同樣的書只買一 (學校真是夠摳門的)。然后再把這些 ISBN 號從小到大排序,小哼將按照排序好的 ISBN 號去書店買書。請你協助小哼完成“去重”與“排序”的工作。

輸入有 2 行,第 1 行為一個正整數,表示有 n 個同學參與調查(n≤100)。第 2 行有 n個用空格隔開的正整數,為每 圖書的 ISBN 號(假設圖書的 ISBN 號在 1~1000 之間)。

輸出也是 2 行,第 1 行為一個正整數 k,表示需要買多少 書。第 2 行為 k 個用空格隔開的正整數,為從小到大已排好序的需要購買的圖書的 ISBN 號。

例如輸入:

10

20 40 32 67 40 20 89 300 400 15

則輸出:

8

15 20 32 40 67 89 300 400

最后,程序運行的時間限制為 1 秒。

解決這個問題的方法大致有兩種。第一種方法:先將這 n 個圖書的 ISBN 號去重,再進行從小到大排序并輸出;第二種方法:先從小到大排序,輸出的時候再去重。這兩種方法都可以。

先來看第一種方法。通過第一節的學習我們發現,桶排序稍加改動正好可以起到去重的效果,因此我們可以使用桶排序的方法來解決此問題。

#include

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++) //循環讀入n個圖書的ISBN號

{

scanf("%d",&t); //把每一個ISBN號讀到變量t中

a[t]=1; //標記出現過的ISBN號

}

for(i=1;i<=1000;i++) //依次判斷1~1000這個1000個桶

{

if(a[i]==1)//如果這個ISBN號出現過則打印出來

printf("%d ",i);

}

getchar();getchar();

return 0;

}

這種方法的時間復雜度就是桶排序的時間復雜度,為 O(N+M)。

第二種方法我們需要先排序再去重。排序我們可以用冒泡排序或者快速排序。

20 40 32 67 40 20 89 300 400 15

將這 10 個數從小到大排序之后為

15 20 20 32 40 40 67 89 300 400。

接下來,要在輸出的時候去掉重復的。因為我們已經排好序,所以相同的數都會緊挨在一起。只要在輸出的時候,預先判斷一下當前這個數 a[i]與前面一個數 a[i 1]是否相同。如果相同則表示這個數之前已經輸出過了,不用再次輸出;不同則表示這個數是第一次出現,需要輸出這個數。

#include

int main(){

int a[101],n,i,j,t;

scanf("%d",&n); //讀入n

for(i=1;i<=n;i++) //循環讀入n個圖書ISBN號

{

scanf("%d",&a[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個數

for(i=2;i<=n;i++) //從2循環到n

{

if( a[i] != a[i-1] ) //如果當前這個數是第一次出現則輸出

printf("%d ",a[i]);

}

getchar();getchar();

return 0;

}

這種方法的時間復雜度由兩部分組成,一部分是冒泡排序的時間復雜度,是 N (N2),另一部分是讀入和輸出,都是 O(N),因此整個算法的時間復雜度是 O(2N+N 2)。相對于 N2 來說,2N 可以忽略(我們通常忽略低階),最終該方法的時間復雜度是 O(N2)。

接下來我們還需要看下數據范圍。每個圖書 ISBN 號都是 1~1000 之間的整數,并且參加調查的同學人數不超過 100,即 n≤100。之前已經說過,在粗略計算時間復雜度的時候,我們通常認為計算機每秒鐘大約運行 10 億次(當然實際情況要更快)。因此以上兩種方法都可以在 1 秒鐘內計算出解。如果題目中圖書的 ISBN 號范圍不是在 1~1000 之間,而是 2147483648~2147483647 之間的話,那么第一種方法就不可行了,因為你無法申請出這么大的數組來標記每一個 ISBN 號是否出現過。另外如果 n 的范圍不是小于等于 100,而是小于等于 10 萬,那么第二種方法的排序部分也不能使用冒泡排序。因為題目要求的時間限制是 1 秒,使用冒泡排序對 10 萬個數進行排序,計算機要運行 100 億次,需要 10 秒鐘,因此要替換為快速排序,快速排序只需要 100000×log2100000≈100000×17≈170 萬次,這還不到0.0017 秒。是不是很神奇?同樣的問題使用不同的算法竟然有如此之大的時間差距,這就是算法的魅力!

我們來回顧一下 章三種排序算法的時間復雜度。桶排序是最快的,它的時間復雜度是O(N+M);冒泡排序是 O(N 2);快速排序是 O(NlogN)。