第八章排序概述插入排序交換排序選擇排序歸并排序分配排序

外排序

1/106§1內(nèi)排序(Sorting)？簡單地說，排序就是將一組雜亂無章數(shù)據(jù)按一定規(guī)律排列起來（遞增或遞減）。排序是計算機中經(jīng)常碰到操作，通常稱為分類或整序。2/106排序幾個基本概念數(shù)據(jù)表(DataList)

待排序數(shù)據(jù)對象有限集合。關鍵字(Key)作為排序依據(jù)數(shù)據(jù)對象中屬性域。主關鍵字不一樣數(shù)據(jù)對象若關鍵字互不相同，則這種關鍵字稱為主關鍵字。排序確實切定義使一組任意排列對象變成一組按關鍵字線性有序?qū)ο?。用于排序測度關鍵字通常稱為排序碼。3/106排序幾個基本概念排序算法穩(wěn)定性判斷標準：排序碼相同數(shù)據(jù)對象在排序過程中是否保持前后次序不變。如2,2*,1，排序后若為1,2*,2則該排序方法是不穩(wěn)定。內(nèi)排序與外排序區(qū)分標準：排序過程是否全部在內(nèi)存進行。排序時間開銷

它是衡量算法好壞最主要標志。通慣用算法執(zhí)行中數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動次數(shù)來衡量。

4/106排序方法有很多，但簡單地判斷那一個算法最好，方便能夠普遍選取則是困難。評價排序算法好壞標準主要有兩條：算法執(zhí)行所需要時間和所需要附加空間。另外，算法本身復雜程度也是需要考慮一個原因。排序算法所需要附加空間普通都不大，矛盾并不突出。而排序是一個經(jīng)常執(zhí)行一種運算，往往屬于系統(tǒng)關鍵部分，所以排序時間開銷是算法好壞最主要標志。5/106排序亦稱分類，是計算機進行數(shù)據(jù)處理一個基本運算，其功效是將一個數(shù)據(jù)元素無序序列調(diào)整為一個有序序列。目標是到達當計算機中數(shù)據(jù)經(jīng)過排序后，提升工作效率和質(zhì)量。是在線性表上施加操作。

排序碼就是指作為排序依據(jù)數(shù)據(jù)項。數(shù)據(jù)元素能夠有多個排序碼。

排序準確定義：

有n個統(tǒng)計（元素）：{R1，R2，R3，………，Rn}及其對應排序碼序列：{K1，K2，K3，…………Kn}6/106所確定1，2，………….n一個排列p1,p2,p3,……,pn，使得對應排序碼滿足非遞減（或非遞增）關系：Kp1≤Kp2≤Kp3≤……≤Kpn或Kp1≥Kp2≥Kp3≥……≥Kpn即成為：{Rp1,Rp2,Rp3,……,Rpn}自然，不一樣排序策略就得到不一樣排序過程；

策略相同但排序所采取排序方法不一樣，都會有不一樣排序算法。常見排序策略和方法有：7/106直接插入排序shell插入排序（縮小增量排序）

插入策略二分插入排序表插入排序直接交換排序（冒泡排序）

交換策略快速排序直接選擇排序

選擇策略堆排序

歸并策略

分配策略基數(shù)排序8/106為簡單起見，數(shù)據(jù)存放結(jié)構采取統(tǒng)計數(shù)組形式。統(tǒng)計數(shù)組類型說明以下：typedefstruct{keytypekey;datatypeother;}rectype;

rectypeR[n];

其中n為統(tǒng)計總數(shù)加19/106§2插入排序基本原理，每步將一個待排序?qū)ο?，按其關鍵字大小，插入到前面已經(jīng)排好序一組對象適當位置上，直到對象全部插入為止。直接插入排序(InsertSort)希爾排序(ShellSort)10/1062.1直接插入排序(InsertSort)

