數(shù)據(jù)結構與算法教學課件-第八章排序

主講人：劉曉靜青海大學計算機技術與應用系第八章排序主要內(nèi)容8.1排序的概念及其算法性能分析8.2插入排序8.3交換排序8.4選擇排序8.5歸并排序8.6內(nèi)部排序算法的分析8.1排序的概念及其算法性能分析8.1.1排序的概念8.1.2排序算法的性能評估8.1.1排序的概念排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。數(shù)據(jù)表(datalist):它是待排序數(shù)據(jù)元素的有限集合。排序碼(key):通常數(shù)據(jù)元素有多個屬性域,即多個數(shù)據(jù)成員組成,其中有一個屬性域可用來區(qū)分元素,作為排序依據(jù)。該域即為排序碼。每個數(shù)據(jù)表用哪個屬性域作為排序碼，要視具體的應用需要而定。8.1.1排序的概念排序：排序算法的穩(wěn)定性:如果在元素序列中有兩個元素r[i]和r[j],它們的排序碼k[i]==k[j],且在排序之前,元素r[i]排在r[j]前面。如果在排序之后,元素r[i]仍在元素r[j]的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的。內(nèi)排序與外排序:內(nèi)排序是指在排序期間數(shù)據(jù)元素全部存放在內(nèi)存的排序；外排序是指在排序期間全部元素個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。8.1.2排序算法的性能評估排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受元素排序碼序列初始排列及元素個數(shù)影響較大的，需要按最好情況和最壞情況進行估算。算法執(zhí)行時所需的附加存儲:評價算法好壞的另一標準。8.2插入排序8.2.1直接插入排序8.2.2折半插入排序8.2.3希爾排序8.2.1直接插入排序基本方法是：每步將一個待排序的元素，按其排序碼大小，插入到前面已經(jīng)排好序的一組元素的適當位置上,直到元素全部插入為止?；舅枷胧?當插入第i(i≥1)個元素時，前面的V[0],V[1],…,V[i-1]已經(jīng)排好序。這時，用V[i]的排序碼與V[i-1],V[i-2],…的排序碼順序進行比較，找到合適的插入位置將V[i]插入，原來位置上的元素向后順移。各趟排序結果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=2012345i=4i=5i=3012345temp21254925*16081621254925*160825*012345temp21254925*16080821254925*1608012345i=4時的排序過程完成1616012345temp21254925*08164916012345temp21254925*0816i=4j=3i=4j=22516012345temp214925*08162525*1621254925*0801234516i=4j=1i=4j=0i=4j=-1012345temp21254925*08162116#include"dataList.h"template<classT>voidInsertSort(dataList<T>&L,intleft,intright){

Element<T>temp;inti,j;for(i=left+1;i<=right;i++)if(L[i]<L[i-1]){//i-1之前的部分已經(jīng)有序

temp=L[i];j=i-1;do{//此處優(yōu)于for語句

L[j+1]=L[j];j--;}while(j>=left&&temp<L[j]);//停定位條件

L[j+1]=temp;}}; 直接插入排序的算法算法分析設待排序元素個數(shù)為currentSize=n,則該算法的主程序執(zhí)行n-1趟。排序碼比較次數(shù)和元素移動次數(shù)與元素排序碼的初始排列有關。直接插入排序是一種穩(wěn)定的排序方法。最好情況下，排序前元素已按排序碼從小到大有序，每趟只需與前面有序元素序列的最后一個元素比較1次，總的排序碼比較次數(shù)為n-1,元素移動次數(shù)為0。最壞情況下,第i趟時第i個元素必須與前面i個元素都做排序碼比較,并且每做1次比較就要做1次數(shù)據(jù)移動。則總排序碼比較次數(shù)KCN和元素移動次數(shù)RMN分別為平均情況下排序的時間復雜度為o(n2)。15算法分析8.2.2折半插入排序基本思想是:設在順序表中有一個元素序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已經(jīng)排好序的元素。在插入V[i]時,利用折半搜索法尋找V[i]的插入位置。template<classT>voidBinaryInsertSort(dataList<T>&L,constintleft,constintright){//利用折半搜索,在L.Vector[left]到L.Vector[i-1]中//查找L.Vector[i]應插入的位置,再進行插入。

Element<T>temp;inti,low,high,middle,k;for(i=left+1;i<=right;i++){

temp=L[i];low=left;high=i-1;//搜索范圍初值

while(low<=high){ //折半搜索插入位置

middle=(low+high)/2;

//取中點if(temp<L[middle])

//插入值小于中點值

high=middle-1; //向左縮小區(qū)間

elselow=middle+1; //否則,向右縮小區(qū)間

}//while語句繼續(xù)搜索

for(k=i-1;k>=low;k--)

L[k+1]=L[k];

//成塊移動,空出插入位置

L[low]=temp; //插入

}};折半搜索比順序搜索快,所以折半插入排序就

