《數(shù)據(jù)結構》排序》ppt課件

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

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

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

3、，是一種常用的排序方法處理記錄號插入位置下標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直接插入排序示例例如，有一組關鍵字序列為{91,67,35,62,29,72,46}，直接插入排序過程如圖9.1所示。用C語言描述的直接插入排序算法如下：typedefst

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

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

6、72,46,57}，插入排序的步長序列為4,2,1。希爾插入排序過程如圖9.2。步長序列的選擇沒有嚴格的規(guī)定，只要該序列{d1,d2,…,dt}滿足d1>d2>…>dt，并且當t≥1時，d1=1，該序列都可選作步長序列。一般采用步長序列為d1=n/2，di+1=di/2(n為待排序序列的長度)。用C語言描述的希爾排序算法如下：算法9.2希爾排序算法。voidShellSort(NODEarray[],intn)/*對存放在數(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