C語言編程常見問題解答  
 

 
發表日期：2003年9月22日    作者：C語言之家整理  已經有3830位讀者讀過此文 
 


                                    第3章  排序與查找

    在計算機科學中，排序(sorting)是研究得最多的問題之一，許多書籍都深入討論了這個問題。本章僅僅是一個介紹，重點放在C語言的實際應用上。

    排 序

    程序員可以使用的基本排序算法有5種：
    ·插入排序(insertionsort．)
    ·交換排序(exchangesOrt)
    ·選擇排序(selectionsort)    
    ·歸并排序(mergesort)
    ·分布排序(distributionsort)

    為了形象地解釋每種排序算法是怎樣工作的，讓我們來看一看怎樣用這些方法對桌上一付亂序的牌進行排序。牌既要按花色排序(依次為梅花、方塊、紅桃和黑心)，還要按點數排序(從2到A)。
    插入排序的過程為：從一堆牌的上面開始拿牌，每次拿一張牌，按排序原則把牌放到手中正確的位置。桌上的牌拿完后，手中的牌也就排好序了。
    交換排序的過程為：
    (1)先拿兩張牌放到手中。如果左邊的牌要排在右邊的牌的后面，就交換這兩張牌的位置。
    (2)然后拿下一張牌，并比較最右邊兩張牌，如果有必要就交換這兩張牌的位置。
    (3)重復第(2)步，直到把所有的牌都拿到手中。
    (4)如果不再需要交換手中任何兩張牌的位置，就說明牌已經排好序了；否則，把手中的牌放到桌上，重復(1)至(4)步，直到手中的牌排好序。
    選擇排序的過程為：在桌上的牌中找出最小的一張牌，拿在手中；重復這種操作，直到把所有牌都拿在手中。
    歸并排序的過程為：把桌上的牌分為52堆，每堆為一張牌。因為每堆牌都是有序的(記住，此時每堆中只有一張牌)，所以如果把相鄰的兩堆牌合并為一堆，并對每堆牌進行排序，就可以得到26堆已排好序的牌，此時每一堆中有兩張牌。重復這種合并操作，就可以依次得到13堆牌(每一堆中有4張牌)，7堆牌(有6堆是8張牌，還有一堆是4張牌)，最后將得到52張的一堆牌。
    分布排序(也被稱作radix sort，即基數排序)的過程為：先將牌按點數分成13堆，然后將這13堆牌按點數順序疊在一起；再將牌按花色分成4堆，然后將這4堆牌按花色順序疊在一起，牌就排好序了。
    在選用排序算法時，你還需要了解以下幾個術語：
    (1)自然的(natural)
    如果某種排序算法對有序的數據排序速度較快(工作量變小)，對無序的數據排序速度卻較慢(工作變量大)，我們就稱這種排序算法是自然的。如果數據已接近有序，就需要考慮選用自然的排序算法。
    (2)穩定的(stable)
    如果某種排序算法能保持它認為相等的數據的前后順序，我們就稱這種排序算法是穩定的。    
    例如，現有以下名單：
    Mary Jones
    Mary Smith
    Tom Jones
    Susie Queue
    如果用穩定的排序算法按姓對上述名單進行排序，那么在排好序后"Mary Jones”和"Tom Jones”將保持原來的Jr順序，因為它們的姓是相同的。
    穩定的排序算法可按主、次關鍵字對數據進行排序，例如按姓和名排序(換句話說，主要按姓排序，但對姓相同的數據還要按名排序)。在具體實現時，就是先按次關鍵字排序，再按主關鍵字排序。
    (3)內部排序(internal sort)和外部排序(external sort)
    待排數據全部在內存中的排序方法被稱為內部排序，待排數據在磁盤、磁帶和其它外存中的排序方法被稱為外部排序。

    查 找

    和排序算法一樣，查找(searching)算法也是計算機科學中研究得最多的問題之一。查找算法和排序算法是有聯系的，因為許多查找算法依賴于要查找的數據集的有序程度。基本的查找算法有以下4種：
    ·順序查找(sequential searching)。
    ·比較查找(comparison searching)
    ·基數查找(radix searching)
    ·哈希查找(hashing)    
    下面仍然以一付亂序的牌為例來描述這些算法的工作過程。
    順序查找的過程為：從第一張開始查看每一張牌，直到找到要找的牌。
    比較查找(也被稱作binarysearching，即折半查找)要求牌已經排好序，其過程為：任意抽一張牌，如果這張牌正是要找的牌，則查找過程結束。如果抽出的這張牌比要找的牌大，則在它前面的牌中重復查找操作；反之，則在它后面的牌中重復查找操作，直到找到要找的牌。
    基數查找的過程為：先將牌按點數分成13堆，或者按花色分成4堆。然后找出與要找的牌的點數或花色相同的那一堆牌，再在這堆牌中用任意一種查找算法找到要找的牌。
    哈希查找的過程為：
    (1)在桌面上留出可以放若干堆牌的空間，并構造一個函數，使其能根據點數和花色將牌映射到特定的堆中(這個函數被稱為hashfunction，即哈希函數)。
    (2)根據哈希函數將牌分成若干堆。    
    (3)根據哈希函數找到要找的牌所在的堆，然后在這一堆牌中找到要找的牌。    
    例如，可以構造這樣一個哈希函數：    
  pile=rank+suit
    其中，rank是表示牌的點數的一個數值；suit是表示牌的花色的一個數值；pile表示堆值，它將決定一張牌歸入到哪一堆中。如果用1，2，……，13分別表示A，2，……．K，用0，1，2和3分別表示梅花、方塊、紅桃和黑桃，則pile的值將為1，2，……，16，這樣就可以把一付牌分成16堆。
    哈希查找雖然看上去有些離譜，但它確實是一種非常實用的查找算法。各種各樣的程序，從壓縮程序(如Stacker)到磁盤高速緩存程序(如SmartDrive)，幾乎都通過這種方法來提高查找速度，
    
  排序或查找的性能
    
  有關排序和查找的一個主要問題就是速度。這個問題經常被人們忽視，因為與程序的其余部分相比，排序或查找所花費的時間幾乎可以被忽略。然而，對大多數排序或查找應用來說，你不必一開始就花很多精力去編制一段算法程序，而應該先在現成的算法中選用一種最簡單的(見3．1和3．4)，當你發現所用的算法使程序運行很慢時，再換用一種更好的算法(請參見下文中的介紹)。
    下面介紹一種判斷排序或查找算法的速度的方法。
    首先，引入一個算法的復雜度的概念，它指的是在各種情況(最好的、最差的和平均的)下排序或查找需要完成的操作次數，通過它可以比較不同算法的性能。
    算法的復雜度與排序或查找所針對的數據集的數據量有關，因此，引入一個基于數據集數據量的表達式來表示算法的復雜度。
    最快的算法的復雜度O(1)，它表示算法的操作次數與數據量無關。復雜度O(N)(N表示數據集的數據量)表示算法的操作次數與數據量直接相關。復雜度O(logN)介于上述兩者之間，它表示算法的操作次數與數據量的對數有關。復雜度為O(NlogN)(N乘以logN)的算法比復雜度為O(N)的算法要慢，而復雜度為O(N2)的算法更慢。 
    注意：如果兩種算法的復雜度都是O(logN)，那么logN的基數較大的算法的速度要快些，在本章的例子中，logN的基數均為10。

        表3．1  本章所有算法的復雜度