平均性能來說比直接插入排序要快。它所需的排序碼比較次數(shù)與待排序元素序列的初始排列無關，僅依賴于元素個數(shù)。在插入第i個元素時，需要經(jīng)過log2i+1

次排序碼比較,才能確定它應插入的位置。因此，將n個元素(為推導方便,設為n=2k)用折半插入排序所進行的排序碼比較次數(shù)為：折半插入排序是一個穩(wěn)定的排序方法。

算法分析算法分析當n較大時，總排序碼比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。在元素的初始排列已經(jīng)按排序碼排好序或接近有序時，直接插入排序比折半插入排序執(zhí)行的排序碼比較次數(shù)要少。折半插入排序的元素移動次數(shù)與直接插入排序相同，依賴于元素的初始排列。8.2.3希爾排序希爾排序方法又稱為縮小增量排序。該方法的基本思想是:

設待排序元素序列有n個元素,首先取一個整數(shù)gap<n作為間隔，將全部元素分為gap個子序列，所有距離為gap的元素放在同一個子序列中在每一個子序列中分別施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2，重復上述的子序列劃分和排序工作。直到最后取gap==1，將所有元素放在同一個序列中排序為止。8.2.3希爾排序開始時gap的值較大，子序列中的元素較少，排序速度較快;隨著排序進展，gap值逐漸變小,子序列中元素個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)元素已基本有序，所以排序速度仍然很快。21254925*16080123452125*i

=10849Gap=32516492516084925*0821252125*1621254925*160801234521i=20849Gap=22516491625*0821254925*08162125*2521254925*160801234521i

=308Gap=125164925*template<classT>

voidShellsort(dataList<T>&L,constintleft,constintright){inti,j,gap=right-left+1; //增量運算前的初值

Element<T>temp;do{

gap=gap/3+1; //求下一增量值

for(i=left+gap;i<=right;i++)if(L[i]<L[i-gap]){ //逆序,間隔gap

temp=L[i];j=i-gap;do{

L[j+gap]=L[j];j=j-gap;}while(j

>=

left&&temp<L[j]);

L[j+gap]=temp; //將vector[i]回送

}}while(gap>1);};算法分析Gap的取法有多種。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。knuth提出取gap=gap/3+1。還有人提出都取奇數(shù)為好，也有人提出各gap互質為好。對特定的待排序元素序列，可以準確地估算排序碼的比較次數(shù)和元素移動次數(shù)。想要弄清排序碼比較次數(shù)和元素移動次數(shù)與增量選擇之間的依賴關系，并給出完整的數(shù)學分析，還沒有人能夠做到。Knuth利用大量實驗統(tǒng)計資料得出:當n很大時，排序碼平均比較次數(shù)和元素平均移動次數(shù)大約在n1.25到1.6n1.25的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。希爾排序是一種不穩(wěn)定的排序方法。算法分析8.3交換排序8.3.1起泡排序8.3.2快速排序8.3.1起泡排序1.基本思想是兩兩比較待排序元素的排序碼，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之。直到所有元素都排好序為止。2.基本方法是：設待排序元素序列中的元素個數(shù)為n。最多作n-1趟，i=1,2,,n-1。在第i趟中從后向前，j=n-1,n-2,,i，順次兩兩比較V[j-1].key和V[j].key。如果發(fā)生逆序，則交換V[j-1]和V[j]。21254925*16080123452125*i=149251625160849Exchange=10825*4921Exchange=1i=2i=30816Exchange=125*252125*i=44916Exchange=00825213.起泡排序的算法template<classT>voidBubbleSort(dataList<T>&L,constintleft,constintright){intpass=left+1,exchange=1;while(pass<=right&&exchange){exchange=0; //標志為0假定未交換

for(intj=right;j>=pass;j--)if(L[j-1]>L[j]){ //逆序,此處用到j-1，

Swap(L[j-1],L[j]); //交換

exchange=1; //標志置為1,有交換

}pass++;

//已排好序的序列加１

}};4.算法分析第i趟對待排序元素序列V[i-1],V[i],,V[right]進行排序，結果將該序列中排序碼最小的元素交換到序列的第一個位置(i-1)。最多做n-1趟起泡就能把所有元素排好序。在元素的初始排列已經(jīng)按排序碼從小到大排好序時，此算法只執(zhí)行一趟起泡，做n-1次排序碼比較，不移動元素。這是最好的情形。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1≤

