《數(shù)據(jù)結(jié)構(gòu)》排序》ppt課件

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

1、第9章排　序9.1插入排序9.2交換排序9.3選擇排序9.4歸并排序習(xí)題排序是針對(duì)記錄的集合{R1,R2,…,Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…,Kn}，重組記錄之間的關(guān)系，使記錄的排列次序滿足相應(yīng)的關(guān)鍵字的遞增或遞減關(guān)系。記錄的集合也稱為待排序序列。若待排序序列完全存放在內(nèi)存中，則該排序稱為內(nèi)部排序；若由于數(shù)據(jù)集合太大，在排序過程中，需對(duì)外存進(jìn)行訪問，則該排序稱為外部排序。有如下一組待排序序列(每個(gè)記錄只列出關(guān)鍵字一項(xiàng))：53,25,67(1),46,29,67(2),89,43,67(3),76括號(hào)里的數(shù)字代表等值記錄的位置，

2、若排序后為：25,29,43,46,53,67(1),67(2),67(3),76,89則稱所用的排序方法是穩(wěn)定的，反之，若三個(gè)等值記錄的排列順序不是上述順序，就稱所用排序的方法是不穩(wěn)定的。9.1插入排序9.1.1直接插入排序它的基本操作是在處理第i個(gè)記錄時(shí)，前面1到i-1記錄已排成有序，將第i個(gè)記錄插入有序表中，得到一個(gè)新的有序表，表的長度加1。當(dāng)表中只有一個(gè)記錄時(shí)，該表已是有序表，所以，可以從第二個(gè)記錄開始，逐個(gè)插入記錄，直至處理完待排序序列的所有記錄。直接插入排序的時(shí)間復(fù)雜度為O(n2)，并且是一種穩(wěn)定排序。當(dāng)n較小時(shí)，排序的效率較高

3、，是一種常用的排序方法處理記錄號(hào)插入位置下標(biāo)0123456i=1j=0[91]673562297246i=2j=0[6791]3562297246i=3j=0[356791]62297246i=4j=1[35626791]297246i=5j=0[2935626791]7246i=6j=4[293562677291]46i=7j=2[29354662677291]圖9.1直接插入排序示例例如，有一組關(guān)鍵字序列為{91,67,35,62,29,72,46}，直接插入排序過程如圖9.1所示。用C語言描述的直接插入排序算法如下：typedefst

4、ruct{intkey;…/*其他域*/}NODE;算法9.1直接插入排序算法。voidInsertSort(NODEarray[],intn)/*對(duì)存放在數(shù)組array[]中，長度為n的序列排序*/{inti,j;NODEx;for(i=1;i=0&&x.key

5、入步長由大到小不同的若干趟來進(jìn)行。初始，步長較大，相當(dāng)于把待排記錄序列分成若干子序列，各子序列中記錄的間隔為步長距離，由于子序列的長度小，所以子序列的插入排序的效率較高。以后各趟逐步減小步長，隨著步長的減小，子序列的長度在增加，但子序列中包含了上一趟經(jīng)過大的步長插入排序的結(jié)點(diǎn)，因此，已有部分結(jié)點(diǎn)有序，這樣，在排序中記錄移動(dòng)的次數(shù)就少，排序的效率也就高。最后一趟是步長為1，即：對(duì)整個(gè)序列直接插入排序，但這時(shí)整個(gè)序列已基本有序，只要做少量記錄移動(dòng)，就可將該序列排成有序。圖9.2希爾排序示例例如，有8個(gè)關(guān)鍵字序列為{91,67,35,62,29,

6、72,46,57}，插入排序的步長序列為4,2,1。希爾插入排序過程如圖9.2。步長序列的選擇沒有嚴(yán)格的規(guī)定，只要該序列{d1,d2,…,dt}滿足d1>d2>…>dt，并且當(dāng)t≥1時(shí)，d1=1，該序列都可選作步長序列。一般采用步長序列為d1=n/2，di+1=di/2(n為待排序序列的長度)。用C語言描述的希爾排序算法如下：算法9.2希爾排序算法。voidShellSort(NODEarray[],intn)/*對(duì)存放在數(shù)組array[]中，長度為n的序列希爾排序*/{inti,j,step;NODEx;for(step=n/2;step

7、>0;step=step/2)/*step不斷變小，直至為1*/{for(i=step;i=0&&x.key

8、是：首先比較array[n-1].key和array[n-2].key，若為逆序則交換之，然后比較array[n-2].key和array[n-3].key，依此類推，直到比較a