數(shù)據(jù)結構第二十講

數(shù)據(jù)結構第二十講1第1頁，共46頁，2023年，2月20日，星期六19.在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則應作()型調(diào)整以使其平衡。LLB.LRC.RLD.RR27.設有一組記錄的關鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中有（）個記錄。A．1B.2C.3D.431.設哈希表長為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關鍵字為15，38，61，84共四個，現(xiàn)要將關鍵字為49的結點加到表中，用二次探測再散列法解決沖突，則放入的位置是()A．8B．3C．5D．932.假定有k個關鍵字互為同義詞，若用線性探測法把這k個關鍵字存入散列表中，至少要進行多少次探測？()A．k-1次B.k次C.k+1次D.k（k+1）/2次CDDD第2頁，共46頁，2023年，2月20日，星期六34.散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應當以()取其值域的每個值。最大概率B.最小概率C.平均概率D.同等概率35.散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=Kmod17。采用線性探測法處理沖突，并將關鍵字序列26，25，72，38，8，18，59依次存儲到散列表中。（）元素59存放在散列表中的A．8B.9C.10D.11（2）存放元素59需要搜索的次數(shù)是（）。A．2B.3C.4D.536.將10個元素散列到100000個單元的哈希表中，則（）產(chǎn)生沖突。A.一定會B.一定不會C.仍可能會DDCC第3頁，共46頁，2023年，2月20日，星期六第10章排序

排序的概念及種類插入法排序的各種具體實現(xiàn)方法及算法分析選擇法排序的各種具體方法的實現(xiàn)及時間性能分析交換法排序的具體實現(xiàn)及性能分析歸并排序和基數(shù)排序的各自實現(xiàn)算法第4頁，共46頁，2023年，2月20日，星期六本章導讀

排序是日常工作和軟件設計中常用的運算之一。為了提高查詢速度需要將無序序列按照一定的順序組織成有序序列。由于需要排序的數(shù)據(jù)表的基本特性可能存在差異，使得排序方法也不同。如何合理地組織數(shù)據(jù)的邏輯順序，按照何種方式排出的序列最有效？這是本章要討論的主題。本章主要介紹排序的概念及幾種最常見的排序方法，討論其性能和特點，并在此基礎上進一步討論各種方法的適用場合，以便在實際應用中能根據(jù)具體的問題選擇合適的排序方法。第5頁，共46頁，2023年，2月20日，星期六10.1排序的基本概念10.1.1排序及其分類1．排序概念

排序（sorting）又稱分類，是數(shù)據(jù)處理領域中一種很常用的運算。排序就是把一組記錄或數(shù)據(jù)元素的無序序列按照某個關鍵字值（關鍵字）遞增或遞減的次序重新排列的過程。排序的主要目的就是實現(xiàn)快速查找。日常生活中通過排序以后進行檢索的例子屢見不鮮。如電話簿、病歷、檔案室中的檔案、圖書館和各種詞典的目錄表等，幾乎都需要對有序數(shù)據(jù)進行操作。第6頁，共46頁，2023年，2月20日，星期六假設含有n個記錄的序列為：{R1，R2，…，Rn}(1)其相應的關鍵字序列為：{K1，K2

，…，Kn}需確定1，2，…，n的一種排序p1，p2，…，pn，使其相應的關鍵字滿足如下關系：Kp1≤Kp2≤…≤Kpn(2)即使得式（1）的序列成為一個按關鍵字有序的序列{Rp1，Rp2，…，Rpn}

(3)這個將原有表中任意順序的記錄變成一個按關鍵字有序排列的過程稱為排序。第7頁，共46頁，2023年，2月20日，星期六2．排序分類

