C語言五種基本排序算法

程序員可以使用的基本排序算法有5種：

1. 插入排序(insertionsort．)
2. 交換排序(exchangesOrt)
3. 選擇排序(selectionsort)
4. 歸并排序(mergesort)
5. 分布排序(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)
待排數據全部在內存中的排序方法被稱為內部排序，待排數據在磁盤、磁帶和其它外存中的排序方法被稱為外部排序。

4種基本的C語言查找算法

和排序算法一樣，查找(searching)算法也是計算機科學中研究得最多的問題之一。查找算法和排序算法是有聯系的，因為許多查找算法依賴于要查找的數據集的有序程度。

基本的查找算法有以下4種：

1. 順序查找(sequential searching)
2. 比較查找(comparison searching)
3. 基數查找(radix searching)
4. 哈希查找(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)，幾乎都通過這種方法來提高查找速度，

C語言排序或查找的性能分析

有關排序和查找的一個主要問題就是速度。這個問題經常被人們忽視，因為與程序的其余部分相比，排序或查找所花費的時間幾乎可以被忽略。然而，對大多數排序或查找應用來說，你不必一開始就花很多精力去編制一段算法程序，而應該先在現成的算法中選用一種最簡單的(見3．1和3．4)，當你發現所用的算法使程序運行很慢時，再換用一種更好的算法(請參見下文中的介紹)。

下面介紹一種判斷排序或查找算法的速度的方法。
首先，引入一個算法的復雜度的概念，它指的是在各種情況(最好的、最差的和平均的)下排序或查找需要完成的操作次數，通過它可以比較不同算法的性能。

算法的復雜度與排序或查找所針對的數據集的數據量有關，因此，引入一個基于數據集數據量的表達式來表示算法的復雜度。

最快的算法的復雜度O(1)，它表示算法的操作次數與數據量無關。復雜度O(N)(N表示數據集的數據量)表示算法的操作次數與數據量直接相關。復雜度O(logN)介于上述兩者之間，它表示算法的操作次數與數據量的對數有關。復雜度為O(NlogN)(N乘以logN)的算法比復雜度為O(N)的算法要慢，而復雜度為O(N ²)的算法更慢。

注意：如果兩種算法的復雜度都是O(logN)，那么logN的基數較大的算法的速度要快些，在本章的例子中，logN的基數均為10。

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

表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》一書中，作者對排序和查找算法進行了全面的介紹，在該書中你將讀到更多關于復雜度和復雜度理論的內容，并且能見到比本章中所提到的更多的算法。

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

C語言排序方法中哪一種最方便?

答案是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) ;
22: }

在例3．1中，第19行和第20行的for循環語句用來計算傳遞給qsort()函數的數組元素個數，函數comp()的作用是將函數qsort()傳遞給它的類型(const void *)轉換為函數strcmp()
所要求的類型(const char *)。因為在函數qsort()中，ele1和ele2是指向數組元素的指針，而在例3．1中這些數組元素本身也是指針，因此，應該先將ele1和ele2轉換為const char **類型，然后在轉換結果前加上指針運算符“*”，才能得到函數strcmp()所要求的類型。

盡管有qsort()函數，但程序員經常還要自己編寫排序算法程序，其原因有這樣幾點：
第一，在有些異常情況下，qsort()函數的運行速度很慢，而其它算法程序可能會快得多；
第二，qsort()函數是為通用的目的編寫的，這給它帶來了一些不利之處，例如每次比較時都要通過用戶提供的一個函數指針間接調用一個函數；
第三，由于數組元素的長度在程序運行時才能確定下來，因此用來在數組中移動數組元素的那部分代碼沒有針對數組元素長度相同的情況進行優化；
第四，qsort()函數要求所有數據都在同一個數組中，而在實際應用中，數據的長度和性質千變萬化，可能很難甚至無法滿足這一要求；
第五，qsort()函數通常不是一種穩定的排序方法。

C語言排序方法中，哪一種最快?

首先，對大多數包含排序應用的程序來說，排序算法的速度并不重要，因為在程序中排序? 的工作量并不是很多，或者，與排序相比，程序中其它操作所花費的時間要多得多。

實際上，沒有哪一種排序算法永遠是最快的，在運行程序的軟硬件環境相同的情況下，不同排序算法的速度還與數據的長度、性質以及數據的初始順序有關。

