數(shù)據(jù)結(jié)構(gòu)第講哈希表和插入排序

數(shù)據(jù)結(jié)構(gòu)第講哈希表和插入排序第一頁(yè)，共五十八頁(yè)，2022年，8月28日9.3.1什么是哈希表哈希表技術(shù)的主要目標(biāo)是提高查找效率。1.哈希函數(shù)：根據(jù)關(guān)鍵字直接計(jì)算出元素所在位置的函數(shù)。

例：設(shè)哈希函數(shù)為：H(K)=K/3+1，則構(gòu)造關(guān)鍵字序列為1、2、5、9、11、13、16、21、27的散列表（哈希表）為：序號(hào)12345678910H(K)15913162127211第二頁(yè)，共五十八頁(yè)，2022年，8月28日2.沖突兩個(gè)不同的關(guān)鍵字具有相同的存儲(chǔ)位置。序號(hào)12345678910H(K)15913162127211第三頁(yè)，共五十八頁(yè)，2022年，8月28日3.哈希表根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映象到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲(chǔ)位置，這種表便稱為哈希表，這一映象過(guò)程稱為哈希造表或散列，所得存儲(chǔ)位置稱為哈希地址或散列地址。第四頁(yè)，共五十八頁(yè)，2022年，8月28日在哈希存儲(chǔ)中，若發(fā)生沖突，則必須采取特殊的方法來(lái)解決沖突問(wèn)題，才能使哈希查找能順利進(jìn)行。雖然沖突不可避免，但發(fā)生沖突的可能性卻與三個(gè)方面因素有關(guān)。(1)裝填因子α；裝填因子是指哈希表中己存入的元素個(gè)數(shù)n與哈希表的大小m的比值，即α=n/m（α<=1）。α越小，發(fā)生沖突的可能性越小，反之，發(fā)生沖突的可能性就越大。但是，α太小又會(huì)造成大量存貯空間的浪費(fèi)，因此必須兼顧存儲(chǔ)空間和沖突兩個(gè)方面。(2)所構(gòu)造的哈希函數(shù);(3)解決沖突的方法。第五頁(yè)，共五十八頁(yè)，2022年，8月28日①構(gòu)造好的哈希函數(shù)，使沖突盡可能的少②設(shè)計(jì)有效的解決沖突的方法第六頁(yè)，共五十八頁(yè)，2022年，8月28日第9章查找9.1靜態(tài)查找表9.2動(dòng)態(tài)查找表9.3哈希表

9.3.1什么是哈希表9.3.2哈希函數(shù)的構(gòu)造方法9.3.3處理沖突的方法9.3.4哈希表的查找及其分析第七頁(yè)，共五十八頁(yè)，2022年，8月28日9.3.2哈希函數(shù)的構(gòu)造方法例：關(guān)鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：1.直接定址法取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，即（K）=K或H（K）=a*K+b（其中a、b為常數(shù)）。0123456789900800700500300100優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突。缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。

第八頁(yè)，共五十八頁(yè)，2022年，8月28日2.除后余數(shù)法取關(guān)鍵字被不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為哈希函數(shù)。即H（K）=Kmodp（p≤m）經(jīng)驗(yàn)得知：一般可選p為質(zhì)數(shù)或不包含小于20的質(zhì)因素的合數(shù)。3.平方取中法取關(guān)鍵字平方后的中間幾位為哈希函數(shù)。因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。例：2589的平方值為6702921，可以取中間的029為地址。

第九頁(yè)，共五十八頁(yè)，2022年，8月28日選用關(guān)鍵字的某幾位組合成哈希地址。選用原則應(yīng)當(dāng)是：各種符號(hào)在該位上出現(xiàn)的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如80個(gè)）關(guān)鍵碼，其樣式如下：討論：①

第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號(hào)：①②③④⑤⑥⑦②若哈希地址取兩位（因元素僅80個(gè)），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。4.數(shù)字分析法第十頁(yè)，共五十八頁(yè)，2022年，8月28日5.折疊法