增排序和減排序：如果排序的結果是按關鍵字從小到大的次序排列的，就是增排序，否則就是減排序。（2）穩(wěn)定排序和不穩(wěn)定排序：假設Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri領先于Rj（即i<j）。若在排序后的排序中Ri仍領先于Rj，即那些具有相同關鍵字的記錄，經(jīng)過排序后它們的相對次序仍然保持不變，則稱這種排序方法是穩(wěn)定的；反之，若Rj領先于Ri，則稱所用的方法是不穩(wěn)定的。第8頁，共46頁，2023年，2月20日，星期六(3)內(nèi)部排序與外部排序：在排序中，若數(shù)據(jù)表中的所有記錄的排列過程都是在內(nèi)存中進行的，稱為內(nèi)部排序。由于待排序的記錄數(shù)量太多，在排序過程中不能同時把全部記錄放在內(nèi)存，需要不斷地通過在內(nèi)存和外存之間交換數(shù)據(jù)元素來完成整個排序的過程，稱為外部排序。在外部排序情況下，只有部分記錄進入內(nèi)存，在內(nèi)存中進行內(nèi)部排序，待排序完成后再交換到外部存儲器中加以保存。然后再將其它待排序的記錄調(diào)入內(nèi)存繼續(xù)排序。這一過程需要反復進行，直到全部記錄排出次序為止。顯然，內(nèi)部排序是外部排序的基礎，本章主要介紹內(nèi)部排序的各種方法。

第9頁，共46頁，2023年，2月20日，星期六10.1.2排序算法的效率分析

與許多算法一樣，對各種排序算法性能的評價主要從兩個方面來考慮，一是時間性能；二是空間性能。

1．

時間復雜度分析

排序算法的時間復雜度可用排序過程中記錄之間關鍵字的比較次數(shù)與記錄的移動次數(shù)來衡量。在本章各節(jié)中討論算法的時間復雜度時，一般都按平均時間復雜度進行估算；對于那些受數(shù)據(jù)表中記錄的初始排列及記錄數(shù)目影響較大的算法，按最好情況和最壞情況分別進行估算。第10頁，共46頁，2023年，2月20日，星期六2．空間復雜度分析

排序算法的空間復雜度是指算法在執(zhí)行時所需的附加存儲空間，也就是用來臨時存儲數(shù)據(jù)的內(nèi)存使用情況。

在以后的排序算法中，若無特別說明，均假定待排序的記錄序列采用順序表結構來存儲，即數(shù)組存儲方式，并假定是按關鍵字遞增方式排序。為簡單起見，假設關鍵字類型為整型。待排序的順序表類型的類型定義如下：typedefintKeyType//定義關鍵字類型typedefstructdataType//記錄類型{keytypekey;//關鍵字項elemtypeotherelement;//其他數(shù)據(jù)項}RecType; 第11頁，共46頁，2023年，2月20日，星期六10.2插入排序

插入排序的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子表中的適當位置，直到全部記錄插入完成為止。也就是說，將待序列表分成左右兩部分，左邊為有序表（有序序列），右邊為無序表（無序序列）。整個排序過程就是將右邊無序表中的記錄逐個插入到左邊的有序表中，構成新的有序序列。

根據(jù)不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希爾排序等。本章重點介紹直接插入排序、折半插入排序和希爾排序。

第12頁，共46頁，2023年，2月20日，星期六10.2.1直接插入排序

直接插入排序(InsertionSort)是所有排序方法中最簡單的一種排序方法。其基本原理是順次地從無序表中取出記錄Ri(1≤i≤n)，與有序表中記錄的關鍵字逐個進行比較，找出其應該插入的位置，再將此位置及其之后的所有記錄依次向后順移一個位置，將記錄Ri插入其中。假設待排序的n個記錄為{R1，R2，……，Rn}，初始有序表為[R1]，初始無序表為[R2…Rn]。當插入第i個記錄Ri(2≤i≤n)時，有序表為[R1…Ri-1]，無序表為[Ri…Rn]。將關鍵字Ki依次與Ki-1，Ki-2

，…，K1進行比較，找出其應該插入的位置，將該位置及其以后的記錄向后順移，插入記錄Ri，完成序列中第i個記錄的插入排序。當完成序列中第n個記錄Rn的插入后，整個序列排序完畢。

