10.1基本概念
排序(Sorting)是計算機程序設(shè)計中的一種重要操作，其功能是對一個數(shù)據(jù)元素集合或序列重新排列成一個按數(shù)據(jù)元素某個項值有序的序列。作為排序依據(jù)的數(shù)據(jù)項稱為“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵碼。為了便于查找，通常希望計算機中的數(shù)據(jù)表是按關(guān)鍵碼有序的。如有序表的折半查找，查找效率較高。還有，二叉排序樹、B-樹和B+樹的構(gòu)造過程就是一個排序過程。若關(guān)鍵碼是主關(guān)鍵碼，則對于任意待排序序列，經(jīng)排序后得到的結(jié)果是唯一的；若關(guān)鍵碼是次關(guān)鍵碼，排序結(jié)果可能不唯一，這是因為具有相同關(guān)鍵碼的數(shù)據(jù)元素，這些元素在排序結(jié)果中，它們之間的的位置關(guān)系與排序前不能保持。
若對任意的數(shù)據(jù)元素序列，使用某個排序方法，對它按關(guān)鍵碼進行排序：若相同關(guān)鍵碼元素間的位置關(guān)系，排序前與排序后保持一致，稱此排序方法是穩(wěn)定的；而不能保持一致的排序方法則稱為不穩(wěn)定的。

排序分為兩類：內(nèi)排序和外排序。
內(nèi)排序：指待排序列完全存放在內(nèi)存中所進行的排序過程，適合不太大的元素序列。
外排序：指排序過程中還需訪問外存儲器，足夠大的元素序列，因不能完全放入內(nèi)存，只能使用外排序。

10.2插入排序
10.2.1直接插入排序
設(shè)有n個記錄，存放在數(shù)組r中，重新安排記錄在數(shù)組中的存放順序，使得按關(guān)鍵碼有序。即
r[1].key≤r[2].key≤……≤r[n].key

先來看看向有序表中插入一個記錄的方法：
設(shè)１<ｊ≤ｎ，r[1].key≤r[2].key≤……≤r[j-1].key，將r[j]插入，重新安排存放順序，使得r[1].key≤r[2].key≤……≤r[j].key，得到新的有序表，記錄數(shù)增１。

【算法10.1】
① r[0]=r[j]； //r[j]送r[0]中，使r[j]為待插入記錄空位
i=j-1； //從第i個記錄向前測試插入位置，用r[0]為輔助單元， 可免去測試i<1。
② 若r[0].key≥r[i].key，轉(zhuǎn)④。 //插入位置確定
③ 若r[0].key < r[i].key時，
r[i+1]=r[i]；i=i-1；轉(zhuǎn)②。 //調(diào)整待插入位置
④ r[i+1]=r[0]；結(jié)束。 //存放待插入記錄
【例10.1】向有序表中插入一個記錄的過程如下：
r[1] r[2] r[3] r[4] r[5] 存儲單元
2 10 18 25 9 將r[5]插入四個記錄的有序表中，j=5
r[0]=r[j]；i=j-1； 初始化，設(shè)置待插入位置
2 10 18 25 □ r[i+1]為待插入位置
i=4，r[0] < r[i]，r[i+1]=r[i]；i--； 調(diào)整待插入位置
2 10 18 □ 25
i=3，r[0] < r[i]，r[i+1]=r[i]；i--； 調(diào)整待插入位置
2 10 □ 18 25
i=2，r[0] < r[i]，r[i+1]=r[i]；i--； 調(diào)整待插入位置
2 □ 10 18 25
i=1，r[0] ≥r[i]，r[i+1]=r[0]； 插入位置確定，向空位填入插入記錄
2 9 10 18 25 向有序表中插入一個記錄的過程結(jié)束

直接插入排序方法：僅有一個記錄的表總是有序的，因此，對n個記錄的表，可從第二個記錄開始直到第n個記錄，逐個向有序表中進行插入操作，從而得到n個記錄按關(guān)鍵碼有序的表。

【算法10.2】
void InsertSort(S_TBL &p)
{ for(i=2；i<=p->length；i++)
if(p->elem[i].key < p->elem[i-1].key) /*小于時，需將elem[i]插入有序表*/
{ p->elem[0].key=p->elem[i].key； /*為統(tǒng)一算法設(shè)置監(jiān)測*/
for(j=i-1；p->elem[0].key < p->elem[j].key；j--)
p->elem[j+1].key=p->elem[j].key； /*記錄后移*/
p->elem[j+1].key=p->elem[0].key； /*插入到正確位置*/
}
}
【效率分析】
空間效率：僅用了一個輔助單元。
時間效率：向有序表中逐個插入記錄的操作，進行了n-1趟，每趟操作分為比較關(guān)鍵碼和移動記錄，而比較的次數(shù)和移動記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列。
最好情況下：即待排序列已按關(guān)鍵碼有序，每趟操作只需1次比較2次移動。
總比較次數(shù)=n-1次
總移動次數(shù)=2(n-1)次
最壞情況下：即第j趟操作，插入記錄需要同前面的j個記錄進行j次關(guān)鍵碼比較，移動記錄的次數(shù)為j+2次。
平均情況下：即第j趟操作，插入記錄大約同前面的j/2個記錄進行關(guān)鍵碼比較，移動記錄的次數(shù)為j/2+2次。
由此，直接插入排序的時間復(fù)雜度為O(n2)。是一個穩(wěn)定的排序方法。

10.2.2折半插入排序
直接插入排序的基本操作是向有序表中插入一個記錄，插入位置的確定通過對有序表中記錄按關(guān)鍵碼逐個比較得到的。平均情況下總比較次數(shù)約為n2/4。既然是在有序表中確定插入位置，可以不斷二分有序表來確定插入位置，即一次比較，通過待插入記錄與有序表居中的記錄按關(guān)鍵碼比較，將有序表一分為二，下次比較在其中一個有序子表中進行，將子表又一分為二。這樣繼續(xù)下去，直到要比較的子表中只有一個記錄時，比較一次便確定了插入位置。
二分判定有序表插入位置方法：
① low=1；high=j-1；r[0]=r[j]； // 有序表長度為j-1，第j個記錄為待插入記錄
//設(shè)置有序表區(qū)間，待插入記錄送輔助單元
② 若low>high，得到插入位置，轉(zhuǎn)⑤
③ low≤high，m=(low+high)/2； // 取表的中點，并將表一分為二，確定待插入?yún)^(qū)間*/
④ 若r[0].key<r[m].key，high=m-1； //插入位置在低半?yún)^(qū)
否則，low=m+1； // 插入位置在高半?yún)^(qū)
轉(zhuǎn)②
⑤ high+1即為待插入位置，從j-1到high+1的記錄，逐個后移，r[high+1]=r[0]；放置待插入記錄。