基本思想：當插入第i個對象時，前面V[0],V[1],…,V[i-1]已經(jīng)排好序，此時，用v[i]關鍵字與V[i-1],V[i-2],…關鍵字次序進行比較，找到插入位置即將V[i]插入，原來位置上對象向后順移。11/106直接插入排序舉例i(0)(1)(2)(3)(4)(5)temp[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[16212525*49]08085[0816212525*49]12/106直接插入排序算法INSERTSORT(rectypeR[]){inti,j;for(i=1;i<n;i++){temp＝R[i];j＝i-1;while(j>=0&&temp.key<R[j].key){R[j+1]＝R[j];j++;}R[j+1]＝temp;}}13/106算法中引入附加統(tǒng)計temp作用：是進入查找循環(huán)之前，它保留了R[i]副本，使得不至于因統(tǒng)計后移而丟失R[i]中內(nèi)容。14/106算法分析直接插入排序算法由兩重循環(huán)組成，對于有n個統(tǒng)計排序，內(nèi)循環(huán)表明完成一趟排序所需進行統(tǒng)計關鍵字間比較和統(tǒng)計后移。若初始時關鍵字遞增有序，這是最好情況。每一趟排序中僅需進行一次關鍵字比較，所以總比較次數(shù)為n-1。在while循環(huán)之前和之中，最少要移動統(tǒng)計兩次，所以總比較次數(shù)為2(n-1)。若初始時關鍵字遞減有序，這是最壞情況。這時統(tǒng)計比較和移動次數(shù)分別為：15/106直接插入排序穩(wěn)定性直接插入排序是一個穩(wěn)定排序方法。原理：關鍵字相同兩個對象，在整個排序過程中，不會經(jīng)過比較而相互交換。16/1062.2希爾(shell)排序1959年由D.L.Shell提出，又稱縮小增量排序(Diminishing-incrementsort)?；舅枷耄涸诓迦肱判蛑校槐容^相鄰結(jié)點，一次比較最多把結(jié)點移動一個位置。假如對位置間隔較大距離結(jié)點進行比較，使得結(jié)點在比較以后能夠一次跨過較大距離，這么就能夠提升排序速度。17/106希爾排序基本過程

設待排序?qū)ο笮蛄杏衝個對象，首先取一個整數(shù)gap<n作為間隔，將全部對象分為gap個子序列，全部距離為gap對象放在同一個序列中，在每一個子序列中分別施行直接插入排序，然后縮小間隔gap，如取gap=gap/2，重復上述子序列劃分和排序工作，直到最終取gap為1為止。18/106希爾排序示例i(0)(1)(2)(3)(4)(5)gap21254925*1608121--25*325--1649--0821160825*2549221-08-25216-25*-4908162125*2549308162125*2549108162125*254919/106希爾排序算法rectypeR[n+d1];intd[t];

