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

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

1、Chapter8Sort什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(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個(gè)記錄的序列為{R1,R2,…，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系：Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2,…，Rpn}的操作

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

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

4、三步進(jìn)行：3．將entry[i]插入(復(fù)制)到entry[j+1]的位置上。2．將entry[j+1..i-1]中的所有記錄均后移一個(gè)位置；1．在entry[1..i-1]中查找entry[i]的插入位置，entry[1..j].key?entry[i].key

5、從entry[i-1]起向前進(jìn)行順序查找，監(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、[0]jentry[i]j=i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置令i=2，3，…,n,實(shí)現(xiàn)整個(gè)序列的排序。for(i=2;i<=n;++i)if(entry[i].keyvoidSortable_list::insertion_sort(){//對順序表L作直接插入排序。for(i=2;i<=size();++i)if(entry[i].key

7、ntry[i-1].key){}}entry[0]=entry[i];//復(fù)制為監(jiān)視哨for(j=i-1;entry[0].key

8、動(dòng)”的次數(shù)：因?yàn)閑ntry[1..i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在entry[1..i-1]中查找entry[i]的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉６?、折半插入排序Templ