【算法10.3】
void InsertSort(S_TBL *s)
{ /* 對順序表s作折半插入排序 */
for(i=2；i<=s->length；i++)
{ s->elem[0]=s->elem[i]； /* 保存待插入元素 */
low=i；high=i-1； /* 設(shè)置初始區(qū)間 */
while(low<=high) /* 該循環(huán)語句完成確定插入位置 */
{ mid=(low+high)/2；
if(s->elem[0].key>s->elem[mid].key)
low=mid+1； /* 插入位置在高半?yún)^(qū)中 */
else high=mid-1； /* 插入位置在低半?yún)^(qū)中 */
}/* while */
for(j=i-1；j>=high+1；j--) /* high+1為插入位置 */
s->elem[j+1]=s->elem[j]； /* 后移元素，留出插入空位 */
s->elem[high+1]=s->elem[0]； /* 將元素插入 */
}/* for */
}/* InsertSort */
【時間效率】
確定插入位置所進行的折半查找，關(guān)鍵碼的比較次數(shù)至多為 ，次，移動記錄的次數(shù)和直接插入排序相同，故時間復(fù)雜度仍為O(n2)。是一個穩(wěn)定的排序方法。
10.2.3表插入排序
直接插入排序、折半插入排序均要大量移動記錄，時間開銷大。若要不移動記錄完成排序，需要改變存儲結(jié)構(gòu)，進行表插入排序。所謂表插入排序，就是通過鏈接指針，按關(guān)鍵碼的大小，實現(xiàn)從小到大的鏈接過程，為此需增設(shè)一個指針項。操作方法與直接插入排序類似，所不同的是直接插入排序要移動記錄，而表插入排序是修改鏈接指針。用靜態(tài)鏈表來說明。
#define SIZE 200
typedef struct{
ElemType elem； /*元素類型*/
int next； /*指針項*/
}NodeType； /*表結(jié)點類型*/
typedef struct{
NodeType r[SIZE]； /*靜態(tài)鏈表*/
int length； /*表長度*/
}L_TBL； /*靜態(tài)鏈表類型*/
假設(shè)數(shù)據(jù)元素已存儲在鏈表中，且0號單元作為頭結(jié)點，不移動記錄而只是改變鏈指針域，將記錄按關(guān)鍵碼建為一個有序鏈表。首先，設(shè)置空的循環(huán)鏈表，即頭結(jié)點指針域置0，并在頭結(jié)點數(shù)據(jù)域中存放比所有記錄關(guān)鍵碼都大的整數(shù)。接下來，逐個結(jié)點向鏈表中插入即可。
【例10.2】表插入排序示例

MAXINT 49 38 65 97 76 13 27 49
0 - - - - - - - -

MAXINT 49 38 65 97 76 13 27 49
1 0 - - - - - - -

MAXINT 49 38 65 97 76 13 27 49
2 0 1 - - - - - -

MAXINT 49 38 65 97 76 13 27 49
2 3 1 0 - - - - -

MAXINT 49 38 65 97 76 13 27 49
2 3 1 4 0 - - - -

MAXINT 49 38 65 97 76 13 27 49
2 3 1 5 0 4 - - -

MAXINT 49 38 65 97 76 13 27 49
6 3 1 5 0 4 2 - -

MAXINT 49 38 65 97 76 13 27 49
6 3 1 5 0 4 7 2 -

MAXINT 49 38 65 97 76 13 27 49
6 8 1 5 0 4 7 2 3

圖10.1
表插入排序得到一個有序的鏈表，查找則只能進行順序查找，而不能進行隨機查找，如折半查找。為此，還需要對記錄進行重排。
重排記錄方法：按鏈表順序掃描各結(jié)點，將第i個結(jié)點中的數(shù)據(jù)元素調(diào)整到數(shù)組的第i個分量數(shù)據(jù)域。因為第i個結(jié)點可能是數(shù)組的第j個分量，數(shù)據(jù)元素調(diào)整僅需將兩個數(shù)組分量中數(shù)據(jù)元素交換即可，但為了能對所有數(shù)據(jù)元素進行正常調(diào)整，指針域也需處理。
【算法10.3】
1. j=l->r[0].next；i=1； //指向第一個記錄位置，從第一個記錄開始調(diào)整
2. 若i=l->length時，調(diào)整結(jié)束；否則，
a. 若i=j，j=l->r[j].next；i++；轉(zhuǎn)(2) //數(shù)據(jù)元素應(yīng)在這分量中，不用調(diào)整，處理下一個結(jié)點
b. 若j>i，l->r[i].elem<-->l->r[j].elem； //交換數(shù)據(jù)元素
p=l->r[j].next； // 保存下一個結(jié)點地址
l->r[j].next=l->[i].next；l->[i].next=j； // 保持后續(xù)鏈表不被中斷
j=p；i++；轉(zhuǎn)(2) // 指向下一個處理的結(jié)點
c. 若j<i，while(j<i) j=l->r[j].next；//j分量中原記錄已移走，沿j的指針域找尋原記錄的位置
轉(zhuǎn)到(a)
【例10.3】對表插入排序結(jié)果進行重排示例

MAXINT 49 38 65 97 76 13 27 49
6 8 1 5 0 4 7 2 3

MAXINT 13 38 65 97 76 49 27 49
6 (6) 1 5 0 4 8 2 3

MAXINT 13 27 65 97 76 49 38 49
6 (6) (7) 5 0 4 8 1 3

MAXINT 13 27 38 97 76 49 65 49
6 (6) (7) (7) 0 4 8 5 3

MAXINT 13 27 38 49 76 97 65 49
6 (6) (7) (7) (6) 4 0 5 3

MAXINT 13 27 38 49 49 97 65 76
6 (6) (7) (7) (6) (8) 0 5 4

MAXINT 13 27 38 49 49 65 97 76
6 (6) (7) (7) (6) (8) (7) 0 4

MAXINT 13 27 38 49 49 65 76 97
6 (6) (7) (7) (6) (8) (7) (8) 0

圖10.2
【時效分析】
表插入排序的基本操作是將一個記錄插入到已排好序的有序鏈表中，設(shè)有序表長度為i，則需要比較至多i+1次，修改指針兩次。因此，總比較次數(shù)與直接插入排序相同，修改指針總次數(shù)為2n次。所以，時間復(fù)雜度仍為O(n2)