在筆者的“工具箱”中，有三種算法在不同的情況下都是最快、最有用的，這三種算法分別是快速排序、歸并排序和基數排序。

快速排序
快速排序是一種分割處理式的排序算法，它將一個復雜的排序問題分解為若干較容易處理的排序問題，然后逐一解決。在快速排序算法中，首先要從數據集的數據中選擇一個數據作為分割值，然后將數據分成以下3個子集：
??? (1) 將大于分割值的數據移到分割值前面，組成子集1；
??? (2) 分割值本身為子集2；???
??? (3) 將小于分割值的數據移到分割值后面，組成子集3。
等于分割值的數據可以放在任意一個子集中，這對快速排序算法沒有任何影響。由于子集2已經是有序的，所以此后只需對子集1和子集3進行快速排序。

需要注意的是，當數據集很小時，無法進行快速排序，而要使用其它排序算法。顯然，當數據集中的數據只有兩個或更少時，就不可能將數據集再分割成三個子集。實際上，當數據集比較小時，程序員就應該考慮是否仍然采用快速排序算法，因為在這種情況下另外一些排序算法往往更快。

例3. 2a用快速排序算法重寫了例3．1中的字符串數組排序程序，你同樣可以將它和本章末尾的有關代碼一起編譯成一個可執行程序。程序中定義了一個宏，它可使程序更易讀，并能加快執行速度。

快速排序算法是由程序中的myQsort()函數實現的，它是按升序對一個字符串數組進行排序的。函數myQsort()的具體工作過程如下：
??? (1)首先檢查最簡單的情況。在第17行，檢查數組中是否沒有或只有一個元素——在這種情況下，數組已經是有序的，函數就可以返回了。在第19行，檢查數組中是否只有兩個元素——在這種情況下，要么數組已經是按升序排列的，要么交換這兩個元素的位置，使它們按升序排列。
??? (2)在第28行至第53行，將數組分割為兩個子集：第一個子集中的數據大于或等于分割值，第二個子集中的數據小于分割值。

在第28行，選擇數組中間的元素作為分割值，并將其和數組中的第一個元素交換位置。在第37行至第39行，在數組中找到屬于第二個子集的第一個元素；在第45行至第47行，在數組中找到屬于第一個子集的最后一個元素。在第49行，檢查屬于第二個子集的第一個元素是否位于屬于第一個子集的最后一個元素的后面，如果是，則第一個子集的所有元素都已在第二個子集的所有元素的前面，數據已經劃分好了；否則，交換這兩個元素的位置，然后重復上述這種檢查。
??? (3)當兩個子集分割完畢后，在第55行，將分割值和第一個子集中的最后一個元素交換位置，排序結束時這個分割值將仍然排在現在這個位置。在第57行和第58行，分別調用myQsort()函數對分割所得的子集進行排序。當所有的子集都經過排序后，整個數組也就排好序了。

例3. 2a一個不使用qsort()函數的快速排序算法程序