是將關(guān)鍵字按要求的長(zhǎng)度分成位數(shù)相等的幾段，最后一段如不夠長(zhǎng)可以短些，然后把各段重疊在一起相加并去掉進(jìn)位，以所得的和作為地址。適用于：每一位上各符號(hào)出現(xiàn)概率大致相同的情況。

移位法：將各部分的最后一位對(duì)齊相加。

間界疊加法：從一端向另一端沿分割界來(lái)回折疊后，最后一位對(duì)齊相加。例：元素42751896,移位法：

427＋518＋96=1041間界疊加法：

42751896—>724+518+69=1311第十一頁(yè)，共五十八頁(yè)，2022年，8月28日6.隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即H(key)=random(key)，其中random為隨機(jī)函數(shù)。通常，當(dāng)關(guān)鍵字長(zhǎng)度不等時(shí)采用此法構(gòu)造哈希函數(shù)較恰當(dāng)。第十二頁(yè)，共五十八頁(yè)，2022年，8月28日實(shí)際工作中需視不同情況采用不同的哈希函數(shù)。通?？紤]的因素：(1)計(jì)算哈希函數(shù)所需時(shí)間(包括硬件指令的因素)；(2)關(guān)鍵字的長(zhǎng)度；(3)哈希表的大小；(4)關(guān)鍵字的分布情況；(5)記錄的查找頻率。第十三頁(yè)，共五十八頁(yè)，2022年，8月28日第9章查找9.1靜態(tài)查找表9.2動(dòng)態(tài)查找表9.3哈希表

9.3.1什么是哈希表

9.3.2哈希函數(shù)的構(gòu)造方法

9.3.3處理沖突的方法9.3.4哈希表的查找及其分析第十四頁(yè)，共五十八頁(yè)，2022年，8月28日9.3.3處理沖突的方法1.開(kāi)放地址法

開(kāi)放地址就是表中尚未被占用的地址，當(dāng)新插入的記錄所選地址已被占用時(shí)，即轉(zhuǎn)而尋找其它尚開(kāi)放的地址。（1）線性探測(cè)法設(shè)散列函數(shù)H（K）=Kmodm（m為表長(zhǎng)），若發(fā)生沖突，則沿著一個(gè)探查序列逐個(gè)探查，那么，第i次計(jì)算沖突的散列地址為：Hi=(H(K)+di)modm(di=1,2,…,m-1)第十五頁(yè)，共五十八頁(yè)，2022年，8月28日例關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長(zhǎng)為m=11；哈希函數(shù)為Hash(key)=keymod11；擬用線性探測(cè)法處理沖突。建哈希表：012345678910477291116922283第十六頁(yè)，共五十八頁(yè)，2022年，8月28日線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；線性探測(cè)法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)，大大降低了查找效率。可采用二次探測(cè)法或偽隨機(jī)探測(cè)法，以改善“堆積”問(wèn)題。

第十七頁(yè)，共五十八頁(yè)，2022年，8月28日1.開(kāi)放地址法（2）二次探測(cè)法二次探測(cè)法對(duì)應(yīng)的探查地址序列的計(jì)算公式為：Hi=(H(k)+di)modm其中di

=12,-12,22,-22,…,j2,-j2(j≤m/2)。第十八頁(yè)，共五十八頁(yè)，2022年，8月28日012345678910112234792167298若di＝偽隨機(jī)序列，就稱為偽隨機(jī)探測(cè)法例關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長(zhǎng)為m=11；哈希函數(shù)為Hash(key)=keymod11；擬用二次探測(cè)法處理沖突。建哈希表如下：Hi=(H(k)+di)modm其中di