10.2.4希爾排序(Shell’s Sort)
希爾排序又稱縮小增量排序，是1959年由D.L.Shell提出來的，較前述幾種插入排序方法有較大的改進。
直接插入排序算法簡單，在n值較小時，效率比較高，在n值很大時，若序列按關(guān)鍵碼基本有序，效率依然較高，其時間效率可提高到O(n)。希爾排序即是從這兩點出發(fā)，給出插入排序的改進方法。
希爾排序方法：
1. 選擇一個步長序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按步長序列個數(shù)k，對序列進行k趟排序；
3. 每趟排序，根據(jù)對應(yīng)的步長ti，將待排序列分割成若干長度為m的子序列，分別對各子表進行直接插入排序。僅步長因子為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。

【例10.4】待排序列為 39，80，76，41，13，29，50，78，30，11，100，7，41，86。
步長因子分別取5、3、1，則排序過程如下：
p=5 39 80 76 41 13 29 50 78 30 11 100 7 41 86
└─────────┴─────────┘
└─────────┴──────────┘
└─────────┴──────────┘
└─────────┴──────────┘
└─────────┘
子序列分別為{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。

第一趟排序結(jié)果：
p=3 29 7 41 30 11 39 50 76 41 13 100 80 78 86
└─────┴─────┴─────┴──────┘
└─────┴─────┴─────┴──────┘
└─────┴─────┴──────┘
子序列分別為{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。
第二趟排序結(jié)果：
p=1 13 7 39 29 11 41 30 76 41 50 86 80 78 100
此時，序列基本“有序”，對其進行直接插入排序，得到最終結(jié)果：
7 11 13 29 30 39 41 41 50 76 78 80 86 100

圖10.3

【算法10.5】
void ShellInsert(S_TBL &p，int dk)
{ /*一趟增量為dk的插入排序，dk為步長因子*/
for(i=dk+1；i<=p->length；i++)
if(p->elem[i].key < p->elem[i-dk].key) /*小于時，需elem[i]將插入有序表*/
{ p->elem[0]=p->elem[i]； /*為統(tǒng)一算法設(shè)置監(jiān)測*/
for(j=i-dk；j>0&&p->elem[0].key < p->elem[j].key；j=j-dk)
p->elem[j+dk]=p->elem[j]； /*記錄后移*/
p->elem[j+dk]=p->elem[0]； /*插入到正確位置*/
}
}

void ShellSort(S_TBL *p，int dlta[]，int t)
{ /*按增量序列dlta[0，1…，t-1]對順序表*p作希爾排序*/
for(k=0；k<t；t++)
ShellSort(p，dlta[k])； /*一趟增量為dlta[k]的插入排序*/
}

【時效分析】
希爾排序時效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于步長因子序列的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的步長因子序列的方法。步長因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：步長因子中除1外沒有公因子，且最后一個步長因子必須為1。希爾排序方法是一個不穩(wěn)定的排序方法。

10.3 交換排序
交換排序主要是通過兩兩比較待排記錄的關(guān)鍵碼，若發(fā)生與排序要求相逆，則交換之。
10.3.1冒泡排序(Bubble Sort)
先來看看待排序列一趟冒泡的過程：設(shè)1<j≤n，r[1],r[2],···,r[j]為待排序列，
通過兩兩比較、交換，重新安排存放順序，使得r[j]是序列中關(guān)鍵碼最大的記錄。一趟冒泡方法為：
① i=1； //設(shè)置從第一個記錄開始進行兩兩比較
② 若i≥j，一趟冒泡結(jié)束。
③ 比較r[i].key與r[i+1].key，若r[i].key≤r[i+1].key，不交換，轉(zhuǎn)⑤
④ 當(dāng)r[i].key>r[i+1].key時， r[0]=r[i]；r[i]=r[i+1]；r[i+1]=r[0]；
將r[i]與r[i+1]交換
⑤ i=i+1； 調(diào)整對下兩個記錄進行兩兩比較，轉(zhuǎn)②
冒泡排序方法：對n個記錄的表，第一趟冒泡得到一個關(guān)鍵碼最大的記錄r[n]，第二趟冒泡對n-1個記錄的表，再得到一個關(guān)鍵碼最大的記錄r[n-1]，如此重復(fù)，直到n個記錄按關(guān)鍵碼有序的表。
【算法10.6】
① j=n； //從n記錄的表開始
② 若j<2，排序結(jié)束
③ i=1； //一趟冒泡，設(shè)置從第一個記錄開始進行兩兩比較，
④ 若i≥j，一趟冒泡結(jié)束，j=j-1；冒泡表的記錄數(shù)-1，轉(zhuǎn)②
⑤ 比較r[i].key與r[i+1].key，若r[i].key≤r[i+1].key，不交換，轉(zhuǎn)⑤
⑥ 當(dāng)r[i].key>r[i+1].key時， r[i]<-->r[i+1]； 將r[i]與r[i+1]交換
⑦ i=i+1； 調(diào)整對下兩個記錄進行兩兩比較，轉(zhuǎn)④
【效率分析】
空間效率：僅用了一個輔助單元。
時間效率：總共要進行n-1趟冒泡，對j個記錄的表進行一趟冒泡需要j-1次關(guān)鍵碼比較。
移動次數(shù)：
最好情況下：待排序列已有序，不需移動。
10.3.2快速排序
快速排序是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，將待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵碼大于等于支點記錄的關(guān)鍵碼，另一部分所有記錄的關(guān)鍵碼小于支點記錄的關(guān)鍵碼。我們將待排序列按關(guān)鍵碼以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關(guān)鍵碼有序。
一次劃分方法：
設(shè)1≤p<q≤n，r[p],r[p+1],...,r[q]為待排序列
① low=p；high=q； //設(shè)置兩個搜索指針，low是向后搜索指針，high是向前搜索指針
r[0]=r[low]； //取第一個記錄為支點記錄，low位置暫設(shè)為支點空位
② 若low=high，支點空位確定，即為low。
r[low]=r[0]； //填入支點記錄，一次劃分結(jié)束
否則，low<high，搜索需要交換的記錄，并交換之
③ 若low<high且r[high].key≥r[0].key //從high所指位置向前搜索，至多到low+1位置
high=high-1；轉(zhuǎn)③ //尋找r[high].key<r[0].key
r[low]=r[high]； //找到r[high].key<r[0].key，設(shè)置high為新支點位置，
//小于支點記錄關(guān)鍵碼的記錄前移。
④ 若low<high且r[low].key<r[0].key //從low所指位置向后搜索，至多到high-1位置
low=low+1；轉(zhuǎn)④ //尋找r[low].key≥r[0].key
r[high]=r[low]； //找到r[low].key≥r[0].key，設(shè)置low為新支點位置，
//大于等于支點記錄關(guān)鍵碼的記錄后移。
轉(zhuǎn)② //繼續(xù)尋找支點空位

【算法10.7】
int Partition(S_TBL *tbl,int low,int high) /*一趟快排序*/
{ /*交換順序表tbl中子表tbl->[low…h(huán)igh]的記錄，使支點記錄到位，并反回其所在位置*/
/*此時，在它之前(后)的記錄均不大(小)于它*/
tbl->r[0]=tbl->r[low]; /*以子表的第一個記錄作為支點記錄*/
pivotkey=tbl->r[low].key; /*取支點記錄關(guān)鍵碼*/
while(low<higu) /*從表的兩端交替地向中間掃描*/
{ while(low<high&&tbl->r[high].key>=pivotkey) high--;
tbl->r[low]=tbl->r[high]; /*將比支點記錄小的交換到低端*/
while(low<high&&tbl-g>r[high].key<=pivotkey) low++;
tbl->r[low]=tbl->r[high]; /*將比支點記錄大的交換到低端*/
}
tbl->r[low]=tbl->r[0]; /*支點記錄到位*/
return low; /*反回支點記錄所在位置*/
}
【例10.5】一趟快排序過程示例
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] r[10] 存儲單元
49 14 38 74 96 65 8 49 55 27 記錄中關(guān)鍵碼
low=1；high=10； 設(shè)置兩個搜索指針， r[0]=r[low]； 支點記錄送輔助單元，
□ 14 38 74 96 65 8 49 55 27
↑ ↑
low high
第一次搜索交換
從high向前搜索小于r[0].key的記錄，得到結(jié)果
27 14 38 74 96 65 8 49 55 □
↑ ↑
low high
從low向后搜索大于r[0].key的記錄，得到結(jié)果
27 14 38 □ 96 65 8 49 55 74
↑ ↑
low high
第二次搜索交換
從high向前搜索小于r[0].key的記錄，得到結(jié)果
27 14 38 8 96 65 □ 49 55 74
↑ ↑
low high
從low向后搜索大于r[0].key的記錄，得到結(jié)果
27 14 38 8 □ 65 96 49 55 74
↑ ↑
low high
第三次搜索交換
從high向前搜索小于r[0].key的記錄，得到結(jié)果
27 14 38 8 □ 65 96 49 55 74
↑↑
low high
從low向后搜索大于r[0].key的記錄，得到結(jié)果
27 14 38 8 □ 65 96 49 55 74
↑↑
low high
low=high，劃分結(jié)束，填入支點記錄
27 14 38 8 49 65 96 49 55 74

【算法10.8】
void QSort(S_TBL *tbl,int low,int high) /*遞歸形式的快排序*/
{ /*對順序表tbl中的子序列tbl->[low…h(huán)igh]作快排序*/
if(low<high)
{ pivotloc=partition(tbl,low,high); /*將表一分為二*/
QSort(tbl,low,pivotloc-1); /*對低子表遞歸排序*/
QSort(tbl,pivotloc+1,high); /*對高子表遞歸排序*/
}
}

【效率分析】
空間效率：快速排序是遞歸的，每層遞歸調(diào)用時的指針和參數(shù)均要用棧來存放，遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致。因而，存儲開銷在理想情況下為O(log2n)，即樹的高度；在最壞情況下，即二叉樹是一個單鏈，為O(n)。
時間效率：在n個記錄的待排序列中，一次劃分需要約n次關(guān)鍵碼比較，時效為O(n)，若設(shè)T(n)為對n個記錄的待排序列進行快速排序所需時間。
理想情況下：每次劃分，正好將分成兩個等長的子序列，則

T(n)≤cn+2T(n/2) c是一個常數(shù)
≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)
≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)
······
≤cnlog2n+nT(1)=O(nlog2n)