SHELLSORT(rectypeR[],intd[]){inti,j,k,h;rectypetemp;k＝0;dl=1;

do{h＝d[k];for(i=h+dl;i<n+dl;i++){temp＝R[i];j＝i-h;while(temp.key<R[j].key){p[j+h]＝R[j];j＝j-h;}R[j+h]＝temp;}k++;}while(h!=1);}20/106為什么shell排序時間性能優(yōu)于直接插入排序呢？因為直接插入排序在初態(tài)為正序時所需時間最少，實際上，初態(tài)為基本有序時直接插入排序所需比較和移動次數(shù)均較少。其次，當n值較小時，n和n2差別也較小，即直接插入排序最好時間復雜度O(n)和最壞時間復雜度O(n2)差別不大。在shell排序開始時增量較大，分組較多，每組記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量逐漸縮小，分組數(shù)逐漸降低，而各組記錄數(shù)目逐漸增多，但組內(nèi)元素已經(jīng)過多次排序，數(shù)組已經(jīng)比較接近有序狀態(tài)，所以新一趟排序過程也較塊。21/106希爾排序中gap取法Shell最初方案是gap=n/2,gap=gap/2，直到gap=1.Knuth方案是gap=gap/3+1其它方案有：都取奇數(shù)為好；或gap互質(zhì)為好等等。22/106希爾排序時間復雜度對希爾排序復雜度分析很困難，在特定情況下能夠準確地估算關鍵字比較和對象移動次數(shù)，不過考慮到與增量之間依賴關系，并要給出完整數(shù)學分析，當前還做不到。Knuth統(tǒng)計結(jié)論是，平均比較次數(shù)和對象平均移動次數(shù)在n1.25與1.6n1.25之間。23/106希爾排序穩(wěn)定性希爾排序是一個不穩(wěn)定排序方法。如序列322*524/106§3交換排序兩種常見交換排序冒泡排序(BubbleSort)快速排序(QuickSort)基本原理：每一次兩兩比較待排序統(tǒng)計排序碼，只要是逆序統(tǒng)計對，則進行交換，直到全部逆序?qū)Χ冀粨Q完為止。25/106冒泡排序基本思想首先依序比較n個待排序統(tǒng)計一端開始，依次兩兩比較排序碼，只要是逆序，則交換，這么完成一趟交換排序，結(jié)果就是將最大（或最?。┙y(tǒng)計交換到最終面（或最前面）；然后其余統(tǒng)計同法進行兩兩比較，每一趟都將較大（?。┰亟粨Q到最終（前）面，一直進行下去，直到最終一個統(tǒng)計排完或沒有要交換元素時候為止。3.1冒泡排序26/106冒泡排序基本過程首先從R[0]到R[n-1]對n個元素比較其排序碼，對逆序元素進行交換，完成一趟排序時，將排序碼值最到元素幾交換到最終一個位置，即R[n-1]，該過程相當于一趟冒泡；然后，又從R[0]到R[n-2]中又進行一趟交換冒泡，這么一直進行下去，直到最終一個元素R[0]或某一趟沒有交換元素為止。3.1，冒泡排序27/106冒泡排序示例i(0)(1)(2)(3)(4)(5)21254925*160810821254925*162081621254925*30816212525*4940816212525*4928/106冒泡排序算法voidbubblesort(R[]){for(i=0;i<n-2;i++){flag=1;for(j=n-1;j>=i;j++)if(R[j+1].key<R[j].key){t=R[j+1];R[j+1]=R[j];R[j]=t;Flag=0;}if(flag)break;}29/106冒泡排序時間復雜度考慮關鍵字比較次數(shù)和對象移動次數(shù)1、在最好情況下，初始狀態(tài)是遞增有序，一趟掃描就可完成排序，關鍵字比較次數(shù)為n-1，沒有統(tǒng)計移動。2、若初始狀態(tài)是反序，則需要進行n-1趟掃描，每趟掃描要進行n-i次關鍵字比較，且每次需要移動統(tǒng)計三次，所以，最大比較次數(shù)和移動次數(shù)分別為：冒泡排序方法是穩(wěn)定。30/106快速排序基本思想在當前無序區(qū)R[l]到R[h]任意取出一個元素作為比較“基準”，以此為基準將當前無序序列劃分為兩個部分：一部分元素中全部元素排序碼都小于基準元素；另一部分元素中全部元素排序碼都大于基準元素，則基準元素所在位置就是該元素排序最終位置；然后同法依次對兩部分元素進行分劃，繼續(xù)進行下去，直到得到一個有序序列為止。3.2快速排序31/106快速排序過程設置兩個指示器i和j,其初值分別為i=l,j=h.不妨取第一個元素R[i](=R[l])為基準，并將其保留于變量x中。令j從h開始往前掃描，直到找到第一個排序碼值小于x排序碼值時候統(tǒng)計R[j],則將其移動到I位置上（即相當于將比基準小元素移動到左邊）；然后，令i自i+1起往后掃描，直到找到第一個排序碼值大于x排序碼值時候統(tǒng)計R[i],則將其移動到j位置上（即相當于將比基準大元素移動到右邊）；接著，又令j從j-1開始往前掃描、重復上述交替改變掃描方向，從兩端各自向中間靠攏，直到i=j時，便是基準x最終位置，將其放在此位置上就完成了一次劃分。3.2快速排序32/106快速排序示例4938659776132749’

38659776132749’273865977613

49’4938

9776136549’4938139776

6549’493813

76976549’4938134976496549’49temp33/106快速排序算法intPARTITION(rectypeR[],intl,inth){inti,j;rectypetemp;i=l;j=h;temp=R[i];do{while((R[j].key>=temp.key)&&(i<j))j--;if(i<j)R[i++]=R[j];while((R[i].key<=temp.key)&&(i<j))i++;if(i<j)R[j--]=R[i];}while(i!=j);R[i]=temp;returni;}

34/106QUICKSORT(rectypeR[],ints1,intt1){inti;if(s1<t1){i=PARTITION(R,s1,t1);QUICKSORT(R,s1,i-1);QUICKSORT(R,i+1,t1);}}35/106快速排序時間復雜度2、最好情況是每次所取基準都是當前無序區(qū)“中值”統(tǒng)計，劃分結(jié)果是基準左右兩個無序子區(qū)長度大致相等。考慮關鍵字比較次數(shù)和對象移動次數(shù)1、最壞情況是每次劃分選取基準都是當前無序區(qū)中關鍵字最小（或最大）統(tǒng)計，劃分結(jié)果是基準左邊（或右邊）為空，劃分前后無序區(qū)元素個數(shù)降低一個，所以，排序必須做n-1趟，每一趟中需做n-i次比較，所以最大比較次數(shù)為36/106設C(n)表示對長度為n序列進行快速排序所需比較次數(shù)，顯然，它應該等于對長度為n無序區(qū)進行劃分所需比較次數(shù)n-1，加上遞歸地對劃分所得左右兩個無序子區(qū)進行快速排序所需比較次數(shù)。假設文件長度n=2k，k=log2n，所以有：37/106

快速排序統(tǒng)計移動次數(shù)不會大于比較次數(shù)，所以，快速排序最壞時間復雜度為O(n2)；最好時間復雜度為O(nlog2n)。能夠證實，快速排序平均時間復雜度也是O(nlog2n)。快速排序是不穩(wěn)定排序方法。38/106§4選擇排序兩種常見選擇排序直接選擇排序堆排序基本原理:將待排序結(jié)點分為已排序(初始為空)和為未排序兩組，依次將未排序結(jié)點中值最小結(jié)點插入已排序組中。39/106直接選擇排序基本思想在全部統(tǒng)計中選擇出排序碼最小統(tǒng)計，將其與第一個元素交換；然后其余統(tǒng)計中選擇出次小統(tǒng)計與第二個元素交換，一直進行下去；直到最終一個統(tǒng)計排完為止。4.1直接選擇排序40/106直接選擇排序過程首先從R[0]到R[n-1]中選擇出最小統(tǒng)計，將其與R[0]交換；然后，又從R[1]到R[n-1]中選擇出最小統(tǒng)計與R[1]交換；這么，當?shù)趇趟時從R[0]到R[i-1]就是已經(jīng)排好序，直到最終一個元素R[n-1]排好為止。4.1直接選擇排序41/106直

