數(shù)據(jù)結(jié)構(gòu)第二十二講

第二十二講1、2、總復(fù)習(xí)110.5歸并排序歸并排序(MergeSort)也是一種常用的排序方法，“歸并”的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。如圖8-11為兩組有序表的歸并，有序表{4,25,34,56,69,74}和{15,26,34,47,52}，通過歸并把它們合并成一個(gè)有序表{4,15,25,26,34,34,47,52,56,69,74}。圖8-11兩組有序表的歸并2二路歸并排序的基本思想是：將有n個(gè)記錄的待排序列看作n個(gè)有序子表，每個(gè)有序子表的長(zhǎng)度為1，然后從第一個(gè)有序子表開始，把相鄰的兩個(gè)有序子表兩兩合并，得到n/2個(gè)長(zhǎng)度為2或1的有序子表（當(dāng)有序子表的個(gè)數(shù)為奇數(shù)時(shí)，最后一組合并得到的有序子表長(zhǎng)度為1），這一過程稱為一趟歸并排序。再將有序子表兩兩歸并，如此反復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序表為止。上述每趟歸并排序都需要將相鄰的兩個(gè)有序子表兩兩合并成一個(gè)有序表，這種歸并方法稱為二路歸并排序。31．兩個(gè)有序表的合并算法Merge()。設(shè)線性表R[low..m]，和R[m+1..high]是兩個(gè)已排序的有序表，存放在同一數(shù)組中相鄰的位置上，將它們合并到一個(gè)數(shù)組Rl中，合并過程如下：(1)比較線性表R[low..m]與R[m+1..high]的第一個(gè)記錄，將其中關(guān)鍵字值較小的記錄移入表R1(如果關(guān)鍵字值相同，可將R[low..m]的第一個(gè)記錄移入R1中)。(2)將關(guān)鍵字值較小的記錄所在線性表的長(zhǎng)度減1，并將其后繼記錄作為該線性表的第一個(gè)記錄。反復(fù)執(zhí)行上述過程，直到線性表R[low..m]或R[m+1..high]之一成為空表，然后將非空表中剩余的記錄移入R1中，此時(shí)Rl成為一個(gè)有序表。算法描述如下：4voidMerge(RecTypeR[],RecTypeR1[],intlow,intm,inthigh){//R[low..m]和R[m+1..high]是兩個(gè)有序表inti=low,j=m+l,k=low;//k是Rl的下標(biāo)，i、j分別為R[low..m]和R[m+1..high]的下標(biāo)

while(i<=m&&j<=high){

//在R[low..m]和R[m+1..high]均未掃描完時(shí)循環(huán)

if(R[i].key<=R[j].key){//將R[low..m]中的記錄放入R1中

R1[k]=R[i];i++;k++;

}else{//將R[m+1..high]中的記錄放入R1中

R1[k]=R[j];j++;k++;

}}5while(i<=m){//將R[low..m]余下部分復(fù)制到R1

R1[k]=R[i];i++;k++;}

while(j<=high){//將R[m+1..high]余下部分復(fù)制到R1

R1[k]=R[j];

j++;k++;}}62．一趟歸并排序的算法MergePass()。一趟歸并排序的算法調(diào)用n/(2*length)次歸并算法merge()，將R[1..n]中前后相鄰且長(zhǎng)度為length的有序子表進(jìn)行兩兩歸并，得到前后相鄰且長(zhǎng)度為2*length的有序表，并存放在R1[1..n]中。如果n不是2*length的整數(shù)倍，則可出現(xiàn)兩種情況：一種情況是，剩下一個(gè)長(zhǎng)度為length的有序子表和一個(gè)長(zhǎng)度小于length的子表，合并之后其有序表的長(zhǎng)度小于2*length；另一種情況是，只剩下一個(gè)子表，其長(zhǎng)度小于等于length，此時(shí)不調(diào)用算法merge()，只需將其直接放入數(shù)組R1中，準(zhǔn)備進(jìn)行下一趟歸并排序。算法描述如下：7voidMergePass(RecTypeR[],RecTypeR1[],intlength,intn){inti=0,j;while(i+2*length-l<n){Merge(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;//歸并長(zhǎng)度為length的兩相鄰有序子表

}

if(i+length-1<n-1)//余下兩個(gè)有序子表，其中一個(gè)長(zhǎng)度小于lengh

Merge(R,R1,i,i+length-1,n-1);//歸并兩個(gè)有序表

else

for(j=i;j<n;j++)//剩下一個(gè)有序子表，其長(zhǎng)度小于lengh

R1[j]=R[j];}83．歸并排序算法Merge--_Sort()兩路歸并排序需要由多趟歸并過程實(shí)現(xiàn)。第一趟length=1，以后每執(zhí)行一趟歸并后將length加倍。第一趟歸并的結(jié)果存放在R1中；第二趟將數(shù)組R1中的有序子表兩兩合并，結(jié)果存放在數(shù)組R中；如此反復(fù)進(jìn)行。為使最終排序結(jié)果存放在數(shù)組R中，進(jìn)行歸并的趟數(shù)必須是偶數(shù)。因此當(dāng)只需奇數(shù)趟歸并即可完成排序時(shí)，應(yīng)再進(jìn)行一趟歸并，只是此時(shí)只剩下一個(gè)長(zhǎng)度不大于length的有序表，直接從數(shù)組R1復(fù)制到R中即可。算法描述如下：voidMerge--_Sort(RecTypeR[],intn){intlength=1;while(length<n){MergePass(R,R1,length,n);length=2*length;MergePass(R1,R,length,n);length=2*length;}}9【例10-8】初始序列為｛23，56，42，37，15，84，72，27，18｝用二路歸并排序法排序?！窘狻颗判蚝蟮慕Y(jié)果為：｛15，18，23，27，37，42，56，72，84｝，整個(gè)歸并過程如圖8-12所示。圖10-12歸并排序示例10顯然，n個(gè)記錄進(jìn)行二路歸并排序時(shí)，歸并的趟數(shù)為O(log2n)，每趟歸并中，關(guān)鍵字的比較次數(shù)不超過n，因此，二路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。對(duì)序列進(jìn)行歸并排序時(shí)，除采用二路歸并排序外，還可以采用多路歸并排序方法（可參考其它有關(guān)書籍）。歸并排序需要的輔助空間R1與待排序記錄的數(shù)量相等，因此二路歸并排序的空間復(fù)雜度為O(n)，這是常用的排序方法中空間復(fù)雜度最差的一種排序方法。另外，從排序的穩(wěn)定性看，二路歸并排序是一種穩(wěn)定的排序方法。1110.6各種排序方法的比較在前面幾節(jié)中討論了內(nèi)部排序的方法。對(duì)于內(nèi)部排序主要介紹了四大類排序方法：插入排序（直接插入排序、折半插入排序和希爾排序）、交換排序（冒泡排序和快速排序）、選擇排序（簡(jiǎn)單選擇排序和堆排序）、歸并排序。詳細(xì)討論了各種排序方法的基本原理，并從時(shí)間復(fù)雜性、空間復(fù)雜性以及排序的穩(wěn)定性三方面討論了各種排序方法的時(shí)效性，介紹了各排序方法的實(shí)現(xiàn)算法及其存在的優(yōu)缺點(diǎn)。如果待排序的數(shù)據(jù)量很小，最好選擇編程簡(jiǎn)單的排序算法，因?yàn)樵谶@種情況下采用編程復(fù)雜、效率較高的排序方法所能節(jié)約的計(jì)算機(jī)時(shí)間是很有限的。反之，如果待處理的數(shù)據(jù)量很大，特別是當(dāng)排序過程作為應(yīng)用程序的一部分需要經(jīng)常執(zhí)行時(shí)，就應(yīng)該認(rèn)真分析和比較各種排序方法，從中選出運(yùn)行效率最高的方法。12下面具體比較一下各種排序方法，以便實(shí)現(xiàn)不同的排序處理。(1)插入排序的原理：向有序序列中依次插入無序序列中待排序的記錄，直到無序序列為空，對(duì)應(yīng)的有序序列即為排序的結(jié)果，其主旨是“插入”。(2)交換排序的原理：先比較大小，如果逆序就進(jìn)行交換，直到有序。其主旨是“若逆序就交換”。(3)選擇排序的原理：先找關(guān)鍵字最小的記錄，再放到已排好序的序列后面，依次選擇，直到全部有序，其主旨是“選擇”。(4)歸并排序的原理：依次對(duì)兩個(gè)有序子序列進(jìn)行“合并”，直到合并為一個(gè)有序序列為止，其主旨是“合并”。(5)基數(shù)排序的原理：按待排序記錄的關(guān)鍵字的組成成分進(jìn)行排序的一種方法，即依次比較各個(gè)記錄關(guān)鍵字相應(yīng)“位”的值，進(jìn)行排序，直到比較完所有的“位”，即得到一個(gè)有序的序列。各種排序方法的工作原理不同，對(duì)應(yīng)的性能也有很大的差別，下面通過一個(gè)表格可以看到各排序方法具體的時(shí)間性能、空間性能等方面的區(qū)別。13表10-2內(nèi)部排序方法的時(shí)間性能、空間性能表14依據(jù)這些因素，可得出如下幾點(diǎn)結(jié)論：(1)若n較?。ㄈ鏽值小于50），對(duì)排序穩(wěn)定性不作要求時(shí)，宜采用選擇排序方法，若關(guān)鍵字的值不接近逆序，亦可采用直接插入排序法。但如果規(guī)模相同，且記錄本身所包含的信息域比較多的情況下應(yīng)首選簡(jiǎn)單選擇排序方法。因?yàn)橹苯硬迦肱判蚍椒ㄖ杏涗浳恢玫囊苿?dòng)操作次數(shù)比直接選擇排序多，所以選用直接選擇排序?yàn)橐恕?2)如果序列的初始狀態(tài)已經(jīng)是一個(gè)按關(guān)鍵字基本有序的序列，則選擇直接插入排序方法和冒泡排序方法比較合適，因?yàn)椤盎尽庇行虻男蛄性谂判驎r(shí)進(jìn)行記錄位置的移動(dòng)次數(shù)比較少。(3)如果n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法，即快速排序、堆排序或歸并排序方法?？焖倥判蚴悄壳肮J(rèn)的內(nèi)部排序的最好方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序所需的平均時(shí)間最少；堆排序所需的時(shí)間與快速排序相同，但輔助空間少于快速排序，并且不會(huì)出現(xiàn)最壞情況下時(shí)間復(fù)雜性達(dá)到O(n2)的狀況。這兩種排序方法都是不穩(wěn)定的，若要求排序穩(wěn)定則可選用歸并排序。通?？梢詫⑺椭苯硬迦肱判蚪Y(jié)合在一起用。先利用直接插入排序求得兩個(gè)子文件，然后，再進(jìn)行兩兩歸并。15前面討論的排序算法，除基數(shù)排序外，都是在一維數(shù)組上實(shí)現(xiàn)的，當(dāng)記錄本身信息量較大時(shí)，為了避免移動(dòng)記錄而浪費(fèi)大量的時(shí)間，可以采用鏈表作為存儲(chǔ)結(jié)構(gòu)，如插入排序和歸并排序都易于在鏈表上實(shí)現(xiàn)；但有的方法，如快速排序和堆排序，在鏈表上卻難于實(shí)現(xiàn)，在這種情況下，可以提取關(guān)鍵字建立索引表，然后，對(duì)索引表進(jìn)行排序。然而更為簡(jiǎn)單的方法是引入一個(gè)整型向量作為輔助表。排序前，若排序算法中要求交換，則只需交換相對(duì)應(yīng)的向量，而無需交換具體的記錄內(nèi)容；排序結(jié)束后，向量就指示了記錄之間的順序關(guān)系。16本章小結(jié)