in)做n-i次排序碼比較,執(zhí)行n-i次元素交換。在最壞情形下總的排序碼比較次數(shù)KCN和元素移動次數(shù)RMN為：起泡排序需要一個附加元素以實現(xiàn)元素值的對換。起泡排序是一個穩(wěn)定的排序方法。4.算法分析8.3.2快速排序基本思想:任取待排序元素序列中的某個元素(例如取第一個元素)作為基準，按照該元素的排序碼大小，將整個元素序列劃分為左右兩個子序列：左側子序列中所有元素的排序碼都小于或等于基準元素的排序碼右側子序列中所有元素的排序碼都大于基準元素的排序碼基準元素則排在這兩個子序列中間(這也是該元素最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的元素都排在相應位置上為止。QuickSort(List){if(List的長度大于1){

將序列List劃分為兩個子序列

LeftList和

RightList;QuickSort(LeftList);QuickSort(RightList);

將兩個子序列

LeftList和

RightList

合并為一個序列List;}}算法描述21254925*16080123452125*i=14925*1625160849pivot08254921i=2i=308162525*21pivotpivotpivot21254925*160801234525*i=1劃分251625160849pivotpos0825*49081625*2521pivotpos21比較4次交換25,16iipivotpos21比較1次交換49,0849lowpivotpos交換21,08#include"dataList.h"template<classT>voidQuickSort_(dataList<T>&L,constintleft,constintright){//對元素Vector[left],...,Vector[right]進行排序,//pivot=L.Vector[left]是基準元素,排序結束后它的//位置在pivotPos,把參加排序的序列分成兩部分,

//左邊元素的排序碼都小于或等于它,右邊都大于它

if(left<right){ //元素序列長度大于1時

intpivotpos=L.Partition(left,right);//劃分

QuickSort(L,left,pivotpos-1);2.快速排序的算法

QuickSort(L,pivotpos+1,right); }};template<classT>intdataList<T>::Partition(constintlow,constinthigh){//數(shù)據(jù)表類的共有函數(shù)

intpivotpos=low;Element<T>pivot=Vector[low]; //基準元素

for(inti=low+1;i<=high;i++) //檢測整個序列,進行劃分

if(Vector[i]<pivot){pivotpos++;if(pivotpos!=i)Swap(Vector[pivotpos],Vector[i]);} //小于基準的交換到左側去

Vector[low]=Vector[pivotpos];Vector[pivotpos]=pivot; //將基準元素就位

returnpivotpos; //返回基準元素位置};練習10

8

6

12

15

4

19

20

算法quicksort是一個遞歸的算法,其遞歸樹如圖所示。算法partition利用序列第一個元素作為基準，將整個序列劃分為左右兩個子序列。算法中執(zhí)行了一個循環(huán)，只要是排序碼小于基準元素排序碼的元素都移到序列左側，最后基準元素安到位,函數(shù)返回其位置。2125*25490816快速排序可以遞歸實現(xiàn)，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹高度一致，理想情況為log2(n+1)。存儲開銷為O(log2n)。在最壞情況，即待排序序列已按從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到比上一次少一個元素的子序列。需經(jīng)過n-1趟才能把所有元素定位，且第i

趟需經(jīng)過n-i

次排序碼比較才能找到第i

個元素的安放位置，總的排序碼比較次數(shù)將達到用第一個元素作為基準元素

快速排序退化的例子

08

16212525*4908012345pivot初始

16212525*49

0816

212525*4921

081625

2525*49

081621

25*4925*

0816212549

0816212525*i=1i=2i=3i=4i=5從快速排序算法的遞歸樹可知，快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對一個元素定位后，該元素的左側子序列與右側子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。在n個元素的序列中，對一個元素定位所需時間為O(n)。若設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+2T(n/8))=3cn+8T(n/8)………