接

選擇

排序

示

例4938659776132749’1338659776492749’1327659776493849’1327389776496549’1327384976976549’1327384949’9765761327384949’6597761327384949’65769742/106直接選擇排序算法SELECTSORT(rectypeR[]){inti,j,k;rectypetemp;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(R[j].key<R[k].key)k=j;if(k!=i){temp=R[i];R[i]=R[k];R[k]=temp;}}}43/106直接選擇排序時間復雜度2.當文件為正序時，移動次數(shù)為0，文件初態(tài)為反序時，每趟排序均要執(zhí)行交換操作，總移動次數(shù)取最大值3(n-1)。直接選擇排序是不穩(wěn)定排序方法。1、不論初始狀態(tài)怎樣，在第i趟排序中選擇最小關鍵字統(tǒng)計，需做n-i次比較，所以總比較次數(shù)為：44/1064.2堆排序因為直接選擇排序過程中，每趟選擇過程中所進行比較，都沒有進行保留，從而造成了排序效率低下。于是引入樹形結(jié)構排序。

堆排序引入45/1064.2堆排序就是樹形結(jié)構排序。也就是體育比賽中錦標賽方式。其排序方法以下：

首先對

n個統(tǒng)計排序碼進行兩兩比較，得到[n/2]個較小元素，然后再將其進行兩兩比較，得到[n/4]個較小元素，依此進行下去，直到找到最小排序碼元素為止，則即完成一趟選擇，同法，每趟選擇都選擇出最小元素，直到最終一個元素時為止，即完成了排序。

1、錦標賽排序46/1064.2堆排序顯然，為了保留每次比較結(jié)果，都不得不需要大量輔助存放空間，于是為了填補這個缺點，1964年由Willioms提出了只需要一個輔助存放空間即可完成堆排序。