排序是軟件設(shè)計(jì)中最常用的運(yùn)算之一。排序分為內(nèi)部排序和外部排序，涉及多種排序的方法。內(nèi)部排序是將待排序的記錄全部放在內(nèi)存的排序。本章所討論的各種內(nèi)部排序的方法大致可分為：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。插入排序算法的基本思想是：將待序列表看做是左、右兩部分，其中左邊為有序序列，右邊為無序序列，整個(gè)排序過程就是將右邊無序序列中的記錄逐個(gè)插入到左邊的有序序列中。直接插入排序是這類排序算法中最基本的一種，然而，該排序法時(shí)間性能取決于待排序記錄的初始特性。折半插入排序是通過折半查找的方法在有序表中查找記錄插入位置的排序方法。希爾排序算法是一種改進(jìn)的插入排序，其基本思想是：將待排記錄序列劃分為若干組，在每組內(nèi)先進(jìn)行直接插入排序，以使組內(nèi)序列基本有序，然后再對(duì)整個(gè)序列進(jìn)行直接插入排序。其時(shí)間性能不取決于待排序記錄的初始特性。17交換排序的基本思想是：兩兩比較待排序列的記錄關(guān)鍵字，發(fā)現(xiàn)逆序即交換?；谶@種思想的排序有冒泡排序和快速排序兩種。冒泡排序的基本思想是：從一端開始，逐個(gè)比較相鄰的兩個(gè)記錄，發(fā)現(xiàn)逆序即交換。然而，其時(shí)間性能取決于待排序記錄的初始特性?？焖倥判蚴且环N改進(jìn)的交換排序，其基本思想是：以選定的記錄為中間記錄，將待排序記錄劃分為左、右兩部分，其中左邊所確記錄的關(guān)鍵字不大于右邊所有記錄的關(guān)鍵字，然后再對(duì)左右兩部分分別進(jìn)行快速排序。18選擇排序的基本思想是：在每一趟排序中，在待排序子表中選出關(guān)鍵字最小或最大的記錄放在其最終位置上。直接選擇排序和堆排序是基于這一思想的兩個(gè)排序算法。直接選擇排序算法采用的方法較直觀：通過對(duì)待排序子表中完整地比較一遍以確定最大(小)記錄，并將該記錄放在子表的最前(后)面。堆排序就是利用堆來進(jìn)行的一種排序，其中堆是一個(gè)滿足特定條件的序列，該條件用完全二叉樹模型表示為每個(gè)結(jié)點(diǎn)不大于(小于)其左、右孩子的值。利用堆排序可使選擇下一個(gè)最大(小)數(shù)的時(shí)間加快，因而提高算法的時(shí)間復(fù)雜度，達(dá)到O(nlog2n)。歸并排序是一種基于歸并的排序，其基本操作是指將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。首先將n個(gè)待排序記錄看成n個(gè)長(zhǎng)度為1的有序序列，第一趟歸并后變成n/2個(gè)長(zhǎng)度為2或1的有序序列；再進(jìn)行第二趟歸并，如此反復(fù)，最終得到一個(gè)長(zhǎng)度為n的有序序列。歸并排序的時(shí)間復(fù)雜度為O(nlog2n)，最初待排序記錄的排列順序?qū)\(yùn)算時(shí)間影響不大，不足之處就是需要占用較大的輔助空間。1919．對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是()。選擇B.冒泡C.快速D.插入22．下列排序算法中()不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序AB2023．下列排序算法中()排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。選擇B.冒泡C.歸并D.堆26．一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)CC2143．對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是（）。A．{21,25,5,17,9,23,30}B．{25,23,30,17,21,5,9}C．{21,9,17,30,25,23,5}Ｄ．{5,9,17,21,23,25,30}44．對(duì)關(guān)鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結(jié)果為（）。(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)AB2248.快速排序方法在（）情況下最不利于發(fā)揮其長(zhǎng)處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)相同值C.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D.要排序的數(shù)據(jù)已基本有序50.以下序列不是堆的是()。A.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)DD2351．下列四個(gè)序列中，哪一個(gè)是堆（）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1552.堆排序是（）類排序，堆排序平均執(zhí)行的時(shí)間復(fù)雜度和需要附加的存儲(chǔ)空間復(fù)雜度分別是（）

A.插入B.交換C.歸并D.基數(shù)E.選擇

F.O（n2）和O（1）G.O（nlog2n）和O（1）H.O（nlog2n）和O（n）I.O（n2）和O（n）CEG241、選擇題（40分，20道*2），考查基本概念，基本原理；2、填空題（10分，10個(gè)空*2），考查基本概念，基本原理，部分簡(jiǎn)單操作和程序的編寫；3、應(yīng)用題（操作