最壞情況下：即每次劃分，只得到一個子序列，時效為O(n2)。
快速排序是通常被認(rèn)為在同數(shù)量級（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取支點記錄，即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄。快速排序是一個不穩(wěn)定的排序方法。
10.4選擇排序
選擇排序主要是每一趟從待排序列中選取一個關(guān)鍵碼最小的記錄，也即第一趟從n個記錄中選取關(guān)鍵碼最小的記錄，第二趟從剩下的n-1個記錄中選取關(guān)鍵碼最小的記錄，直到整個序列的記錄選完。這樣，由選取記錄的順序，便得到按關(guān)鍵碼有序的序列。
10.4.1 簡單選擇排序
操作方法：第一趟，從n個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的n-1個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；如此，第i趟，則從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄交換，直到整個序列按關(guān)鍵碼有序。

【算法10.9】
void SelectSort(S_TBL *s)
{ for(i=1；i<s->length；i++)
{ /* 作length-1趟選取 */
for(j=i+1，t=i；j<=s->length；j++)
{ /* 在i開始的length-n+1個記錄中選關(guān)鍵碼最小的記錄 */
if(s->elem[t].key>s->elem[j].key)
t=j； /* t中存放關(guān)鍵碼最小記錄的下標(biāo) */
}
s->elem[t]<-->s->elem[i]； /* 關(guān)鍵碼最小的記錄與第i個記錄交換 */
}
}

從程序中可看出，簡單選擇排序移動記錄的次數(shù)較少，但關(guān)鍵碼的比較次數(shù)依然是

10.4.2樹形選擇排序
按照錦標(biāo)賽的思想進行，將n個參賽的選手看成完全二叉樹的葉結(jié)點，則該完全二叉樹有2n-2或2n-1個結(jié)點。首先，兩兩進行比賽(在樹中是兄弟的進行，否則輪空，直接進入下一輪)，勝出的再兄弟間再兩兩進行比較，直到產(chǎn)生第一名；接下來，將作為第一名的結(jié)點看成最差的，并從該結(jié)點開始，沿該結(jié)點到根路徑上，依次進行各分枝結(jié)點子女間的比較，勝出的就是第二名。因為和他比賽的均是剛剛輸給第一名的選手。如此，繼續(xù)進行下去，直到所有選手的名次排定。

【例10.6】16個選手的比賽(n=24)

圖10.5

圖10.6