=12,-12,22,-22,…,j2,-j2(j≤m/2)第十九頁(yè)，共五十八頁(yè)，2022年，8月28日2.鏈地址法優(yōu)點(diǎn)：插入、刪除方便。缺點(diǎn)：占用存儲(chǔ)空間多?；舅枷耄簩⒕哂邢嗤５刂返挠涗涙湷梢粋€(gè)單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表，然后用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來(lái)，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。第二十頁(yè)，共五十八頁(yè)，2022年，8月28日例：設(shè){47,7,29,11,16,92,22,8,3,50,37,89}的哈希函數(shù)為：Hash(key)=keymod11，用拉鏈法處理沖突，建表。

01234567891022118934737922971650810有沖突的元素可以插在表尾,也可以插在表頭。第二十一頁(yè)，共五十八頁(yè)，2022年，8月28日3.再哈希法Hi=RHi(key)RHi均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。不易產(chǎn)生“聚集”，但是增加了計(jì)算時(shí)間。

4.建立一個(gè)公共溢出區(qū)第二十二頁(yè)，共五十八頁(yè)，2022年，8月28日第9章查找9.1靜態(tài)查找表9.2動(dòng)態(tài)查找表9.3哈希表

9.3.1什么是哈希表

9.3.2哈希函數(shù)的構(gòu)造方法9.3.3處理沖突的方法

9.3.4哈希表的查找及其分析第二十三頁(yè)，共五十八頁(yè)，2022年，8月28日9.3.4哈希表的查找及其分析散列表的目的主要是用于快速查找。在建表時(shí)采用何種散列函數(shù)及何種解決沖突的辦法，在查找時(shí)，也采用同樣的散列函數(shù)及解決沖突的辦法。第二十四頁(yè)，共五十八頁(yè)，2022年，8月28日例：設(shè)有一組關(guān)鍵字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函數(shù)為：H（k）=kmod13。采用開(kāi)放地址的線性探測(cè)法解決沖突，試在0～18的散列地址空間中，對(duì)該關(guān)鍵字序列構(gòu)造哈希表。解：依題意m=19，得到線性探測(cè)法對(duì)應(yīng)的探查地址序列計(jì)算公式為：di=(H(k)+j)mod19;j=1,2,……,18其計(jì)算函數(shù)如下：

第二十五頁(yè)，共五十八頁(yè)，2022年，8月28日H(19)=19mod13=6H(01)=01mod13=1H(23)=23mod13=10H(14)=14mod13=1(沖突)H(14)=(1+1)mod19=2H(55)=55mod13=3H(20)=20mod13=7H(84)=84mod13=6

(沖突)H(84)=(6+1)mod19=7

(沖突)H(84)=(6+2)mod19=8H(27)=27mod13=1（沖突）H(27)=(1+1)mod19=2

(沖突)H(27)=(1+2)mod19=3