-----------------------------------------------------------------
    算    法    最好情況    平均情況    最壞情況
-----------------------------------------------------------------
  快速排序      O(NlogN)    O(NlogN)    O(N2)
  歸并排序      O(N)        O(NlogN)    O(NlogN)
  基數排序      O(N)        O(N)        O(N)    
  線性查找                  O(N)
  折半查找                  O(NlogN)
  哈希查找                  O(N/M)*
  健樹查找                  O(1)**
-----------------------------------------------------------------
* M是哈希表項的數目
** 實際上相當于有232個哈希表項的哈希查找

    表3. 1列出了本章所有算法的復雜度。對于排序算法，表中給出了最好的、平均的和最差的情況下的復雜度，平均情況是指數據隨機排列的情況；排序算法的復雜度視數據的初始排列情況而定，它一般介于最好的和最差的兩種情況之間。對于查找算法，表中只給出了平均情況下的復雜度，在最好的情況(即要找的數據恰好在第一次查找的位置)下，查找算法的復雜度顯然是O(1)；在最壞的情況(即要找的數據不在數據集中)下，查找算法的復雜度通常與平均情況下的復雜度相同。    
    需要注意的是，算法的復雜度只表示當N值變大時算法的速度變慢的程度，它并不表示算法應用于給定大小的數據集時的實際速度。算法的實際速度與多種因素有關，包括數據集的數據類型以及所用的編程語言、編譯程序和計算機等。換句話說，與復雜度高的算法相比，復雜度低的算法并不具備絕對的優越性。實際上，算法的復雜度的真正意義在于，當N值大于某一數值后，復雜度低的算法就會明顯比復雜度高的算法快。
    為了說明算法的復雜度和算法的實際執行時間之間的關系，表3．2列出了本章所有例子程序的執行時間。本章所有例子程序均在一臺以Linux為操作系統的90MHz奔騰計算機上由GNU C編譯程序編譯，在其它操作系統中，這些例子程序的執行時間與表3．2所列的時間是成比例的。

                 表3. 2  本章所有例子程序的執行時間