圖10.5中，從葉結(jié)點開始的兄弟間兩兩比賽，勝者上升到父結(jié)點；勝者兄弟間再兩兩比賽，直到根結(jié)點，產(chǎn)生第一名91。比較次數(shù)為 23+22+21+20=24-1=n-1。
圖10.6中，將第一名的結(jié)點置為最差的，與其兄弟比賽，勝者上升到父結(jié)點，勝者兄弟間再比賽，直到根結(jié)點，產(chǎn)生第二名83。比較次數(shù)為4，即log2n次。其后各結(jié)點的名次均是這樣產(chǎn)生的，所以，對于n個參賽選手來說，即對1，故時間復(fù)雜度為O(nlog2n)。該方法占用空間較多，除需輸出排序結(jié)果的n個單元外，尚需n-1個輔助單元。-n+1)log2n-n個記錄進行樹形選擇排序，總的關(guān)鍵碼比較次數(shù)至多為(n

10.4.3 堆排序(Heap Sort)
設(shè)有n個元素的序列 k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。

圖10.7 兩個堆示例

若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點的值均不大于(或不小于)其子女的值，根結(jié)點的值是最小(或最大)的。
設(shè)有n個元素，將其按關(guān)鍵碼排序。首先將這n個元素按關(guān)鍵碼建成堆，將堆頂元素輸出，得到n個元素中關(guān)鍵碼最小(或最大)的元素。然后，再對剩下的n-1個元素建成堆，輸出堆頂元素，得到n個元素中關(guān)鍵碼次小(或次大)的元素。如此反復(fù)，便得到一個按關(guān)鍵碼有序的序列。稱這個過程為堆排序。
因此，實現(xiàn)堆排序需解決兩個問題：
1. 如何將n個元素的序列按關(guān)鍵碼建成堆；
2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1個元素，使其按關(guān)鍵碼成為一個新堆。
首先，討論輸出堆頂元素后，對剩余元素重新建成堆的調(diào)整過程。
調(diào)整方法：設(shè)有m個元素的堆，輸出堆頂元素后，剩下m-1個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。將根結(jié)點與左、右子女中較小(或小大)的進行交換。若與左子女交換，則左子樹堆被破壞，且僅左子樹的根結(jié)點不滿足堆的性質(zhì)；若與右子女交換，則右子樹堆被破壞，且僅右子樹的根結(jié)點不滿足堆的性質(zhì)。繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作，直到葉子結(jié)點，堆被建成。稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。
【例10.6】

圖10.8自堆頂?shù)饺~子的調(diào)整過程

再討論對n個元素初始建堆的過程。
建堆方法：對初始序列建堆的過程，就是一個反復(fù)進行篩選的過程。n個結(jié)點的完全
子樹成為堆，之后向前依次對各結(jié)點為根的子樹進行篩選，使之成為堆，直到根結(jié)點。
【例10.7】

堆排序：對n個元素的序列進行堆排序，先將其建成堆，以根結(jié)點與第n個結(jié)點交換；調(diào)整前n-1個結(jié)點成為堆，再以根結(jié)點與第n-1個結(jié)點交換；重復(fù)上述操作，直到整個序列有序。
【算法10.10】
void HeapAdjust(S_TBL *h，int s，int m)
{/*r[s…m]中的記錄關(guān)鍵碼除r[s]外均滿足堆的定義，本函數(shù)將對第s個結(jié)點為根的子樹篩選，使其成為大頂堆*/
rc=h->r[s]；
for(j=2*s；j<=m；j=j*2) /* 沿關(guān)鍵碼較大的子女結(jié)點向下篩選 */
{ if(j<m&&h->r[j].key<h->r[j+1].key)
j=j+1； /* 為關(guān)鍵碼較大的元素下標(biāo)*/
if(rc.key<h->r[j].key) break； /* rc應(yīng)插入在位置s上*/
h->r[s]=h->r[j]； s=j； /* 使s結(jié)點滿足堆定義 */
}
h->r[s]=rc； /* 插入 */
}

void HeapSort(S_TBL *h)
{ for(i=h->length/2；i>0；i--) /* 將r[1..length]建成堆 */
HeapAdjust(h，i，h->length)；
for(i=h->length；i>1；i--)
{ h->r[1]<-->h->r[i]； /* 堆頂與堆低元素交換 */
HeapAdjust(h，1，i-1)； /*將r[1..i-1]重新調(diào)整為堆*/
}
}