(沖突)H(27)=(1+3)mod19=4012345678910111213141516171819{19,01,23,14,55,20,84,27,68,11,10,77}0123145520842777101168……第二十六頁(yè)，共五十八頁(yè)，2022年，8月28日哈希查找的性能分析哈希查找按理論分析，它的時(shí)間復(fù)雜度應(yīng)為O(1)，它的平均查找長(zhǎng)度應(yīng)為ASL=1，但實(shí)際上由于沖突的存在，它的平均查找長(zhǎng)度將會(huì)比1大。下面將分析幾種方法的平均查找長(zhǎng)度。第二十七頁(yè)，共五十八頁(yè)，2022年，8月28日1.線性探查法的性能分析由于線性探查法解決沖突是線性地查找空閑位置的，平均查找長(zhǎng)度與表的大小m無(wú)關(guān)，只與所選取的哈希函數(shù)H及裝填因子α的值和該處理方法有關(guān)。這時(shí)的成功的平均查找長(zhǎng)度為：ASL=(1+1/(1-α))/2第二十八頁(yè)，共五十八頁(yè)，2022年，8月28日2.鏈地址法查找的性能分析由于鏈地址法查找就是在單鏈表上查找，查找單鏈表中第一個(gè)結(jié)點(diǎn)的次數(shù)為1，第二個(gè)結(jié)點(diǎn)次數(shù)為2，其余依次類推。平均查找長(zhǎng)度：ASL=1+α/2第二十九頁(yè)，共五十八頁(yè)，2022年，8月28日例：給定關(guān)鍵字序列{11，78，10，1，3，2，4，21}，試分別用順序查找、二分查找、二叉排序樹(shù)查找、平衡二叉樹(shù)查找、哈希查找(用線性探查法和拉鏈法)來(lái)實(shí)現(xiàn)查找，試畫(huà)出它們的對(duì)應(yīng)存儲(chǔ)形式(順序查找的順序表，二分查找的判定樹(shù)，二叉排序樹(shù)查找的二叉排序樹(shù)及平衡二叉樹(shù)查找的平衡二叉樹(shù)，兩種哈希查找的哈希表)，并求出每一種查找的成功平均查找長(zhǎng)度。設(shè)哈希函數(shù)為：H(k)=kmod11，哈希表表長(zhǎng)m=11。第三十頁(yè)，共五十八頁(yè)，2022年，8月28日順序查找的順序表（一維數(shù)組）由圖可得：順序查找的成功平均查找長(zhǎng)度為ASL=(1+2+3+4+5+6+7+8)/8=4.5第三十一頁(yè)，共五十八頁(yè)，2022年，8月28日二分查找的判定樹(shù)（中序序列為從小到大排列的有序序列）由圖可得：二分查找的成功平均查找長(zhǎng)度為ASL=(1+2*2+3*4+4)/8=2.625第三十二頁(yè)，共五十八頁(yè)，2022年，8月28日二叉排序樹(shù)（關(guān)鍵字順序已確定，該二叉排序樹(shù)應(yīng)唯一）如圖(a)所示，平衡二叉樹(shù)（關(guān)鍵字順序已確定，該平衡二叉樹(shù)也應(yīng)該是唯一的），如圖(b)所示。由圖(a)可得：二叉排序樹(shù)查找的成功平均查找長(zhǎng)度為ASL=(1+2*2+3*2+4+5*2)/9=3.125由圖(b)可得：平衡二叉樹(shù)的成功平均查找長(zhǎng)度為ASL=(1+2*2+3*3+4*2)/8=2.75

11

10

1

3

2

4

78

213

1

11

2

10

4

78

21

(a)二叉排序樹(shù)

(b)平衡二叉樹(shù)第三十三頁(yè)，共五十八頁(yè)，2022年，8月28日線性探查法解決沖突的哈希表如圖所示。由圖可得：線性探查法的成功平均查找長(zhǎng)度為ASL=（1+1+2+1+3+2+8+1）/8=2.375第三十四頁(yè)，共五十八頁(yè)，2022年，8月28日鏈地址法解決沖突的哈希表如圖所示。由圖可得：鏈地址法的成功平均查找長(zhǎng)度為ASL=(1*6+2*2)/8=1.25第三十五頁(yè)，共五十八頁(yè)，2022年，8月28日小結(jié)1.掌握查找的基本概念；2.熟練掌握靜態(tài)查找表的查找算法思想并靈活應(yīng)用；3.熟練掌握動(dòng)態(tài)查找表的特點(diǎn)以及二叉排序樹(shù)、平衡二叉樹(shù)的各種操作思想4.了解B-、B+樹(shù)的概念及插入和刪除操作；5.熟練掌握哈希表的基本概念、哈希函數(shù)的構(gòu)造方法和解決沖突的方法，并能計(jì)算平均查找長(zhǎng)度。第三十六頁(yè)，共五十八頁(yè)，2022年，8月28日第10章內(nèi)部排序10.1排序的基本概念10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較第三十七頁(yè)，共五十八頁(yè)，2022年，8月28日10.1排序的基本概念1.排序設(shè)含有n個(gè)記錄的文件｛R1，R2，…Rn｝，相應(yīng)的關(guān)鍵字為｛K1，K2，…Kn｝，需確定一種排列P(1),P(2)…P(n)使其相應(yīng)的關(guān)鍵字滿足遞增(或遞減)關(guān)系：KP(1)≤KP(2)≤…KP(n)或KP(1)≥KP(2)≥…KP(n)使上述文件成為一個(gè)按其關(guān)鍵字線性有序的文件｛RP(1)，RP(2)，…RP(n)｝，這種運(yùn)算就稱為排序。將數(shù)據(jù)元素的無(wú)序序列調(diào)整為有序序列的過(guò)程。第三十八頁(yè)，共五十八頁(yè)，2022年，8月28日2.排序算法的穩(wěn)定性