cnlog2n+nT(1)=O(nlog2n)可以證明，函數(shù)quicksort的平均計算時間也是O(nlog2n)。實驗結果表明:就平均計算時間而言，快速排序是內(nèi)排序方法中最好的一個?？焖倥判蛩惴ㄆ骄枰M行2nlnn次比較。因為2nlnn≈1.39nlog2n,所以快速排序平均情況下的比較次數(shù)比最好情況高約39%?？蓞⒖糝obertSedgewick,AlgorithmsinC++Parts1-4,Fundamentals,DataStructures,Sorting,Searching(中譯本：算法I-IV,C++實現(xiàn)——基礎、數(shù)據(jù)結構、排序和搜索，第3版中國電力出版社，2005年)3.關于快速排序的最好與平均性能其排序速度退化到簡單排序的水平,比直接插入排序還慢。占用附加存儲(棧)將達到O(n)。穩(wěn)定性：快速排序是一種不穩(wěn)定的排序方法。對于n較大的平均情況而言,快速排序是“快速”的,但是當n很小時,這種排序方法往往比其它簡單排序方法還要慢。有研究表明，當排序序列長度為5~25時，采用直接插入排序要比快速排序至少快10%。為此，一些與快速排序相關的改進算法應運而生。4.快速排序的算法分析基本思想是:每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i個待排序元素中選出排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟作完，待排序元素只剩下1個,就不用再選了。8.4選擇排序8.4.1直接選擇排序8.4.2鏈表直接選擇排序8.4.3堆排序8.4選擇排序1.直接選擇排序的基本步驟是：在一組元素V[i]～V[n-1]中選擇具有最小排序碼的元素；若它不是這組元素中的第一個元素,則將它與這組元素中的第一個元素對調(diào);在這組元素中剔除這個具有最小排序碼的元素。在剩下的元素V[i+1]～V[n-1]中重復執(zhí)行第①、②步,直到剩余元素只有一個為止。8.4.1

直接選擇排序21254925*16080123452125*i=0492516251608490825*4921i=1i=2081625*2521初始最小者

08交換21,08最小者

16交換25,16最小者

21交換49,214925*01234525*i=42516084925*21結果i=308162521最小者

25*無交換最小者

25無交換25211608各趟排序后的結果#include"dataList.h"template<classT>voidSelectSort(dataList<T>&L,constintleft,constintright){for(inti=left;i<right;i++){intk=i;//在L[i]到L[n-1]找最小排序碼元素

for(intj=i+1;j<=right;j++)

if(L[j]<L[k])k=j;if(k!=i)Swap(L[i],L[k]); //交換

}};2.直接選擇排序的算法i=1時選擇排序的過程012345160825*492125ikj492549250825*1621ikj25*25490825*211625ikj16<2549250825*1621012345ikj2116k