?1: #include <stdlib.h>
?2:
?3: #define exchange(A, B, T)? ((T) = (A), (A) = (B),(B)=(T))
?4:???????????????????????????????????????
?5:
?6: / * Sorts an array of strings using quick sort algorithm * /
?7: static void myQsort(const char * array[], size_t num)
?8: {
?9:???? const char * temp
10:???? size_t i, j;
11:
12:?????? /*
13:?????? * Check the simple cases first:
14:?????? * If fewer than 2 elements, already sorted
15:?????? * If exactly 2 elements, just swap them (if needed).
16:????????? * /
17:?????? if (num <2)
18:??????????????? return;
19:?????? else if (num==2)
20:??????? {
21:?????????? if (strcmp(array[O], array[1])>O)
22:???????????????? exchange (array[0], array[1] ,temp)
23:??????? }
24:??????? / *
25:??????? * Partition the array using the middle (num/2)
26:??????? element as the dividing element.
27:????????? * /
28:?????? exchange (array[0], array[num / 2], temp)
29:?????? i=1;
30:?????? j=num;
31:?????? for (; ;)
32:???????? {
33:???????????? / *
34:?????????????? * Sweep forward until and element is found that
35:?????????????? * belongs in the second partition.
36:?????????????? * /
37:????????????? while (i<j && strcmp (array[i], array[0])
38:?????????????????????????????????????????????????? <=0)
39:??????????????????? i++;
40:????????????? / *
41:??????????????? * Then sweep backward until an element
42:??????????????? * is found that belongs in the first
43:??????????????? * partition.
44:??????????????? * /
45:???????????? while (i<j&& strcmp(array[j-1], array[O]
46:?????????????????????????????????????????????? >=0)
47:????????????????? j--;
48:????????????? / * If no out-of-place elements, you're done * /
49:??????????? if (i>=j)
50:????????????????? break
51:?????????????? / * Else, swap the two out-of-place elements * /
52:????????????? exchange(array[i], array[j-l], temp)
53:??????? }
54:?????? / * Restore dividing element * /
55:?????? exchange(array[O], array[i-1], temp)
56:?????? / * Now apply quick sort to each partition * /
57:?????? myQsort (array, i-1 )
58:?????? myQsort (array + i, num-i)
59:? }
60:
61: / * Sort strings using your own implementation of quick sort * /
62: void sortStrings (char * array[])
63: {
64:?????? / * First, determine the length of the array * /
65:?????? int num
66:
67:?????? for (num = O; array[num] ; num++ )
68:
69:?????? myQsort((void * ) array, num)
70: }

C語言歸并算法詳解

歸并排序也是一種分割處理式的排序算法，它是由Johnyon Neumann于1945年提出的。

在歸并排序算法中，將待排序數據看作是一個鏈表序列，每個鏈表(最壞的情況下每個鏈表中只有一個元素)中的數據都已經排好序，然后不斷地將相鄰的鏈表合并為一些較大的鏈表，當所有的鏈表都合并為一個鏈表時，排序過程也就結束了。歸并排序算法特別適合于對鍵表或其它非數組形式的數據結構進行排序，它還能對無法放入內存的數據進行排序；或者被作為一種特定的排序算法來使用。

例3．2b是實現歸并排序算法的一個例子，你可以將它和本章結尾的有關代碼一起編譯成一個可執行程序。有關list_t類型及其操作函數的代碼也已在本章末尾列出。?

在例3．2b中，字符串被存放在一個鏈表中，而不是一個數組中。實際上，將數據組織為鏈表后更利于歸并排序算法對其進行處理，因為數組中的元素是無法合并的，除非利用另外分配的內存空間。

例3．2b通過以下4個函數共同實現歸并排序算法：???
(1)split()函數
??? split()函數將一個字符串鏈表分割為一個由多個字符串鏈表組成的鏈表，其中每一個字符串鏈表都已經是排好序的。例如，如果初始鏈表為("the" "quick""brown" "fox")，則split()函數將返回一個由3個鏈表組成的鏈表，這3個鏈表分別為(“the”)，("quick”)和("brown”“fox”)。因為字符串“brown”和“fox”已經是排好序的，所以它們被放到一個鏈表中。

??? 盡管split()函數將初始鏈表分割為一系列只含一個數據的鏈表后，本例的排序算法仍然能很好地執行，但是，如果初始鏈表中的數據已經接近有序，那么在分割初始鏈表時，將相鄰的有序數據放到同一個鏈表中，就能大大減少以后的工作量，從而使本例的排序算法成為自然的排序算法(見本章開始部分中的介紹)。

??? 當輸入鏈表不為空時，程序第14—24行的循環將一直進行下去。在每次循環中，程序第16行將構造一個新的鏈表；第17—22行將把輸入鏈表中的元素不斷地移到所構造的鏈表之中，直到處理完輸入鏈表中的所有元素，或者檢查到兩個無序的元素；第23行將把所構造的鏈表添加到輸出鏈表(它的數據也是鏈表)中。

(2)merge()函數
??? merge()函數將兩個數據已經有序的鏈表合并為一個數據有序的鏈表。
??? 當正在合并的兩個鏈表都不為空時，程序第37—45行的循環將一直進行下去。第40行的if 語句將比較兩個鏈表中的第一個元素，并把較小的元素移到輸出鏈表中。當正在合并的兩個鏈表中有一個為空時，另一個鏈表中的元素必須全部添加到輸出鏈表中。第46行和第47行將已為空的鏈表和另一個鏈表與輸出鏈表鏈接上，從而結束整個合并過程。

(3)mergePairs()函數
??? 通過調用merge()函數，mergePairs()函數分別對一個由字符串鏈表組成的鏈表中的每個對鏈表進行合并，并用合并所得的鏈表代替原來的那對鏈表。

??? 當輸入鏈表不為空時，程序第61—77行的循環將一直進行下去。第63行的if語句檢查輸入鏈表中是否至少有兩個字符串鏈表，如果沒有，第76行就把這個單獨的鏈表添加到輸出鏈表中；如果有，第65行和第66行將從輸入鏈表中選出頭兩個鏈表，第68行和69行將合并這兩個鏈表，第72行將把合并所得的鏈表添加到輸出鏈表中，第70行、第71行和第73行將釋放所分配的過渡性結點，第72行和第73行將從輸入鏈表中刪去頭兩個鏈表。

(4)sortStrings()函數
??? sonStrings()函數對一個字符串數組進行歸并排序。
??? 程序第88行和第89行將字符串數組轉換為一個字符串鏈表。第90行調用split()函數將初始鏈表分割為一個由字符串鏈表組成的鏈表。第91行和第92行調用mereePairs()函數將分割所得的鏈表中的所有字符串鏈表合并為一個字符串鏈表。第93行檢查合并所得的鏈表是否為空(當原來的字符串數組中只有。個元素時該鏈表為空)，若不為空，才能將該鏈表從分割所得的鏈表中移出。

需要注意的是，sortStrings()函數沒有釋放它所用過的內存。???

例3．2b一個歸并排序算法程序
?1. #include<stdlib.h>
?2: #include "list.h"
?3:
?4: /*
?5:? * Splits a list of strings into a list of lists of strings
?6:? * in which each list of strings is sorted.
?7:? */
?8: static list-t split(list_t in)
?9: {
10:????? list-t out
11:????? list-t * curr;
12:????? out. head=out, tail=NULL;
13:
14:????? while (in. head)
15:????? {
16:?????????? curr =newList();
17:?????????? do
18:?????????? {
19:??????????????? appendNode (curr, removeHead (&in));
20:?????????? }
21:???????? while (in. head && strcmp (curr->tail->u. str,
22:???????????????????????????? in. head->u.str) < = 0);
23:???????? appendNode(&out, newNode(curr));
24:???? }
25:???? return Out;
26: }
27:
28: /*
29:? * Merge two sorted lists into a third sorted list,
30:? *.which is then returned.
31:? * /
32: static list_t merge (list_t first, list_t second)
33: {
34:???????? list_t out;
35:???????? out.head=out, tail=NULL;
36:
37:???????? while (first. head && second, head)
38:?????????? {
39:???????????????? listnode_t * temp;
40:???????????????? if (strcmp (first. head->u.str,
41:??????????????????????? second. head->u.str) <=0)
42:????????????????????? appendNode(&out, removeHead(&first));
43:????????????????? else
44:?????????????????????? appendNode (&out, removeHead (&second));
45:?????????? }
46:???????? concatList (&out, &first);
47:???????? concatList (&out, &second);
48:???????? return out;
49: }
50:
51: /*
52:? * Takes a list of lists 0{ strings and merges'each pair of
53:? * lists into a single list. The resulting list has 1/2 as
54:? * many lists as the original.
55:? * /
56: static list_t mergePairs(list_t in)
57: {
58:????? list_ t out;
59:????? out. head:out, tail=NUll;
60:
61:????? while (in. head)
62:????? {
63:?????????? if (in. head->next)
64:?????????? {
65:????????????????? list_t * first =in. head->u.list;
66:????????????????? list_t * second;
67:????????????????????????????? in.head->next->u.list
68:????????????????? in. head->u.list = copyOf (merge ( * first,
69:?????????????????????????????????????????????????????????? * second));
70:????????????????? free (first);
71:????????????????? free (second);
72:????????????????? appendNode (&out, removeHead (&in))
73:????????????????? free (removeHead (&in));
74:???????????? }
75:???????????? else
76:???????????????? appendNode (&out, removeHead (&in));
77:????? }
78:????? return out
79: }
80:
81: / * Sort strings using merge sort * /
82: void sortStrings (const char * array[])
83: {
84:???????? int i;
85:???????? list_t out;
86:???????? out.head=out, tail=NULL;
87:
88:????????? for (i=0; array[i]; i++)
89:???????????? appendNode(&out, newNode((void * ) array[i]))
90:????????? out= split (out);
91:???????? while (out.head ! =out.tail)
92:???????????? out = mergePairs (out);
93:???????? if (out.head)
94:????????????????? out = * out.head->u.list;
95:??????? for (i=O; array[i]; i++)
96:??????????????? array[i] = removeHead (&out)->u.str;
97: }