---------------------------------------------------------------------------
    例子程序    算  法      2000      4000      6000      8000      10000
---------------------------------------------------------------------------
    例3．1     qsort()      0．02     0．05     0．07     0．11     0，13
    例3．2a    快速排序     0．02     0．07     0．13     0．18     0．20
    例3．2b    歸并排序     0．03     0．08     0．14     0．18     0．26
    例3．2c    基數排序     0．07     0．15     0．23     0．30     0．39
    例3．4     bsearch()    0. 37     0．39     0．39     0．40     0．41
    例3．5     折半查找     0．32     0．34     0．34     0．36     0．36
    例3．6     線性查找     9．67     20．68    28．71    36．31    45. 51
    例3．7     鍵樹查找     0．27     0．28     0．29     0．29     0．30
    例3．8     哈希查找     0．25     0．26     0．28     0．29     0．28
---------------------------------------------------------------------------

 注意：(1)表中所列的時間以秒為單位。(2)表中所列的時間經過統一處理，只包括排序或查找所花費的時間。(3)2000等數值表示數據集的數據量。(4)數據集中的數據是從文件／usr／man／manl／gcc．1(GNUC編譯程序中的一個文件)中隨機提取的詞。(5)在查找算法中，要查找的數據是從文件／usr／man／manl／g++．1(GNUC++編譯程序中的一個文件)中隨機提取的詞。(6)函數qsort()和bseareh()分別是C標準庫函數中用于快速排序算法和折半查找算法的函數，其余例子程序是專門為本章編寫的。
    在閱讀完以上內容后，你應該能初步體會到如何根據不同的情況來選用一種合適的排序或查找算法。在Donald E．Knuth所著的《The Art Of Computer Programming，Volume 3，Sorting and Searching》一書中，作者對排序和查找算法進行了全面的介紹，在該書中你將讀到更多關于復雜度和復雜度理論的內容，并且能見到比本章中所提到的更多的算法。

    公用代碼
    本章中的許多例子程序是可以直接編譯運行的。在這些例子程序中，許多代碼是相同的， 這些相同的代碼將統一在本章的末尾列出。

    3．1  哪一種排序方法最方便?
    答案是C標準庫函數qsort()，理由有以下三點：
    (1)該函數是現成的；    
    (2)該函數是已通過調試的；
    (3)該函數通常是已充分優化過的。
    qsort()函數通常使用快速排序算法，該算法是由C. A．R．Hoare于1962年提出的。以下是qsort()函數的原型：
    void qsort(void *buf，size_t hum，size_t size，
    int(*comp)(const void *ele1，const void *ele2));

    qsort()函數通過一個指針指向一個數組(buf)，該數組的元素為用戶定義的數據，數組的元素個數為num，每個元素的字節長度都為size。數組元素的排序是通過調用指針comp所指向的一個函數來實現的，該函數對數組中由ele1和ele2所指向的兩個元素進行比較，并根據前者是小于、等于或大于后者而返回一個小于、等于或大于0的值。   
    例3．1中給出了一個函數sortStrings()，該函數就是通過qsort()函數對一個以NULL指針結束的字符串數組進行排序的。將例3．1所示的代碼和本章結尾的有關代碼一起編譯成一個可執行程序后，就能按字母順序對一個以NULL指針結束的字符串數組進行排序了。

1:#include<stdlib. h>
 2:
 3: /*
 4:  * This routine is used only by sortStrings(), to provide a
 5:  * string comparison {unction to pass to qsort().
 6:  */
 7: static int comp(const void * elel, const void * ele2)
 8: {
 9:    return strcmp( * (const char * * ) ele1,
10:                * (const char * * ) ele2);
11: }
12:
13: / * Sort strings using the library function qsort() * /
14: void sortStrings(const char * array[-'])
15: {
16,       /* First, determine the length of the array * /
17:       int num;
18:
19:      for (num=O; array[num]; num++)
20:
21:      qsort(array, num, sizeof( * array), comp) ;