指示當前序列中最小者直接選擇排序的排序碼比較次數(shù)KCN與元素的初始排列無關。設整個待排序元素序列有n個元素，則第i趟選擇具有最小排序碼元素所需的比較次數(shù)總是n-i-1次。總的排序碼比較次數(shù)為//i從0開始元素移動次數(shù)與元素序列初始排列有關。當這組元素初始狀態(tài)是按其排序碼從小到大有序的時候,元素的移動次數(shù)達到最少RMN=0。鏈表直接選擇排序最壞情況是每一趟都要進行交換，總的元素移動次數(shù)為RMN=3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。//前例若待排序的數(shù)據(jù)元素順序存放于單鏈表中，每一趟排序先在鏈表中選擇關鍵碼值最大的元素，將它從鏈中摘下，再插入一個初始為空的新鏈表的首部。當所有元素都從原鏈表中摘下并插入到新鏈表中，則新鏈表中元素已經(jīng)有序鏈接起來。8.4.2鏈表直接選擇排序若待排序的數(shù)據(jù)元素順序存放于單鏈表中，每一趟排序先在鏈表中選擇關鍵碼值最大的元素，將它從鏈中摘下，再插入一個初始為空的新鏈表的首部。當所有元素都從原鏈表中摘下并插入到新鏈表中，則新鏈表中元素已經(jīng)有序鏈接起來。6015252515253515fh∧qp25f15∧h35∧pq=∧f35∧hpq=∧

f

=∧h35∧f∧∧1.鏈表直接選擇排序的示例2.