1、錦標賽排序47/1064.2堆排序堆定義：n個元素序列所對應排序碼序列{K1,K2,K3,……,Kn},當且僅當Ki≤K2iKi≤K2i+1或Ki≥K2iKi≥K2i+12、堆排序48/1064.2堆排序稱為小根堆（大根堆）。由此，若序列{K1,K2,K3,……,Kn}是小根堆，則堆頂元素（即為完全二叉樹根）必為序列中全部元素最小（最大）值。2、堆排序49/1064.2堆排序每次在得到一個堆之后，輸出堆頂元素后，使得剩下n-1個元素序列再建成一個堆，則得到n個元素次小元素。繼續(xù)進行下去，直到得到一個有序序列為止。由此可見：實現(xiàn)堆排序需要處理兩個問題：堆排序基本思想50/1064.2堆排序（1）怎樣由一個無序序列建立一個堆；（2）怎樣在輸出堆頂元素之后，調(diào)整剩下元素成為一個新堆。

堆排序基本思想51/1064.2堆排序?qū)τ诘诙€問題，在堆一個堆輸出堆頂元素之后，而且用最終一個元素代替后，就會破壞堆特征，故需要進行適當調(diào)整。依據(jù)堆定義，只需要依次與左右孩子進行比較，將左右孩子中較小者與其根結(jié)點進行交換，也就相當于將根結(jié)點往下“篩”，直到每一棵子樹都是小根堆為止。

堆排序基本思想52/1064.2堆排序

對于第一個問題，從一個無序序列建立成堆過程是一個重復“篩選”過程。

若將此序列組織成為一棵完全二叉樹，則最終一個非葉子結(jié)點就是第[n/2]個元素。所以我們篩選建堆過程只需要從第[n/2]處開始。循環(huán)到根結(jié)點時，調(diào)整之后二叉樹就是全部元素組成小根堆。

堆排序基本思想53/106101556253070101556253070小根堆示例54/106705630251510705630251510大根堆示例55/106可見：堆排序第一個工作是建堆，即把整個統(tǒng)計數(shù)組R[1]到R[n]調(diào)整為一個堆。顯然,只有一個結(jié)點樹是堆，而在完全二叉樹中，全部序號i>=low(n/2)結(jié)點都是葉子，所以以這些結(jié)點為根子樹都已是堆。這么，我們只需依次將序號為low(n/2)，low(n/2)-1，...，1結(jié)點作為根子樹都調(diào)整為堆即可。我們以大根堆為例進行說明56/106

若已知結(jié)點R[i]左右子樹已是堆，怎樣將以R[i]為根完全二叉樹也調(diào)整為堆？處理這一問題可采取“篩選法”，其基本思想是：因為R[i]左右子樹已是堆，這兩棵子樹根分別是各自子樹中關鍵字最大結(jié)點，所以我們必須在R[i]和它左右孩子中選取關鍵字最大結(jié)點放到R[i]位置上。若R[i]關鍵字已是三者中最大者，則無須做任何調(diào)整，以R[i]為根子樹已組成堆，不然必須將R[i]和含有最大關鍵字左孩子R[2i]或右孩子R[2i+1]進行交換。假定R[2i]關鍵字最大，將R[i]和R[2i]交換位置，交換之后有可能造成R[2i]為根子樹不再是堆，但因為R[2i]左右子樹依然是堆，于是能夠重復上述過程，將以R[2i]為根子樹調(diào)整為堆，...，如此逐層遞推下去，最多可能調(diào)整到樹葉。57/106例子：關鍵字序列為42，13，91，23，24，16，05，88，n=8，故從第四個結(jié)點開始調(diào)整4213912324160588421391232416058858/10642139188241605234213918824160523不調(diào)整59/1064213918824160523421391882416052360/1064288912324160513428891232416051361/10691884223241605139188422324160513建成堆62/106篩選算法SIFT(rectypeR[],inti;intm){intj;rectypetemp;temp=R[i];j=2*i;while(j<=m){if((j<m)&&(R[j].key<R[j+1].key))j++;if(temp.key<R[j].key){R[i]=R[j];i=j;j=2*i;}elsebreak;}R[i]=temp;}63/106

