數(shù)據(jù)結(jié)構(gòu)與算法分析第8講排序

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

1、Chapter8Sort什么是排序？排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52,49,80,36,14,58,61,23,97,75調(diào)整為14,23,36,49,52,58,61,75,80,97一般情況下，假設(shè)含n個記錄的序列為{R1,R2,…，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系：Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2,…，

2、Rpn}的操作稱作排序。內(nèi)部排序和外部排序若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。三、內(nèi)部排序的方法內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)基于不同的“擴大”有序序列長度的方法，內(nèi)部排序方法大致可分下列幾種類型：插入類交換類選擇類歸并類其它方法1.插入類將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度

3、。2.交換類通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。3.選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。4.歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。5.其它方法數(shù)據(jù)類型插入排序有序序列entry[1..i-1]entry[i]無序序列entry[i..n]一趟直接插入排序的基本思想：有序序列entry[1..i]無序序列entr

4、y[i+1..n]實現(xiàn)“一趟插入排序”可分三步進行：3．將entry[i]插入(復(fù)制)到entry[j+1]的位置上。2．將entry[j+1..i-1]中的所有記錄均后移一個位置；1．在entry[1..i-1]中查找entry[i]的插入位置，entry[1..j].key?entry[i].key

5、-1]中查找entry[i]的插入位置”算法的實現(xiàn)要點：從entry[i-1]起向前進行順序查找，監(jiān)視哨設(shè)置在entry[0]；entry[0]=entry[i];//設(shè)置“哨兵”循環(huán)結(jié)束表明entry[i]的插入位置為j+1entry[0]jentry[i]for(j=i-1;entry[0].key

6、].key;--j);entry[j+1]=entry[j]entry[0]jentry[i]j=i-1上述循環(huán)結(jié)束后可以直接進行“插入”插入位置令i=2，3，…,n,實現(xiàn)整個序列的排序。for(i=2;i<=n;++i)if(entry[i].keyvoidSortable_list::insertion_sort(){//對順序表L作直接插入

7、排序。for(i=2;i<=size();++i)if(entry[i].key

8、：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動”的次數(shù)：“移動”的次數(shù)：因為entry[1..i-1]是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在entry[1..i-1]中查找entry[i]的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。二、折半插入排序Templ