算法與數(shù)據(jù)結(jié)構(gòu)答案第10章排序

《算法與數(shù)據(jù)結(jié)構(gòu)答案第10章排序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第10章排序一、????????????基礎(chǔ)知識(shí)題10.1基本概念：內(nèi)排序，外排序，穩(wěn)定排序，不穩(wěn)定排序，順串，敗者樹(shù)，最佳歸并樹(shù)?！窘獯稹竣艃?nèi)排序和外排序若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類排序問(wèn)題為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類排序問(wèn)題為外部排序。內(nèi)部排序適用于記錄個(gè)數(shù)不多的文件，不需要訪問(wèn)外存，而外部排序適用于記錄很多的大文件，整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。⑵穩(wěn)定排序和不穩(wěn)定排序假設(shè)待排序記錄中有關(guān)鍵字Ki=Kj（i≠j），且在排序前的

2、序列中Ri領(lǐng)先于Rj。經(jīng)過(guò)排序后，Ri與Rj的相對(duì)次序保持不變（即Ri仍領(lǐng)先于Rj），則稱這種排序方法是穩(wěn)定的，否則稱之為不穩(wěn)定的。⑶順串外部排序通常經(jīng)過(guò)兩個(gè)獨(dú)立的階段完成。第一階段，根據(jù)內(nèi)存大小，每次把文件中一部分記錄讀入內(nèi)存，用有效的內(nèi)部排序方法（如快速排序、堆排序等）將其排成有序段，這有序段又稱順串或歸并段。⑷敗者樹(shù)敗者樹(shù)為提高外部排序的效率而采用的，是由參加比賽的n個(gè)元素作葉子結(jié)點(diǎn)而得到的完全二叉樹(shù)。每個(gè)非葉（雙親）結(jié)點(diǎn)中存放的是兩個(gè)子結(jié)點(diǎn)中的敗者數(shù)據(jù),而讓勝者去參加更高一級(jí)的比賽。另外,還需增加一個(gè)結(jié)點(diǎn),即結(jié)點(diǎn)0,存放比賽的全局

3、獲勝者。⑸最佳歸并樹(shù)在外部排序的多路平衡歸并的k叉樹(shù)中，為了提高效率減少對(duì)外存的讀寫次數(shù)，按哈夫曼樹(shù)構(gòu)造的k叉樹(shù)稱最佳歸并樹(shù)。這棵樹(shù)中只有度為0和度為k的結(jié)點(diǎn)。若用m表示歸并段個(gè)數(shù)，用nk表示度為k的個(gè)數(shù)，若(m-1)%(k-1)=0，則不需增加虛段，否則應(yīng)附加k-(m-1)%(k-1)-1個(gè)虛段（即第一個(gè)k路歸并使用(m-1)%(k-1)+1個(gè)歸并段）。?10.2設(shè)待排序的關(guān)鍵字序列為(15，21，6，30，23，6′，20，17)，試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說(shuō)明做了多少次比較。(1)直接插入排序(2)希爾排序(增量

4、為5，2，1)(3)起泡排序(4)快速排序(5)直接選擇排序(6)錦標(biāo)賽排序(7)堆排序(8)二路歸并排序(9)基數(shù)排序【解答】(1)直接插入排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟直接插入排序：【15，21】第二趟直接插入排序：【6，15，21】第三趟直接插入排序：【6，15，21，30】第四趟直接插入排序：【6，15，21，23，30】第五趟直接插入排序：【6，6′，15，21，23，30】第六趟直接插入排序：【6，6′，15，20，21，23，30】第七趟直接插入排序：【6，6′，15，17，20，21

5、，23，30】(2)希爾排序(增量為5，2，1)初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟希爾排序：6′，20，6，30，23，15，21，17第二趟希爾排序：6′，15，6，17，21，20，23，30第三趟希爾排序：6′，6，15，17，20，21，23，30?(3)起泡排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟起泡排序：15，6，21，23，6′，20，17，30第二趟起泡排序：6，15，21，6′，20，17，23，30第三趟起泡排序：6，15，6′，20，17，21，23，30

6、第四趟起泡排序：6，6′，15，17，20，21，30，23第五趟起泡排序：6，6′，15，17，20，21，30，23(4)快速排序初始關(guān)鍵字序列：15，21，6，30，23，6′，20，17第一趟快速排序：【6′，6】15【30，23，21，20，17】第二趟快速排序：6′，6，15【17，23，21，20】30第三趟快速排序：6′，6，15，17【23，21，20】30第四趟快速排序：6′，6，15，17，【20，21】23，30第五趟快速排序：6，6′，15，17，20，21，30，23(5)直接選擇排序初始關(guān)鍵字序列：15，21

7、，6，30，23，6′，20，17第一趟直接選擇排序：6，21，15，30，23，6′，20，17第二趟直接選擇排序：6，6′，15，30，23，21，20，17第三趟直接選擇排序：6，6′，15，30，23，21，20，17第四趟直接選擇排序：6，6′，15，17，23，21，20，30第五趟直接選擇排序：6，6′，15，17，20，21，23，30第六趟直接選擇排序：6，6′，15，17，20，21，23，30第七趟直接選擇排序：6，6′，15，17，20，21，23，30(6)錦標(biāo)賽排序初始關(guān)鍵字序列：15，21，6，30，23，6

8、′，20，17666’1566’171521630236’2017????????6’156’1530?6’171521∞?30236’2017???????????1515231530?23