數(shù)據(jù)結(jié)構(gòu)第二十講

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

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

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

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

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

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

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

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

與許多算法一樣，對(duì)各種排序算法性能的評(píng)價(jià)主要從兩個(gè)方面來(lái)考慮，一是時(shí)間性能；二是空間性能。

1．

時(shí)間復(fù)雜度分析

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

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

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

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

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

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

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

，…，K1進(jìn)行比較，找出其應(yīng)該插入的位置，將該位置及其以后的記錄向后順移，插入記錄Ri，完成序列中第i個(gè)記錄的插入排序。當(dāng)完成序列中第n個(gè)記錄Rn的插入后，整個(gè)序列排序完畢。

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

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

第16頁(yè)，共46頁(yè)，2023年，2月20日，星期六【例10-1】假設(shè)有7個(gè)待排序的記錄，它們的關(guān)鍵字分別為23，4，15，8，19，24，15，用直接插入法進(jìn)行排序。【解】直接插入排序過(guò)程如圖10-1所示。方括號(hào)[]中為已排好序的記錄的關(guān)鍵字，有兩個(gè)記錄的關(guān)鍵字都為15，為表示區(qū)別，將后一個(gè)15加下劃線。

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

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

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

與Ki進(jìn)行比較（i/2

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

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

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

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

第22頁(yè)，共46頁(yè)，2023年，2月20日，星期六while(low<=high)//該循環(huán)語(yǔ)句完成確定插入位置{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頁(yè)，共46頁(yè)，2023年，2月20日，星期六【例10-2】待排序記錄的關(guān)鍵字為：28，13，72，85，39，41，6，20，在前7個(gè)記錄都已排好序的基礎(chǔ)上，采用折半插入第8個(gè)記錄的比較過(guò)程如圖10-2所示。

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

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

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

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

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