第13頁，共46頁，2023年，2月20日，星期六向有序表中插入記錄，主要完成如下操作：(1)搜索插入位置。(2)移動插入點及其以后的記錄空出插入位置。(3)插入記錄。假設將n個待排序的記錄順序存放在長度為n+1的數(shù)組R[1]～R[n]中。R[0]作為輔助空間，用來暫時存儲需要插入的記錄，起監(jiān)視哨的作用。直接插入排序算法如下:第14頁，共46頁，2023年，2月20日，星期六voidInsert_Sort(intR[],intn){inti,j;for(i=2;i<=n;i++)//表示待插入元素的下標{R[0]=R[i];//設置監(jiān)視哨保存待插入元素，騰出R[i]空間j=i-1;//j指示當前空位置的前一個元素while(R[0].key<R[j].key)//搜索插入位置并后移騰出空{(diào)R[j+1]=R[j];j--;}R[j+1]=R[0];//插入元素

}}第15頁，共46頁，2023年，2月20日，星期六顯然，開始時有序表中只有1個記錄[R[1]]，然后需要將R[2]～R[n]的記錄依次插入到有序表中，總共要進行n-1次插入操作。首先從無序表中取出待插入的第i個記錄R[i]，暫存在R[0]中；然后將R[0].key依次與R[i-1].key，R[i-2].key，…進行比較，如果R[0].key<R[i-j].key（1≤j≤i-1），則將R[i-j]后移一個單元；如果R[0].key≥R[i-j].key，則找到R[0]插入的位置i-j+1，此位置已經(jīng)空出，將R[0](即R[i])記錄直接插入即可。然后采用同樣的方法完成下一個記錄R[i+1]的插入排序。如此不斷進行，直到完成記錄R[n]的插入排序，整個序列變成按關鍵字非遞減的有序序列為止。在搜索插入位置的過程中，R[0].key與R[i-j].key進行比較時，如果j=i，則循環(huán)條件R[0].key<R[i-j].key不成立，從而退出while循環(huán)。由此可見R[0]起到了監(jiān)視哨的作用，避免了數(shù)組下標的出界。

第16頁，共46頁，2023年，2月20日，星期六【例10-1】假設有7個待排序的記錄，它們的關鍵字分別為23，4，15，8，19，24，15，用直接插入法進行排序?！窘狻恐苯硬迦肱判蜻^程如圖10-1所示。方括號[]中為已排好序的記錄的關鍵字，有兩個記錄的關鍵字都為15，為表示區(qū)別，將后一個15加下劃線。

第17頁，共46頁，2023年，2月20日，星期六第18頁，共46頁，2023年，2月20日，星期六空間性能：該算法僅需要一個記錄的輔助存儲空間，空間復雜度為O(1)。穩(wěn)定性：由于該算法在搜索插入位置時遇到關鍵字值相等的記錄時就停止操作，不會把關鍵字值相等的兩個數(shù)據(jù)交換位置，所以該算法是穩(wěn)定的。

時間性能：整個算法執(zhí)行for循環(huán)n-1次，每次循環(huán)中的基本操作是比較和移動，其總次數(shù)取決于數(shù)據(jù)表的初始特性，可能有以下幾種情況：（1）當初始記錄序列的關鍵字已是遞增排列時，這是最好的情況。算法中while語句的循環(huán)體執(zhí)行次數(shù)為0，因此，在一趟排序中關鍵字的比較次數(shù)為1，即R[0]的關鍵字與R[j]的關鍵字比較。而移動次數(shù)為2，即R[i]移動到R[0]中，R[0]移動到R[j+1]中。所以，整個排序過程中的比較次數(shù)和移動次數(shù)分別為(n-1)和2×(n-1)，因而其時間復雜度為O(n)。第19頁，共46頁，2023年，2月20日，星期六（2）當初始數(shù)據(jù)序列的關鍵字序列是遞減排列時，這是最壞的情況。在第i次排序時，while語句內(nèi)的循環(huán)體執(zhí)行次數(shù)為i。因此，關鍵字的比較次數(shù)為i，而移動次數(shù)為i+1。所以，整個排序過程中的比較次數(shù)和移動次數(shù)分別為：（3）一般情況下，可認為出現(xiàn)各種排列的概率相同，因此取上述兩種情況的平均值，作為直接插入排序關鍵字的比較次數(shù)和記錄移動次數(shù)，約為n2/4。所以其時間復雜度為O(n2)。根據(jù)上述分析得知：當原始序列越接近有序時，該算法的執(zhí)行效率就越高。第20頁，共46頁，2023年，2月20日，星期六10.2.2折半插入排序

直接插入排序的基本操作是在有序表中進行查找和插入，而在有序表中查找插入位置，可以通過折半查找的方法實現(xiàn)，由此進行的插入排序稱之為折半插入排序。所謂折半查找，就是在插入Ri時（此時R1，R2，…，Ri-1已排序），取Ri/2的關鍵字Ki/2