次，交換記錄至多k次。所以，在建好堆后，排序過程中的篩選次數(shù)不超過下式：
 + … +?2)-log2(n? + ?1)-log2(n?( 2  )?log22 < nlog2n2
而建堆時的比較次數(shù)不超過4n次，因此堆排序最壞情況下，時間復(fù)雜度也為O(nlog2n)。
10.5二路歸并排序
二路歸并排序的基本操作是將兩個有序表合并為一個有序表。
設(shè)r[u…t]由兩個有序子表r[u…v-1]和r[v…t]組成，兩個子表長度分別為v-u、t-v+1。合并方法為：
⑴ i=u；j=v；k=u； //置兩個子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)
⑵ 若i>v 或 j>t，轉(zhuǎn)⑷ //其中一個子表已合并完，比較選取結(jié)束
⑶ //選取r[i]和r[j]關(guān)鍵碼較小的存入輔助數(shù)組rf
如果r[i].key<r[j].key，rf[k]=r[i]； i++； k++； 轉(zhuǎn)⑵
否則，rf[k]=r[j]； j++； k++； 轉(zhuǎn)⑵
⑷ //將尚未處理完的子表中元素存入rf
如果i<v，將r[i…v-1]存入rf[k…t] //前一子表非空
如果j<=t，將r[i…v]存入rf[k…t] //后一子表非空
⑸ 合并結(jié)束。

【算法10.11】
void Merge(ElemType *r，ElemType *rf，int u，int v，int t)
{
for(i=u，j=v，k=u；i<v&&j<=t；k++)
{ if(r[i].key<r[j].key)
{ rf[k]=r[i]；i++；}
else
{ rf[k]=r[j]；j++；}
}
if(i<v) rf[k…t]=r[i…v-1]；
if(j<=t) rf[k…t]=r[j…t]；
}

一.兩路歸并的迭代算法
1個元素的表總是有序的。所以對n個元素的待排序列，每個元素可看成1個有序子

表長度均為2。再進行兩兩合并，直到生成n個元素按關(guān)鍵碼有序的表。
【算法10.12】
void MergeSort(S_TBL *p，ElemType *rf)
{ /*對*p表歸并排序，*rf為與*p表等長的輔助數(shù)組*/
ElemType *q1，*q2；
q1=rf；q2=p->elem；
for(len=1；len<p->length；len=2*len) /*從q2歸并到q1*/
{ for(i=1；i+2*len-1<=p->length；i=i+2*len)
Merge(q2，q1，i，i+len，i+2*len-1)； /*對等長的兩個子表合并*/
if(i+len-1<p->length)
Merge(q2，q1，i，i+len，p->length)； /*對不等長的兩個子表合并*/
else if(i<=p->length)
while(i<=p->length) /*若還剩下一個子表，則直接傳入*/
q1[i]=q2[i]；
q1<-->q2； /*交換，以保證下一趟歸并時，仍從q2歸并到q1*/
if(q1!=p->elem) /*若最終結(jié)果不在*p表中，則傳入之*/
for(i=1；i<=p->length；i++)
p->elem[i]=q1[i]；
}
}

二.兩路歸并的遞歸算法
【算法10.13】
void MSort(ElemType *p，ElemType *p1，int s，int t)
{ /*將p[s…t]歸并排序為p1[s…t]*/
if(s==t) p1[s]=p[s]
else
{ m=(s+t)/2； /*平分*p表*/
MSort(p，p2，s，m)； /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/
MSort(p，p2，m+1，t)； /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/
Merge(p2，p1，s，m+1，t)； /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/
}
}

void MergeSort(S_TBL *p)
{ /*對順序表*p作歸并排序*/
MSort(p->elem，p->elem，1，p->length)；
}

【效率分析】
需要一個與表等長的輔助元素數(shù)組空間，所以空間復(fù)雜度為O(n)。
對n個元素的表，將這n個元素看作葉結(jié)點，若將兩兩歸并生成的子表看作它們的父結(jié)點，則歸并過程對應(yīng)由葉向根生成一棵二叉樹的過程。所以歸并趟數(shù)約等于二叉樹的高度-1，即log2n，每趟歸并需移動記錄n次，故時間復(fù)雜度為O(nlog2n)。

10.6基數(shù)排序
基數(shù)排序是一種借助于多關(guān)鍵碼排序的思想，是將單關(guān)鍵碼按基數(shù)分成“多關(guān)鍵碼”進行排序的方法。

10.6.1 多關(guān)鍵碼排序
撲克牌中52張牌，可按花色和面值分成兩個字段，其大小關(guān)系為：
花色： 梅花 < 方塊 < 紅心 < 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若對撲克牌按花色、面值進行升序排序，得到如下序列：
梅花2,3,...,A，方塊2,3,...,A，紅心2,3,...,A，黑心2,3,...,A
即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關(guān)系才由面值的大小確定。這就是多關(guān)鍵碼排序。
為得到排序結(jié)果，我們討論兩種排序方法。
方法1：先對花色排序，將其分為4個組，即梅花組、方塊組、紅心組、黑心組。再對每個組分別按面值進行排序，最后，將4個組連接起來即可。
方法2：先按13個面值給出13個編號組(2號，3號，...，A號)，將牌按面值依次放入對應(yīng)的編號組，分成13堆。再按花色給出4個編號組(梅花、方塊、紅心、黑心)，將2號組中牌取出分別放入對應(yīng)花色組，再將3號組中牌取出分別放入對應(yīng)花色組，……，這樣，4個花色組中均按面值有序，然后，將4個花色組依次連接起來即可。
設(shè)n個元素的待排序列包含d個關(guān)鍵碼{k1，k2，…，kd}，則稱序列對關(guān)鍵碼{k1，k2，…，kd}有序是指：對于序列中任兩個記錄r[i]和r[j](1≤i≤j≤n)都滿足下列有序關(guān)系：

其中k1稱為最主位關(guān)鍵碼，kd稱為最次位關(guān)鍵碼。
多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序
逐次排序，分兩種方法：
最高位優(yōu)先(Most Significant Digit first)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD法。
最低位優(yōu)先(Least Significant Digit first)法，簡稱LSD法：先從kd開始排序，再對kd-1進行排序，依次重復(fù)，直到對k1排序后便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法二即是LSD法。

10.6.2鏈?zhǔn)交鶖?shù)排序
將關(guān)鍵碼拆分為若干項，每項作為一個“關(guān)鍵碼”，則對單關(guān)鍵碼的排序可按多關(guān)鍵碼排序方法進行。比如，關(guān)鍵碼為4位的整數(shù)，可以每位對應(yīng)一項，拆分成4項；又如，關(guān)鍵碼由5個字符組成的字符串，可以每個字符作為一個關(guān)鍵碼。由于這樣拆分后，每個關(guān)鍵碼都在相同的范圍內(nèi)(對數(shù)字是0～9，字符是'a'～'z')，稱這樣的關(guān)鍵碼可能出現(xiàn)的符號個數(shù)為“基”，記作RADIX。上述取數(shù)字為關(guān)鍵碼的“基”為10；取字符為關(guān)鍵碼的“基”為26?；谶@一特性，用LSD法排序較為方便。
基數(shù)排序：從最低位關(guān)鍵碼起，按關(guān)鍵碼的不同值將序列中的記錄“分配”到RADIX個隊列中，然后再“收集”之。如此重復(fù)d次即可。鏈?zhǔn)交鶖?shù)排序是用RADIX個鏈隊列作為分配隊列，關(guān)鍵碼相同的記錄存入同一個鏈隊列中，收集則是將各鏈隊列按關(guān)鍵碼大小順序鏈接起來。

【例10.8】以靜態(tài)鏈表存儲待排記錄，頭結(jié)點指向第一個記錄。鏈?zhǔn)交鶖?shù)排序過程如下圖。
圖(a)：初始記錄的靜態(tài)鏈表。

圖(b):第一趟按個位數(shù)分配，修改結(jié)點指針域，將鏈表中的記錄分配到相應(yīng)鏈隊列中。
圖(c):第一趟收集：將各隊列鏈接起來，形成單鏈表。

圖(d):第二趟按十位數(shù)分配，修改結(jié)點指針域，將鏈表中的記錄分配到相應(yīng)鏈隊列中。
圖(e):第二趟收集：將各隊列鏈接起來，形成單鏈表。

圖(f):第三趟按百位數(shù)分配，修改結(jié)點指針域，將鏈表中的記錄分配到相應(yīng)鏈隊列中。
圖(g):第三趟收集：將各隊列鏈接起來，形成單鏈表。此時,序列已有序。

圖10.10
【算法10.14】
#define MAX_KEY_NUM 8 /*關(guān)鍵碼項數(shù)最大值*/
#define RADIX 10 /*關(guān)鍵碼基數(shù)，此時為十進制整數(shù)的基數(shù)*/
#define MAX_SPACE 1000 /*分配的最大可利用存儲空間*/
typedef struct{
KeyType keys[MAX_KEY_NUM]； /*關(guān)鍵碼字段*/
InfoType otheritems； /*其它字段*/
int next； /*指針字段*/
}NodeType； /*表結(jié)點類型*/
typedef struct{
NodeType r[MAX_SPACE]； /*靜態(tài)鏈表，r[0]為頭結(jié)點*/
int keynum； /*關(guān)鍵碼個數(shù)*/
int length； /*當(dāng)前表中記錄數(shù)*/
}L_TBL； /*鏈表類型*/
typedef int ArrayPtr[radix]； /*數(shù)組指針，分別指向各隊列*/