上述算法只是對一個指定結(jié)點進行調(diào)整。有了這個算法，則將初始無序區(qū)R[1]到R[n]建成一個大根堆，可用以下語句實現(xiàn)：for(i=n/2;i>=1;i--)SIFT(R,i,n)

因為建堆結(jié)果把關鍵字最大統(tǒng)計選到了堆頂位置，而排序結(jié)果應是升序，所以，應該將R[1]和R[n]交換，這就得到了第一趟排序結(jié)果。第二趟排序操作首先是將無序區(qū)R[1]到R[n-1]調(diào)整為堆。這時對于當前堆來說，它左右子樹依然是堆，所以，能夠調(diào)用SIFT函數(shù)將R[1]到R[n-1]調(diào)整為大根堆，選出最大關鍵字放入堆頂，然后將堆頂與當前無序區(qū)最終一個統(tǒng)計R[n-1]交換，如此重復進行下去。64/10691884223241605139188422324160513（a）初始堆R[1]到R[8]65/10613884223241605911388422324160591（b）第一趟排序之后66/106（c）重建堆R[1]到R[7]8824422313160591882442231316059167/10605244223131688910524422313168891（d）第二趟排序之后68/106（e）重建堆R[1]到R[6]4224162313058891422416231305889169/106（f）第三趟排序之后0524162313428891052416231342889170/106（g）重建堆R[1]到R[5]2423160513428891242316051342889171/106（h）第四趟排序之后1323160524428891132316052442889172/106（i）重建堆R[1]到R[4]2313160524428891231316052442889173/106（j）第五趟排序之后0513162324428891051316232442889174/106（k）重建堆R[1]到R[3]1613052324428891161305232442889175/106（l）第六趟排序之后0513162324428891051316232442889176/106（m）重建堆R[1]到R[2]1305162324428891130516232442889177/106（n）第七趟排序之后0513162324428891051316232442889178/106堆排序算法HEAPSORT(rectypeR[]){inti;rectypetemp;for(i=n/2;i>=1;i--)SIFT(R,i,n);for(i=n;i>=1;i--){temp=R[1];R[1]=R[i];R[i]=temp;SIFT(R,1,i-1);}}79/106堆排序時間復雜度堆排序時間復雜性為O(nlog2n)空間復雜性為O(1)堆排序是不穩(wěn)定排序方法。80/106§5歸并排序基本原理，經(jīng)過對兩個有序結(jié)點序列合并來實現(xiàn)排序。所謂歸并是指將若干個已排好序部分合并成一個有序部分。81/106兩路歸并基本思想歸并排序是利用“歸并”技術來進行排序，所謂歸并是指將若干個已經(jīng)排序子序列合并為一個有序序列。其算法比較簡單，能夠直接給出。82/106兩路歸并示例25

57

48

37

12

92

862557

3748

9212

8625374857

1286921225374857869283/106歸并算法voidmerge(R[],R1[],low,mid,hign)//R[low]到R[mid]與R[mid+1]到R[high]是兩個有序序列，結(jié)果是合并為一個有序序列R1[low]到R1[high]//{i=low;j<=mid+1;k=low;while(i<=mid&&j<=high)if(R[i].key<=R[j].key)R1[k++]=R[i++];elseR1[k++]=R[j++];while(i<=mid)R1[k++]=R[i++];while(j<=high)R1[k++]=R[j++];}84/106

歸并排序就是利用上述歸并操作實現(xiàn)排序。其基本思想是：將待排序列R[0]到R[n-1]看成n個長度為1有序子序列，把這些子序列兩兩歸并，便得到high(n/2)個有序子序列。然后再把這high(n/2)個有序子序列兩兩歸并，如此重復，直到最終得到一個長度為n有序序列。上述每次歸并操作，都是將兩個子序列歸并為一個子序列，這就是“二路歸并”，類似地還能夠有“三路歸并”或“多路歸并”。85/106歸并過程示例(25)(57)(48)(37)(12)(92)(86)(2557)(3748)(1292)(86)(25374857)(128692)(12253748578692)86/106一趟歸并算法歸并排序就是利用上述歸并操作實現(xiàn)排序。