與Ki進行比較（i/2

表示取不大于i/2的最大整數(shù)），如果Ki<Ki/2，Ri的插入位置只能在R1和Ri/2

之間，則在R1和Ri/2-1之間繼續(xù)進行折半查找，否則在Ri/2+1和Ri-1

之間進行折半查找。如此反復直到最后確定插入位置為止。折半查找的過程是以處于有序表中間位置記錄的關鍵字和Ki比較，經(jīng)過一次比較，便可排除一半記錄，把可插入的區(qū)間縮小一半，故稱為折半。第21頁，共46頁，2023年，2月20日，星期六設置始指針low，指向有序表的第一個記錄，尾指針high，指向有序表的最后一個記錄，中間指針mid指向有序表中間位置的記錄。每次將待插入記錄的關鍵字與mid位置記錄的關鍵字進行比較，從而確定待插入記錄的插入位置。折半插入排序算法如下：

typedefintkeytype;voidInsert_halfSort(RecTypeR[],intn){/*對順序表R作折半插入排序*/inti,j,low,high,mid;for(i=2;i<=n;i++){R[0]=R[i];//保存待插入元素low=1;high=i-1;//設置初始區(qū)間

第22頁，共46頁，2023年，2月20日，星期六while(low<=high)//該循環(huán)語句完成確定插入位置{mid=(low+high)/2;if(R[0].key>R[mid].key)low=mid+1;插入位置在后半部分中elsehigh=mid-1;//插入位置在前半部分中}for(j=i-1;j>=high+1;--j)//high+1為插入位置R[j+1]=R[j];//后移元素，空出插入位置R[high+1]=R[0];//將元素插入}}第23頁，共46頁，2023年，2月20日，星期六【例10-2】待排序記錄的關鍵字為：28，13，72，85，39，41，6，20，在前7個記錄都已排好序的基礎上，采用折半插入第8個記錄的比較過程如圖10-2所示。

第24頁，共46頁，2023年，2月20日，星期六第25頁，共46頁，2023年，2月20日，星期六

折半插入排序僅減少了關鍵字間的比較次數(shù)，但記錄的移動次數(shù)不變。因此折半插入排序的時間復雜度仍為O(n2)。折半插入排序的空間復雜度與直接插入排序相同。折半插入排序也是一個穩(wěn)定的排序方法。

第26頁，共46頁，2023年，2月20日，星期六2.2路插入排序2路插入排序是在折半插入排序的基礎上再改進，其目的是減少排序過程中移動記錄的次數(shù)，但為此需要n個記錄的輔助空間。具體做法如下：設一個和L.r同類型的數(shù)組d，然后從L.r中第2個記錄起依次插入到d[1]之前和之后的有序序列中。先將待插入記錄的關鍵字和d[1]的關鍵字相比較，若L.r[i].key<d[1].key，則將L.r[i]插入到d[1]之前的有序表中。反之，將L.r[i]插入到d[1]之后的有序表中。在實現(xiàn)算法時，可將d看成一個循環(huán)向量，并設兩個指針first和final分別指示排序過程中得到的有序序列中的第一個記錄和最后一個記錄在d中的位置。第27頁，共46頁，2023年，2月20日，星期六第28頁，共46頁，2023年，2月20日，星期六第29頁，共46頁，2023年，2月20日，星期六第30頁，共46頁，2023年，2月20日，星期六2-路插入排序只能減少移動記錄的次數(shù)，而不能絕對避免移動記錄。當L.r[1]的待排序記錄中關鍵字最小或最大的記錄時，2-路插入排序就完全失去它的優(yōu)越性。因此，若希望在排序過程中不移動記錄，只有改變存儲結構，進行表插入排序3.表插入排序#defineSIZE100//靜態(tài)鏈表容量Typedefstruct{RcdTyperc;//記錄項intnext;//指針項}SLNode;//表結點類型第31頁，共46頁，2023年，2月20日，星期六typedefstruct{SLNoder[SIZE];//0號單元為表頭結點intlength;//鏈表當前長度；}SLinkListType;//靜態(tài)鏈表類型設數(shù)組下標為“0”的分量為表頭結點，并令表頭結點記錄的關鍵字區(qū)最大整數(shù)MAXINT。表插入排序的過程描述如下：首先將靜態(tài)鏈表中數(shù)組下標為“1”的分量（結點）和表頭結點構成一個循環(huán)鏈表，然后依次將下標為“2”至“n”的分量（結點）按記錄關鍵字非遞減有序插入到循環(huán)鏈表中第32頁，共46頁，2023年，2月20日，星期六第33頁，共46頁，2023年，2月20日，星期六第34頁，共46頁，2023年，2月20日，星期六第35頁，共46頁，2023年，2月20日，星期六第36頁，共46頁，2023年，2月20日，星期六表插入排序的基本操作仍為將一個記錄插入到已經(jīng)排好序的有序表中，和直接插入排序相比，不同之處僅是以修改2n次指針代替移動記錄，排序過程中所需進行的關鍵字之間的比較次數(shù)相同。因此，表插入排序的時間復雜度仍為O(n2)。表插入排序的結果只是求得一個有序表，則只能進行對它順序查找，不能進行隨機查找，為了實現(xiàn)有序表的折半查找，尚需對記錄進行重新排列。第37頁，共46頁，2023年，2月20日，星期六10.2.3希爾排序

希爾排序（shell’ssort）又稱縮小增量排序(DiminishingIncrementSort)。它是希爾（D.L.Shell）于1959年提出的插入排序的改進算法。如前所述，直接插入排序算法的時間性能取決于數(shù)據(jù)的初始特性，一般情況下，它的時間復雜度為O(n2)。但是當待排序列為正序或基本有序時，時間復雜度則為O(n)。因此，若能在一次排序前將排序序列調(diào)整為基本有序，則排序的效率就會大大提高。正是基于這樣的考慮，希爾提出了改進的插入排序方法。希爾排序的基本思想是：先將整個待排記錄序列分割成若干小組（子序列），分別在組內(nèi)進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。希爾排序的具體步驟如下：

第38頁，共46頁，2023年，2月20日，星期六（1）首先取一個整數(shù)d1<n，稱之為增量，將待排序的記錄分成d1個組，凡是距離為d1倍數(shù)的記錄都放在同一個組，在各組內(nèi)進行直接插入排序，這樣的一次分組和排序過程稱為一趟希爾排序。【例10-3】設有一個待排序的序列有10個記錄，它們的關鍵字分別為58，46，72，95，84，25，37，58，63，12，用希爾排序法進行排序。【解】圖10-3給出了希爾排序的整個過程，用同一連線上的關鍵字表示其所屬的記錄在同一組。為區(qū)別具有相同關鍵字58的不同記錄，用下劃線標記后一個記錄的關鍵字。（2）再設置另一個新的增量d2<d1，采用與上述相同的方法繼續(xù)進行分組和排序過程。（3）繼續(xù)取di+1<di，重復步驟(2)，直到增量d=1，即所有記錄都放在同一個組中。第39頁，共46頁，2023年，2月20日，星期六d1=5;(58,25);(46,37);(72,58);(95,63);(84,12);(25,58);(37,46);(58,72,);(63,95);(12,84);按照遞增的順序得到：第40頁，共46頁，2023年，2月20日，星期六d2=3;{25，63，46，84},{37，12，72},{58，58，95}按照遞增的順序得到：{25，46，63，84},{12，37，72},{58，58，95}第41頁，共46頁，2023年，2月20日，星期六d3=1;{12，25，37，46，58，58，63，72，84，95}按照遞增的順序得到：{25，12，58，46，37，58，63，72，95，84}第42頁，共46頁，2023年，2月20日，星期六第一趟排序時，取d1=5，整個序列被劃分成5組，分別為{58，25}，{46，37}，{72，58}，{95，63}，{84，12}。對各組內(nèi)的記錄進行直接插入排序，得到第一趟排序結果如圖10-3(a)所示。第二趟排序時，取d2=3，將第一趟排序的結果分成3組，分別為{25，63，46，84},{37，12，72},{58，58，95}。再對各組內(nèi)記錄進行直接插入排序，得到第二趟排序結果如圖10-3(b)所示。25125846375863729584第三趟排序時，取d3=1，所有的數(shù)據(jù)記錄分成1組{25，12，58，46，37，58，63，72，95，84}，此時序列基本“有序”，對其進行直接插入排序，最后得到希爾排序的結果如圖10-3(c)所示。1225374