最新數(shù)據(jù)結(jié)構(gòu)-排序教學(xué)講義PPT課件.ppt

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

1、數(shù)據(jù)結(jié)構(gòu)-排序10.1概述10.2插入排序10.3快速排序10.4堆排序10.5歸并排序10.6基數(shù)排序10.7各種排序方法的綜合比較10.1概述一、排序的定義二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類三、內(nèi)部排序的方法內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)基于不同的“擴(kuò)大”有序序列長度的方法，內(nèi)部排序方法大致可分下列幾種類型：插入類交換類選擇類歸并類基數(shù)排序待排記錄的數(shù)據(jù)類型定義如下:#defineMAXSIZE1000//待排順序表最大長度typedefintKeyType;//

2、關(guān)鍵字類型為整數(shù)類型typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RcdType;//記錄類型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]閑置intlength;//順序表長度}SqList;//順序表類型1.插入類將無序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。2.交換類通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。3.選擇類從記錄的

3、無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。4.歸并類通過“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長度。10.2插入排序插入排序的基本思想是：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的有序序列R[1..i-1]R[i]無序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]無序序列R[i+1..n]實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3．將R[

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

5、13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。最簡單的排序法！一、直接插入排序利用“順序查找”實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”算法的實(shí)現(xiàn)要點(diǎn)：從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]；R[0]=R[i];//

6、設(shè)置“哨兵”循環(huán)結(jié)束表明R[i]的插入位置為j+1R[0]jR[i]for(j=i-1;R[0].key

7、]中查找R[i]的插入位置;插入R[i];}voidInsertionSort(SqList&L){//對(duì)順序表L作直接插入排序。for(i=2;i<=L.length;++i)if(L.r[i].key

8、體實(shí)現(xiàn)過程。*表示后一個(gè)25i=121254925*16080123456哨兵21i=2i=3