再來看一個具體的例子《小哼買書》來看看三個排序在應用上的區(qū)別和局限性。小哼的學校要建立一個圖書角，老師派小哼去找一些同學做調(diào)查，看看同學們都喜歡讀哪些書。小哼讓每個同學寫出一個自己最想讀的書的 ISBN 號（你知道嗎？每本書都有唯一的 ISBN 號，不信話你去找本書翻到背面看看）。當然有一些好書會有很多同學都喜歡，這樣就會收集到很多重復的 ISBN 號。小哼需要去掉其中重復的 ISBN 號，即每個 ISBN 號只保留一個，也就說同樣的書只買一本（學校真是夠摳門的）。然后再把這些 ISBN 號從小到大排序，小哼將按照排序好的 ISBN 號去書店去買書。請你協(xié)助小哼完成“去重”與“排序”的工作。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/z.1.png" alt="picturez.1" />

輸入有 2 行，第 1 行為一個正整數(shù)，表示有 n 個同學參與調(diào)查（n<=100）。第 2 行有 n 個用空格隔開的正整數(shù)，為每本圖書的 ISBN 號（假設圖書的 ISBN 號在 1~1000 之間）。

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

102040326740208930040015

則輸出

8152032406789300400

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

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

先來看第一種方法。通過第一節(jié)的學習我們發(fā)現(xià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個圖書的ISBN號
        {
            scanf("%d",&t); //把每一個ISBN號讀到變量t中
            a[t]=1; //標記出現(xiàn)過的ISBN號
        }

        for(i=1;i<=1000;i++) //依次判斷1~1000這個1000個桶
        {
              if(a[i]==1)//如果這個ISBN號出現(xiàn)過則打印出來
                 printf("%d ",i);
        }

        getchar();getchar();
        return 0;
    }

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

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

20 40 32 67 40 20 89 300 400 15

將這 10 個數(shù)從小到大排序之后為 15 20 20 32 40 40 67 89 300 400。

接下來，要在輸出的時候去掉重復的。因為我們已經(jīng)排好序，因此相同的數(shù)都會緊挨在一起。只要在輸出的時候，預先判斷一下當前這個數(shù) a 與前面一個數(shù) a[i-1]是否相同。如果相同則表示這個數(shù)之前已經(jīng)輸出過了，不同再次輸出。不同則表示這個數(shù)是第一次出現(xiàn)需要，則需要輸出這個數(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個圖書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個數(shù)
        for(i=2;i<=n;i++) //從2循環(huán)到n
        {
             if( a[i] != a[i-1] ) //如果當前這個數(shù)是第一次出現(xiàn)則輸出
                 printf("%d ",a[i]);
        }

        getchar();getchar();
        return 0;
    }

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

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

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

【一周一算法】小哼買書
 http://bbs.ahalei.com/thread-4443-1-1.html
(出處: 啊哈磊_編程從這里起步)

上一篇：算法 10：二叉樹下一篇：算法 8：巧妙的鄰接表（數(shù)組實現(xiàn)）