排序碼（Key）作為排序依據(jù)的記錄中的一個(gè)屬性。它可以是任何一種可比的有序數(shù)據(jù)類型，它可以是記錄的關(guān)鍵字，也可以是任何非關(guān)鍵字。如果待排序的序列中，存在多個(gè)具有相同排序碼的數(shù)據(jù)元素，若經(jīng)過(guò)排序這些數(shù)據(jù)元素的相對(duì)次序保持不變，則稱這種排序算法是穩(wěn)定的，若經(jīng)過(guò)排序，這些數(shù)據(jù)元素的相對(duì)次序發(fā)生了改變，則稱這種排序算法是不穩(wěn)定的。第三十九頁(yè)，共五十八頁(yè)，2022年，8月28日3.內(nèi)部排序與外部排序

內(nèi)部排序指當(dāng)文件的數(shù)據(jù)量不太大時(shí)，全部信息放內(nèi)存中處理的排序方法。

外部排序當(dāng)文件的數(shù)據(jù)量較大時(shí)，排序過(guò)程中需要在內(nèi)、外存之間不斷地進(jìn)行數(shù)據(jù)交換才能達(dá)到排序的目的，這種排序稱為外排序。第四十頁(yè)，共五十八頁(yè)，2022年，8月28日4.內(nèi)部排序的方法內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序長(zhǎng)度的過(guò)程。在排序的過(guò)程中，參與排序的記錄序列中存在兩個(gè)區(qū)域：有序區(qū)和無(wú)序區(qū)。使有序區(qū)中記錄的數(shù)目增加一個(gè)或幾個(gè)的操作稱為一趟排序。內(nèi)部排序的方法很多，每種方法都有各自的優(yōu)缺點(diǎn)，適合在不同的環(huán)境(如記錄的初始排列狀態(tài)等)下使用。第四十一頁(yè)，共五十八頁(yè)，2022年，8月28日排序簡(jiǎn)單排序方法，其時(shí)間復(fù)雜度為O(n2)先進(jìn)排序方法，其時(shí)間復(fù)雜度為O(nlogn)基數(shù)排序，其時(shí)間復(fù)雜度為O(d·n)按內(nèi)部排序過(guò)程中所需的工作量來(lái)區(qū)分：第四十二頁(yè)，共五十八頁(yè)，2022年，8月28日插入類（直插排序、二分排序、希爾排序）交換類（冒泡排序、快速排序）選擇類（直選排序、樹(shù)型排序、堆排序）歸并類（二路歸并排序、多路歸并排序）分配類（多關(guān)鍵字排序、基數(shù)排序）按排序過(guò)程中依據(jù)的原則分排序第四十三頁(yè)，共五十八頁(yè)，2022年，8月28日#defineMAXSIZE20//一個(gè)順序表的最大長(zhǎng)度typedefintKeyType;//定義關(guān)鍵字為整數(shù)類型Typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)InfoTypeotherinfo;//其他數(shù)據(jù)項(xiàng)}RedType;//記錄類型Typedefstruct{RedTyper[MAXSIZE+1];//r[0]用作哨兵單元intlength;//順序表長(zhǎng)度}SqList;//順序表類型第四十四頁(yè)，共五十八頁(yè)，2022年，8月28日第10章內(nèi)部排序10.1排序的基本概念10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較第四十五頁(yè)，共五十八頁(yè)，2022年，8月28日10.2插入排序直接插入排序折半插入排序2-路插入排序表插入排序希爾排序第四十六頁(yè)，共五十八頁(yè)，2022年，8月28日1）一趟直接插入排序的基本思想將記錄L.r[i]插入到有序子序列L.r[1..i-1]中，使記錄的有序序列從L.r[1..i-1]變?yōu)長(zhǎng).r[1..i]。完成這個(gè)“插入”分三步進(jìn)行：1．查找L.r[i]在有序子序列L.r