其基本思想是：將待排序統(tǒng)計序列R[0]到R[n-1]看成為n個長度為1有序序列，將其進行兩兩歸并，則得到[n/2]個（n為基數(shù)時候則為[（n+1）/2]個）長度為2有序序列，然后繼續(xù)進行，直到最終得到一個長度為n有序序列為止。這就是2-路歸并排序。其中，最關鍵是將兩個長度為l有序序列歸并為長度為2l有序序列。87/106一趟歸并算法MERGEPASS(rectypeR[],rectypeR1[],intlength){inti,j;i=0;while(i+2*length-1<n){MERGE(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;}if(i+length-1<n-1)MERGE(R,R1,i,i+length-1,n-1);elsefor(j=i;j<n;j++)R1[j]=R[j];}88/106

在上述一趟歸并過程中，假如恰好配成對時候，即可正常完成，不然最終一次歸并時，可能有兩種情況：（1）(2k+1)*len<n<2(k+1)*len表示有兩個有序序列，但后一個長度不足len，此時歸并方法與前相同，僅僅是參數(shù)不一樣而已。（2）2k*len<n<2(k+1)*len表示只有一個有序序列，此時已經(jīng)是有序，故只需要復制到R1中即可。歸并排序就是從長度為1有序序列逐步歸并為長度為2，4，…,n循環(huán)過程。89/106歸并排序算法MERGESORT(rectypeR[]){intlength=1;while(length<n){MERGEPASS(R,R1,length);length=2*length;MERGEPASS(R1,R,length);length=2*length;}}

90/106算法復雜性分析歸并排序是穩(wěn)定排序方法。歸并排序在第i趟歸并后，有序子文件長度為2i，所以，所以，對于含有n個統(tǒng)計序列來說，必須做high(log2n)趟歸并，每趟歸并所花時間為O(n)。所以，二路歸并排序算法時間復雜度為O(nlog2n)，輔助數(shù)組所需空間為O(n)。91/106§6基數(shù)排序基本原理，采取“分配”和“搜集”方法，用對多關鍵字進行排序思想實現(xiàn)對單關鍵字進行排序方法。下面先介紹多關鍵字排序92/106多關鍵字排序方法示例如對撲克牌排序每張撲克牌有兩個“關鍵字”：花色和面值它們之間有次序優(yōu)先。對以上排序，能夠先對花色排序，或先對面值排序。93/106多關鍵字有序概念考慮對象序列{V0,V1,...,Vn-1}，每個對象Vi含d個關鍵字(Ki1,Ki2,...,Kid)。若對序列中任意兩個對象Vi和Vj都有(Ki1,Ki2,...,Kid)<(Kj1,Kj2,...,Kjd)則稱序列對關鍵字(Ki1,Ki2,...,Kid)有序，且K1稱為最高位關鍵字，Kd稱為最低位關鍵字。94/106多關鍵字排序原理：依據(jù)組成關鍵字各位值進行排序。實現(xiàn)基數(shù)排序兩種方法：1最高位優(yōu)先(MSD)排序：從關鍵字高位到低位2最低位優(yōu)先(LSD)排序：從關鍵字低位到高位MSD方法通常是一個遞歸過程。95/106多關鍵字排序（續(xù)）LSD和MSD方法也可應用于對一個關鍵字進行排序。此時可將單關鍵字Ki看成是一個子關鍵字組：(Ki1,Ki2,...,Kid)如對關鍵字取值范圍為0到999一組對象，可看成是(K1,K2,K3)組合。MSD方法按K1,K2,K3次序?qū)θ繉ο笈判?；LSD方法按K3,K2,K1次序?qū)θ繉ο笈判颉?6/106鏈式基數(shù)排序基數(shù)排序是一個經(jīng)典LSD排序方法，它利用“分配”和“搜集”兩種運算對單關鍵字進行排序。此時可將單關鍵字K看成是一個子關鍵字組：(Ki1,Ki2,...,Kid)排序過程：設關鍵字共有d位，讓j=d,d-1,...,1,依次執(zhí)行d次“分配”與“搜集”。97/1061792083069385998455927133B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e271933398455306208179859998/1062719333984553062081798599B[0].fB[1].fB[