鏈表直接選擇排序的算法61單鏈表數(shù)據(jù)類型Linkedlist,每個結點數(shù)據(jù)類型LinkNode,包括data,link域intselectSort(LinkedList&L){LinkNode*f=L,*p,*q,*r,*s;//初始時f指向第一個表項

L=NULL;//變成空表頭

while(f!=NULL){p=s=f;q=r=NULL; //s指示當前最大元素

while(p!=NULL){if(p->data>s->data){s=p;r=q;}//記憶當前找到的排序碼最大結點與前驅

q=p;p=p->link;//循鏈繼續(xù)掃描下一個

}if(s==f)f=f->link;//當前首結點s從鏈中摘下

elser->link=s->link;//最大結點摘下,r為s的前驅

s->link=L;//插入當前最大結點

L=s;//結點s插入到結果鏈表的前端

}};利用堆及其運算,可以很容易地實現(xiàn)選擇排序的思路。堆排序分為兩個步驟根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法siftDown()形成初始堆;通過一系列的元素交換和重新調(diào)整堆進行排序。8.4.3堆排序堆已排好部分初始堆最大堆？最小堆？1.建立初始的最大堆212525*491608012345i212525*164908025431i21254925*1608初始排序碼集合21254925*1608i=2時的局部調(diào)整_無212525*491608012345i492525*16210802543121254925*160849252125*1608i=0時的局部調(diào)整形成最大堆i=1時的局部調(diào)整_無template<classT>siftDown(dataList<T>&L,constintstart,constintm){inti=start;intj=2*i+1; //j是i的左子女

Element<T>temp=L[i]; //暫存子樹根結點

while(j<=m){ //逐層比較

if(j<m&&L[j]<L[j+1])j++;

//讓j指向兩子女中的大者

if(temp>=L[j])break;//temp排序碼大則不調(diào)整

else{ //否則子女中的大者上移

L[i]=L[j];

i=j;j=2*j+1; //i下降到子女位置

}}

L[i]=temp; //temp放到合適位置};最大堆堆頂L.Vector[0]具有最大的排序碼，將L.Vector[0]與L.Vector[n-1]對調(diào),把具有最大

排序碼的元素交換到最后，再對前面的n-1個元素,使用堆的調(diào)整算法siftDown(L,0,n-2)，重新建立最大堆，具有次最大排序碼的元素又上浮到L.Vector[0]位置。再對調(diào)L.Vector[0]和L.Vector[n-2]，再調(diào)用siftDown(L,0,n-3),對前面的n-2個元素重新調(diào)整，…。如此反復執(zhí)行，最后得到全部排序好的元素序列。這個算法即堆排序算法，其細節(jié)在下面的程序中給出。2.基于初始堆進行堆排序492525*211608012345082525*16214902543149252125*160808252125*1649交換0號與5號元素,5號元素就位初始最大堆2525*082116490123451625*082521490254312525*210816491625*210825

49交換0號與4號元素,4號元素就位從0號到4號重新調(diào)整為最大堆25*1608212549012345081625*25214902543125*16210825

4908162125*

25

49交換0號與3號元素,3號元素就位從0號到3號重新調(diào)整為最大堆211625*082549012345081625*25214902543121160825*

25

49081621

25*

25

49交換0號與2號元素,2號元素就位從0號到2號重新調(diào)整為最大堆160825*212549012345081625*25214902543116082125*

25

490816

21

25*

25

49交換0號與1號元素,1號元素就位從0號到1號重新調(diào)整為最大堆3.堆排序的算法template<classT>voidHeapSort(dataList<T>&L){//對表L.Vector[0]到L.Vector[n-1]進行排序,使得表//中各個元素按其排序碼非遞減有序

inti,n=L.length();for(i=(n-2)/2;i>=0;i--)

//將表轉換為堆

siftDown(L,i,n-1); //先調(diào)整成初始堆

for(i=n-1;i>

0;i--){//對表排序,或改為i>=1

L.Swap(0,i);siftDown(L,0,i-1);//交換與調(diào)整

}};設堆中有n個結點,且2k-1≤

n<2k,則對應的完全二叉樹有k層。在第i層上的結點數(shù)≤2i-1

(i=1,…,k)。在第一個形成初始堆的for循環(huán)中對每一個非葉結點調(diào)用了一次堆調(diào)整算法siftDown(),該循環(huán)所用的比較次數(shù)為（移動次數(shù)同）：其中,i是層次編號,2i-1

是第i層的最大結點數(shù),(k-i)是第i層結點能夠移動的最大距離。4.算法分析第二個for循環(huán)中調(diào)用了n-1次siftDown()算法,該循環(huán)的計算時間為O(nlog2n)。因此,堆排序的時間復雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環(huán)中用來執(zhí)行元素交換時所用的一個臨時元素。因此，該算法的空間復雜性為O(1)。堆排序是一個不穩(wěn)定的排序方法。8.5歸并排序8.5.1歸并排序8.5.2迭代的歸并排序8.5.1歸并排序歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。元素序列L1中有兩個有序表Vector[left..mid]和Vector[mid+1..right]。它們可歸并成一個有序表,存于另一元素序列L2的Vector[left..right]

中。這種方法稱為兩路歸并

(2-waymerging)。變量i和j分別是表Vector[left..mid]和Vector[mid+1..right]的檢測指針。k是存放指針。8.5.1歸并排序歸并，是將兩個或兩個以上的有序表合并成一個新的有序表。元素序列L1中有兩個有序表Vector[left..mid]和Vector[mid+1..right]。它們可歸并成一個有序表,存于另一元素序列L2的Vector[left..right]

中。這種方法稱為兩路歸并

(2-waymerging)。變量i和j分別是表Vector[left..mid]和Vector[mid+1..right]的檢測指針。k是存放指針。當i

和j

都在兩個表的表長內(nèi)變化時,根據(jù)對應項的排序碼的大小,依次把排序碼小的元素排放到新表k所指位置中；當i

與j中有一個已經(jīng)超出表長時，將另一個表中的剩余部分照抄到新表中。08212525*49627293

163754leftmidmid+1rightinitListij0816212525*374954627293leftrightkmergeList迭代的歸并排序算法就是利用兩路歸并過程進行排序。其基本思想是：設初始元素序列有n個元素，首先把它看成是n個長度為1

的有序子序列（歸并項），做兩兩歸并，得到n/2

個長度為2

的歸并項（最后一個歸并項的長度為1）；再做兩兩歸并，得到n/4

個長度為4

的歸并項（最后一個歸并項長度可以短些）…，如此重復，最后得到一個長度為n的有序序列。8.5.2迭代的歸并排序迭代的歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16#include"dataList.h"template<classT>voidmerge(dataList<T>&L1,dataList<T>&L2,constintleft,constintmid,constintright){//L1.Vector[left..mid]與L1.Vector[mid+1..right]是兩//個有序表,將這兩個有序表歸并成一個有序表//L2.Vector[left..right]intk,i,j;i=left;j=mid+1;k=left;

//i,j是檢測指針,k是存放指針

1.兩路歸并算法while(i<=mid&&j<=right) //兩兩比較

if(L1[i]<=L1[j])L2[k++]=L1[i++