[1..i-1]中的插入位置j；2．將L.r

[j..i-1]中的記錄后移一個(gè)位置；3．將L.r

[i]復(fù)制到L.r

[j]的位置上。整個(gè)排序過(guò)程進(jìn)行n–1趟插入，即：先將序列中的第1個(gè)記錄著成一個(gè)有序的子序列，然后從第2個(gè)記錄起逐個(gè)插入，直至整個(gè)序列變成接關(guān)鍵字非遞減有序序列為止。1.直接插入排序第四十七頁(yè)，共五十八頁(yè)，2022年，8月28日待排元素序列：[53]2736156942第一次排序：(27)[2753]36156942第二次排序：(36)[273653]156942第三次排序：(53)[15273653]6942第四次排序：(69)[1527365369]42第五次排序:(42)[152736425369]

直接插入排序示例（插入操作要進(jìn)行n-1次）第四十八頁(yè)，共五十八頁(yè)，2022年，8月28日2）直接插入排序算法描述

voidInsertionSort(SqList&L){//對(duì)記錄序列R[1..L.length]作直接插入排序。for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//復(fù)制為監(jiān)視哨for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入到正確位置}}//InsertSort第四十九頁(yè)，共五十八頁(yè)，2022年，8月28日3）直接插入排序性能分析

實(shí)現(xiàn)排序的基本操作有：（1）“比較”關(guān)鍵字的大?。?）“移動(dòng)”記錄對(duì)于直接插入排序：最好情況“比較”次數(shù)：n-1；“移動(dòng)”次數(shù)：2(n-1)最壞的情況“比較”和“移動(dòng)”的次數(shù)均達(dá)到最大值，分別為：(n+2)(n-1)/2；(n+4)(n-1)/2由于待排記錄序列是隨機(jī)的，取上述二值的平均值。所以直接插入排序的時(shí)間復(fù)雜度為O(n2)。

直接插入排序是“穩(wěn)定的”：關(guān)鍵碼相同的兩個(gè)記錄，在整個(gè)排序過(guò)程中，不會(huì)通過(guò)比較而相互交換。第五十頁(yè)，共五十八頁(yè)，2022年，8月28日2.折半插入排序1）基本思想考慮到L.r[1..i-1]是按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“L.r[1…i-1]中查找L.r[i]的插入位置”如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。第五十一?yè)，共五十八頁(yè)，2022年，8月28日(high<low，查找結(jié)束，插入位置為low或high+1)(42>36)(42<53)折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。例：有6個(gè)記錄，前5個(gè)已排序的基礎(chǔ)上，對(duì)第6個(gè)記錄排序。[1527365369]42

[1527365369]42

[1527365369]42

[152736425369]highmidlowlowhighmid

highlow第五十二頁(yè)，共五十八頁(yè)，2022年，8月28日voidBinsertSort(SqList&L){inti,low,high,mid;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];

low=1;high=i-1;While(low<=high){mid=(low+high)/2;if(L.r[0].key<L.r[mid].key)high=mid-1;elselow=mid+1;}

for(j=i-1;j>=low;

j)L.r[j+1]=L.r[j];L.r[low]=L.r[0];}}2)折半插入排序算法第五十三頁(yè)，共五十八頁(yè)，2022年，8月28日3)折半插入排序性能分析折半插入排序