void Distribute(NodeType *s，int i，ArrayPtr *f，ArrayPtr *e)
{ /*靜態(tài)鏈表ltbl的r域中記錄已按(kye[0]，keys[1]，…，keys[i-1])有序)*/
/*本算法按第i個關(guān)鍵碼keys[i]建立RADIX個子表，使同一子表中的記錄的keys[i]相同*/
/*f[0…RADIX-1]和e[0…RADIX-1]分別指向各子表的第一個和最后一個記錄*/
for(j=0；j<RADIX；j++) f[j]=0； /* 各子表初始化為空表*/
for(p=r[0].next；p；p=r[p].next)
{ j=ord(r[p].keys[i])； /*ord將記錄中第i個關(guān)鍵碼映射到[0…RADIX-1]*/
if(!f[j]) f[j]=p；
else r[e[j]].next=p；
e[j]=p； /* 將p所指的結(jié)點插入到第j個子表中*/
}
}

void Collect(NodeType *r，int i，ArrayPtr f，ArrayPtr e)
{/*本算法按keys[i]自小到大地將f[0…RADIX-1]所指各子表依次鏈接成一個鏈表*e[0…RADIX-1]為各子表的尾指針*/
for(j=0；!f[j]；j=succ(j))； /*找第一個非空子表，succ為求后繼函數(shù)*/
r[0].next=f[j]；t=e[j]； /*r[0].next指向第一個非空子表中第一個結(jié)點*/
while(j<RADIX)
{ for(j=succ(j)；j<RADIX-1&&!f[j]；j=succ(j))； /*找下一個非空子表*/
if(f[j]) {r[t].next=f[j]；t=e[j]；} /*鏈接兩個非空子表*/
}
r[t].next=0； /*t指向最后一個非空子表中的最后一個結(jié)點*/
}
void RadixSort(L_TBL *ltbl)
{ /*對ltbl作基數(shù)排序，使其成為按關(guān)鍵碼升序的靜態(tài)鏈表，ltbl->r[0]為頭結(jié)點*/
for(i=0；i<ltbl->length；i++) ltbl->r[i].next=i+1；
ltbl->r[ltbl->length].next=0； /*將ltbl改為靜態(tài)鏈表*/
for(i=0；i<ltbl->keynum；i++) /*按最低位優(yōu)先依次對各關(guān)鍵碼進行分配和收集*/
{ Distribute(ltbl->r，i，f，e)； /*第i趟分配*/
Collect(ltbl->r，i，f，e)； /*第i趟收集*/
}
}
【效率分析】
時間效率：設(shè)待排序列為n個記錄，d個關(guān)鍵碼，關(guān)鍵碼的取值范圍為radix，則進行鏈?zhǔn)交鶖?shù)排序的時間復(fù)雜度為O(d(n+radix))，其中，一趟分配時間復(fù)雜度為O(n)，一趟收集時間復(fù)雜度為O(radix)，共進行d趟分配和收集。
空間效率：需要2*radix個指向隊列的輔助空間，以及用于靜態(tài)鏈表的n個指針。

10.7外排序
10.7.1外部排序的方法
外部排序基本上由兩個相互獨立的階段組成。首先，按可用內(nèi)存大小，將外存上含n個記錄的文件分成若干長度為k的子文件或段(segment)，依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對它們進行排序，并將排序后得到的有序子文件重新寫入外存。通常稱這些有序子文件為歸并段或順串；然后，對這些歸并段進行逐趟歸并，使歸并段(有序子文件)逐漸由小到大，直至得到整個有序文件為止。
顯然，第一階段的工作已經(jīng)討論過。以下主要討論第二階段即歸并的過程。先從一個例子來看外排序中的歸并是如何進行的？

假設(shè)有一個含 10000 個記錄的
文件，首先通過10次內(nèi)部排序得到
10個初始?xì)w并段 R1～R10 ，其中每
一段都含1000個記錄。然后對它們
作如圖10.11所示的兩兩歸并，直至
得到一個有序文件為止。

從圖10.11可見，由10個初始?xì)w并段到一個有序文件，共進行了四趟歸并，每一趟

將兩個有序段歸并成一個有序段的過程，若在內(nèi)存中進行，則很簡單，前面討論的2-路歸并排序中的Merge函數(shù)便可實現(xiàn)此歸并。但是，在外部排序中實現(xiàn)兩兩歸并時，不僅要調(diào)用Merge函數(shù)，而且要進行外存的讀/寫，這是由于我們不可能將兩個有序段及歸并結(jié)果同時放在內(nèi)存中的緣故。對外存上信息的讀/寫是以“物理塊”為單位。假設(shè)在上例中每個物理塊可以容納200個記錄，則每一趟歸并需進行50次“讀”和50次“寫”，四趟歸并加上內(nèi)部排序時所需進行的讀/寫，使得在外排序中總共需進行500次的讀/寫。
一般情況下，外部排序所需總時間=
內(nèi)部排序(產(chǎn)生初始?xì)w并段)所需時間 m*tis
+外存信息讀寫的時間 d*tio
+內(nèi)部歸并排序所需時間 s*utmg
其中：tis是為得到一個初始?xì)w并段進行的內(nèi)部排序所需時間的均值；tio是進行一次外存讀/寫時間的均值；utmg是對u個記錄進行內(nèi)部歸并所需時間；m為經(jīng)過內(nèi)部排序之后得到的初始?xì)w并段的個數(shù)；s為歸并的趟數(shù)；d為總的讀/寫次數(shù)。由此，上例10000個記錄利用2-路歸并進行排序所需總的時間為：
10*tis+500*tio+4*10000tmg
其中tio取決于所用的外存設(shè)備，顯然，tio較tmg要大的多。因此，提高排序效率應(yīng)主要著眼于減少外存信息讀寫的次數(shù)d。
下面來分析d和“歸并過程”的關(guān)系。若對上例中所得的10個初始?xì)w并段進行5-平衡歸并(即每一趟將5個或5個以下的有序子文件歸并成一個有序子文件)，則從下圖可見，僅需進行二趟歸并，外部排序時總的讀/寫次數(shù)便減少至2×100+100=300，比2-路歸并減少了200次的讀/寫。
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10
└─┴─┼─┴─┘ └─┴─┼─┴─┘
R1' R2'
└────┬────┘
有序文件
圖10.12
可見，對同一文件而言，進行外部排序時所需讀/寫外存的次數(shù)和歸并的趟數(shù)s成正比。而在一般情況下，對m個初始?xì)w并段進行k-路平衡歸并時，歸并的趟數(shù)
可見，若增加k或減少m便能減少s。下面分別就這兩個方面討論之。
10.7.2多路平衡歸并的實現(xiàn)
從上式可見，增加k可以減少s，從而減少外存讀/寫的次數(shù)。但是，從下面的討論中又可發(fā)現(xiàn)，單純增加k將導(dǎo)致增加內(nèi)部歸并的時間utmg。那末，如何解決這個矛盾呢？
先看2-路歸并。令u個記錄分布在兩個歸并段上，按Merge函數(shù)進行歸并。每得到歸并后的含u個記錄的歸并段需進行u-1次比較。
再看k-路歸并。令u個記錄分布在k個歸并段上，顯然，歸并后的第一個記錄應(yīng)是k個歸并段中關(guān)鍵碼最小的記錄，即應(yīng)從每個歸并段的第一個記錄的相互比較中選出最小者，這需要進行k-1次比較。同理，每得到歸并后的有序段中的一個記錄，都要進行k-1次比較。顯然，為得到含u個記錄的歸并段需進行(u-1)(k-1)次比較。由此，對n個記錄的文件進行外部排序時，在內(nèi)部歸并過程中進行的總的比較次數(shù)為s(k-1)(n-1)。假設(shè)所得初始?xì)w并段為m個，則可得內(nèi)部歸并過程中進行比較的總的次數(shù)為

k而減少外存信息讀寫時間所得效益，這是我們所不希望的。然而，若在進行k-路歸并時利用“敗者樹”(Tree of Loser)，則可使在k個記錄中選出關(guān)鍵碼最小的記錄時僅需進

它不再隨k的增長而增長。
何謂“敗者樹”？它是樹形選擇排序的一種變型。相對地，我們可稱圖10.5和圖10.6中二叉樹為“勝者樹”，因為每個非終端結(jié)點均表示其左、右子女結(jié)點中“勝者”。反之，若在雙親結(jié)點中記下剛進行完的這場比賽中的敗者，而讓勝者去參加更高一層的比賽，便可得到一棵“敗者樹”。
【例10.9】

(a) (b)
圖10.13 實現(xiàn)5-路歸并的敗者樹

圖10.13(a)即為一棵實現(xiàn)5-路歸并的敗者樹ls[0…4]，圖中方形結(jié)點表示葉子結(jié)點(也可看成是外結(jié)點)，分別為5個歸并段中當(dāng)前參加歸并的待選擇記錄的關(guān)鍵碼；敗者樹中根結(jié)點ls[1]的雙親結(jié)點ls[0]為“冠軍”，在此指示各歸并段中的最小關(guān)鍵碼記錄為第三段中的記錄；結(jié)點ls[3]指示b1和b2兩個葉子結(jié)點中的敗者即是b2，而勝者b1和b3(b3是葉子結(jié)點b3、b4和b0經(jīng)過兩場比賽后選出的獲勝者)進行比較，結(jié)點ls[1]則指示它們中的敗者為b1。在選得最小關(guān)鍵碼的記錄之后，只要修改葉子結(jié)點b3中的值，使其為同一歸并段中的下一個記錄的關(guān)鍵碼，然后從該結(jié)點向上和雙親結(jié)點所指的關(guān)鍵碼進行比較，敗者留在該雙親，勝者繼續(xù)向上直至樹根的雙親。如圖10.13(b)所示。當(dāng)?shù)?/span>3個歸并段中第2個記錄參加歸并時，選得最小關(guān)鍵碼記錄為第一個歸并段中的記錄。為了防止在歸并過程中某個歸并段變?yōu)榭眨梢栽诿總€歸并段中附加一個關(guān)鍵碼為最大的記錄。當(dāng)選出的“冠軍”記錄的關(guān)鍵碼為最大值時，表明此次歸并已完成。由于實現(xiàn)k-路歸并的敗者樹

的初始化也容易實現(xiàn)，只要先令所有的非終端結(jié)點指向一個含最小關(guān)鍵碼的葉子結(jié)點，然后從各葉子結(jié)點出發(fā)調(diào)整非終端結(jié)點為新的敗者即可。

下面程序中簡單描述了利用敗者樹進行k-路歸并的過程，為了突出如何利用敗者樹進行歸并，避開了外存信息存取的細(xì)節(jié)，可以認(rèn)為歸并段已存在。

【算法10.15】
typedef int LoserTree[k]; /*敗者樹是完全二叉樹且不含葉子，可采用順序存儲結(jié)構(gòu)*/

typedef struct{
KeyType key;
}ExNode,External[k]; /*外結(jié)點，只存放待歸并記錄的關(guān)鍵碼*/

void K_Merge(LoserTree *ls,External *b) /*k-路歸并處理程序*/
{ /*利用敗者樹ls將編號從0到k-1的k個輸入歸并段中的記錄歸并到輸出歸并段*/
/*b[0]到b[k-1]為敗者樹上的k個葉子結(jié)點，分別存放k個輸入歸并段中當(dāng)前記錄的關(guān)鍵碼*/
for(i=0;i<k;i++) input(b[i].key); /*分別從k個輸入歸并段讀入該段當(dāng)前第一個記錄的*/
/*關(guān)鍵碼到外結(jié)點*/
CreateLoserTree(ls); /*建敗者樹ls，選得最小關(guān)鍵碼為b[0].key*/
while(b[ls[0]].key!=MAXKEY)
{ q=ls[0]; /*q指示當(dāng)前最小關(guān)鍵碼所在歸并段*/
output(q); /*將編號為q的歸并段中當(dāng)前(關(guān)鍵碼為b[q].key的記錄寫至輸出歸并段)*/
input(b[q].key); /*從編號為q的輸入歸并段中讀入下一個記錄的關(guān)鍵碼*/
Adjust(ls,q); /*調(diào)整敗者樹，選擇新的最小關(guān)鍵碼*/
}
output(ls[0]); /*將含最大關(guān)鍵碼MAXKEY的記錄寫至輸出歸并段*/
}

void Adjust(LoserTree *ls,int s) /*選得最小關(guān)鍵碼記錄后，從葉到根調(diào)整敗者樹，選下一個最小關(guān)鍵碼*/
{ /*沿從葉子結(jié)點b[s]到根結(jié)點ls[0]的路徑調(diào)整敗者樹*/
t=(s+k)/2; /*ls[t]是b[s]的雙親結(jié)點*/
while(t>0)
{ if(b[s].key>b[ls[t]].key) s<-->ls[t]; /*s指示新的勝者*/
t=t/2;
}
ls[0]=s;
}

void CreateLoserTree(LoserTree *ls) /*建立敗者樹*/
{ /*已知b[0]到b[k-1]為完全二叉樹ls的葉子結(jié)點存有k個關(guān)鍵碼，沿從葉子到根的k條路徑*/
/*將ls調(diào)整為敗者樹*/
b[k].key=MINKEY; /*設(shè)MINKEY為關(guān)鍵碼可能的最小值*/
for(i=0;i<k;i++) ls[i]=k; /*設(shè)置ls中“敗者”的初值*/
for(i=k-1;k>0;i--) Adjust(ls,i); /*依次從b[k-1],b[k-2],…,b[0]出發(fā)調(diào)整敗者*/
}

最后要提及一點，k值的選擇并非越大越好，如何選擇合適的k是一個需要綜合考慮的問題。