計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第4講(第三章)

1信息科學(xué)與工程學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)二O一O年十月2查找順序查找對(duì)分查找分塊查找哈希查找O(n)O(log2n)O(log2(m+1)+n/m)O(1)3第3章查找與排序技術(shù)3.1基本的查找技術(shù)

順序查找（順序搜索）：一般是指在線性表中查找指定的元素

基本思想：從第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（查找成功），否則查找失敗

對(duì)于比較大的線性表，順序查找方法的效率很低。但以下兩種情況只能采用順序查找方式（1）若線性表為無序表（表中的排列是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能采用順序查找（2）即使是有序表，若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找4第3章查找與排序技術(shù)

有序表的對(duì)分查找：只適用于順序存儲(chǔ)的有序表（元素按值非遞減排列）

對(duì)分查找基本方法（設(shè)有序表的長度為n，被查元素為x）（1）將x與線性表的中間項(xiàng)進(jìn)行比較，若相等，則查到，結(jié)束（2）若小于中間項(xiàng)的值，則在中間項(xiàng)以前部分以相同方式進(jìn)行查找（3）若大于中間項(xiàng)的值，則在中間項(xiàng)以后部分以相同方式進(jìn)行查找（4）上述過程一直持續(xù)到查找成功或子表長度為0為止5舉例：在下列數(shù)據(jù)中查找元素26：010205091113161921262731lowhighmiddlelowhighmiddlelowmiddlehigh第一次第二次第三次對(duì)分法查找優(yōu)點(diǎn):平均檢索長度小，為log2nhigh第四次第3章查找與排序技術(shù)6第3章查找與排序技術(shù)

分塊查找（索引順序查找）：是順序查找的一種改進(jìn)方法，用于在分塊有序表中進(jìn)行查找分塊有序表：指將長度為n的線性表分成m個(gè)子表，各子表中的長度可以相等也可以不等，但要求最后一個(gè)子表中的每個(gè)元素都大于前一個(gè)子表中的所有元素

分塊有序表的結(jié)構(gòu)（1）線性表本身采用順序存儲(chǔ)結(jié)構(gòu)（2）再建一個(gè)索引表。在索引表中，對(duì)線性表的每個(gè)子表建立一個(gè)索引結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包括兩個(gè)域：7第3章查找與排序技術(shù)

結(jié)點(diǎn)的兩個(gè)域（1）數(shù)據(jù)域：用于存放對(duì)應(yīng)子表中的最大元素值（2）指針域：用于指示對(duì)應(yīng)子表第一個(gè)元素在整個(gè)線性表中的序號(hào)圖3.1是一個(gè)長度n=18的線性表分為m=3個(gè)子表的分塊有序表示意圖圖3.1分塊有序表例

查找過程（1）首先查找索引表，以確定被查元素所在的子表（2）然后在相應(yīng)的子表中用順序查找法進(jìn)行具體的查找83.2哈希（Hash）表技術(shù)

Hash表技術(shù)是另外一類查找技術(shù)。其基本思想：對(duì)被查元素的關(guān)鍵字做某種運(yùn)算后直接確定所要查找項(xiàng)目在表中的位置

直接查找技術(shù)設(shè)表的長度為n。若存在一個(gè)函數(shù)i=i(k)（關(guān)鍵字k的映象函數(shù)），對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足以下條件：（1）1≤i≤n（i為表項(xiàng)序號(hào)）（2）對(duì)于任意的元素關(guān)鍵字k1≠k2，恒存在i(k1)≠i(k2)則稱此表為直接查找表3.2.1哈希表的基本概念直接查找表中各元素的關(guān)鍵字k與表項(xiàng)序號(hào)i之間存在一一對(duì)應(yīng)關(guān)系9假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46，給定哈希函數(shù)：H(k)=k%13， 存貯區(qū)的內(nèi)存地址從0到15，則可得關(guān)鍵字哈希地址：

H（18）=18%13=5H（75）=75%13=10H（60）=60%13=8H（43）=43%13=4H（54）=54%13=2H（90）=90%13=12H（46）=46%13=7

第3章查找與排序技術(shù)10第3章查找與排序技術(shù)

對(duì)直接查找表的操作主要有以下兩種（1）直接查找表的填入：將關(guān)鍵字為k的元素填入到直接查找表計(jì)算關(guān)鍵字k的映象函數(shù)i=i(k)

將關(guān)鍵字k及有關(guān)元素信息填入到表的第i項(xiàng)

（2）直接查找表的取出計(jì)算關(guān)鍵字k的映象函數(shù)i=i(k)

檢查表中的第i項(xiàng)：若i項(xiàng)為空，表明表中無關(guān)鍵字為k的元素；否則取出第i項(xiàng)中的元素11第3章查找與排序技術(shù)

Hash表

Hash表技術(shù)是直接查找技術(shù)的推廣，其主要目標(biāo)是提高查找效率在直接查找技術(shù)中，不允許元素的沖突存在（即不同的關(guān)鍵字其映象函數(shù)值也不同---前述條件（2））實(shí)際應(yīng)用條件（2）很難滿足，對(duì)不同的關(guān)鍵字k1≠k2有i(k1)=i(k2),即發(fā)生了元素沖突（兩個(gè)不同的元素徐存儲(chǔ)在同一個(gè)存儲(chǔ)單元內(nèi)）

例3.2將關(guān)鍵字序列（09，31，26，19，01，13，02，11,27，16，05，21）依次填入長度n=12的表中。映象函數(shù)為i=INT(k/3)+1當(dāng)有元素發(fā)生沖突時(shí)無法直接進(jìn)行查詢，為此，引入Hash表

12第3章查找與排序技術(shù)

Hash表的定義

設(shè)表的長度為n。若存在函數(shù)i=i(k)，對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足1≤i≤n，則稱此表為Hash表。其中函數(shù)i=i(k)稱為關(guān)鍵字k的Hash碼

Hash表中允許幾個(gè)不同的關(guān)鍵字Hash碼相同（即允許沖突存在）如果Hash表中沒有元素的沖突存在，則Hash表成為直接查找表Hash表技術(shù)的關(guān)鍵是處理表中元素沖突的次數(shù)（1）構(gòu)造合適的Hash碼，減少元素沖突的次數(shù)（2）發(fā)生沖突時(shí)進(jìn)行適當(dāng)?shù)奶幚?33.哈希存貯中的沖突處理Hash表技術(shù)關(guān)鍵是要處理好表中元素沖突問題。主要包括3方面的工作：要選擇一個(gè)合適的裝填因子α。裝填因子：是指散列表中己存入的元素個(gè)數(shù)n與散列表的大小m的比值，即α=n/m。當(dāng)α越小時(shí)，發(fā)生沖突的可能性越小，α越大（最大為1）時(shí)，發(fā)生沖突的可能性就越大。但是，為了減少?zèng)_突的發(fā)生，不能將α變得太小，這樣將會(huì)造成大量存貯空間的浪費(fèi)，因此必須兼顧存儲(chǔ)空間和沖突兩個(gè)方面。構(gòu)造合適的哈希函數(shù)。當(dāng)沖突發(fā)生時(shí)，要有適當(dāng)?shù)慕鉀Q沖突的方法。14第3章查找與排序技術(shù)

Hash碼的構(gòu)造實(shí)際設(shè)計(jì)Hash碼時(shí)，要考慮以下兩個(gè)方面的因素（1）使各關(guān)鍵字盡可能均勻分布在如果Hash表中（2）Hash碼的計(jì)算要盡量簡單

幾種簡單的Hash碼構(gòu)造方法（1）截段法：指選取與關(guān)鍵字對(duì)應(yīng)的數(shù)字串中的一段（一般選取低位數(shù)）作為該關(guān)鍵字的Hash碼。該方法中，對(duì)數(shù)字串所截取的位數(shù)取決于Hash表的長度n，一般截取的位數(shù)為log2n（2）分段疊加法：該方法是將關(guān)鍵字的編碼串分割成若干段，然后把它們疊加后再進(jìn)行截段15第3章查找與排序技術(shù)

幾種簡單的Hash碼構(gòu)造方法（3）除法：該方法是將關(guān)鍵字的編碼處以表的長度，最后所得的余數(shù)作為Hash碼。即取Hash碼為i=mod(k,n)其中，k為關(guān)鍵字，n為Hash表的長度,mod為模余運(yùn)算符（4）乘法：該方法是將關(guān)鍵字的編碼與一個(gè)常數(shù)φ相乘后，再處以表的長度n，取其余數(shù)作為Hash碼，即i=mod(k*φ,n)

或者將關(guān)鍵字編碼與φ相乘后，取乘積低位段中的若干二進(jìn)制位（進(jìn)行截段）作為Hash碼16(5)直接定址法可表示為H（k）=a*k+b，其中a、b均為常數(shù)。這種方法計(jì)算特別簡單，并且不會(huì)發(fā)生沖突，但當(dāng)關(guān)鍵字分布不連續(xù)時(shí)，會(huì)出現(xiàn)很多空閑單元，將造成大量存貯單元的浪費(fèi)。第3章查找與排序技術(shù)17第3章查找與排序技術(shù)3.2.2幾種常用的哈希表

線性哈希表：是一種最簡單的Hash表

設(shè)線性Hash表的長度為n，對(duì)現(xiàn)行Hash表的查找過程如下（1）線性Hash表的填入。將關(guān)鍵字k及其相關(guān)信息填入線性Hash表的步驟：計(jì)算關(guān)鍵字k的Hash碼i=i(k)檢查表中的第i項(xiàng)內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及相關(guān)信息填入該項(xiàng)；若不空，則令i=mod(i+1,n)，轉(zhuǎn)繼續(xù)檢查。只要Hash表沒有填滿，最終總能找到一個(gè)空項(xiàng)18第3章查找與排序技術(shù)

線性哈希表

設(shè)線性Hash表的長度為n，對(duì)現(xiàn)行Hash表的查找過程如下

（2）線性Hash表的取出。在Hash表中取出關(guān)鍵字k的元素的步驟：計(jì)算關(guān)鍵字k的Hash碼i=i(k)檢查表中的第i項(xiàng)內(nèi)容：若第i項(xiàng)關(guān)鍵字k，則取出該元素；若第i項(xiàng)為空，則表示在Hash表中沒有該關(guān)鍵字的信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則令i=mod(i+1,n)，轉(zhuǎn)繼續(xù)檢查。只要Hash表沒有填滿，最終總能找到一個(gè)空項(xiàng)線性Hash表的這種處理沖突的方法稱為開放法19第3章查找與排序技術(shù)

線性哈希表

例3.3將關(guān)鍵字序列（09，31，26，19，01，13，02，11，27，16，05，21）依次填入長度為n=12的線性Hash表。設(shè)Hash碼為i=INT(k/3)+120第3章查找與排序技術(shù)

線性哈希表:其優(yōu)點(diǎn)是簡單，但有以下兩個(gè)缺點(diǎn)（1）在填入過程中發(fā)生沖突時(shí)，首先考慮的是下一項(xiàng)，因此當(dāng)沖突較多時(shí)，在線性Hash表中就產(chǎn)生“堆聚”現(xiàn)象（2）在線性Hash表的填入過程中，處理沖突時(shí)會(huì)產(chǎn)生新的沖突

在線性Hash表中，查找一個(gè)關(guān)鍵字的平均查找次數(shù)為其中，稱為Hash表的填滿率（也稱裝填因子）：n為Hash表的長度，m為Hash表中實(shí)際存在的關(guān)鍵字個(gè)數(shù)

特別需要注意的是：當(dāng)（表已填滿）時(shí)，其平均查找次數(shù)E為無窮，因此，線性Hash表不應(yīng)被填滿，否則會(huì)出現(xiàn)無窮循環(huán)21第3章查找與排序技術(shù)

隨機(jī)哈希表:其與線性Hash表的不同在于：發(fā)生元素沖突時(shí)，表項(xiàng)序號(hào)i的改變不是采用加1取模的方法，而是用某種偽隨機(jī)數(shù)來改變（1）隨機(jī)Hash表的填入。將關(guān)鍵字k及其相關(guān)信息填入隨機(jī)Hash表的步驟：計(jì)算關(guān)鍵字k的Hash碼i0=i(k)，且令i=i0偽隨機(jī)數(shù)序列初始化，令j=1（將取隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）③檢查表中的第i項(xiàng)內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及相關(guān)信息填入該項(xiàng)；若不空，則令i=mod(i0+RN(j),n)，并令j=j+1,轉(zhuǎn)③繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)22第3章查找與排序技術(shù)

例3.4將關(guān)鍵字序列（09，31，26，19，01，13，02，11，27，16，05，21）依次填入長度為n=24=16的隨機(jī)Hash表。設(shè)Hash碼為i=INT(k/3)+1。偽隨機(jī)數(shù)序列為：1，6，15，12，13，2，11，8，9，14，7，4，5，10，3，023第3章查找與排序技術(shù)（2）隨機(jī)Hash表的取出。將關(guān)鍵字k及其相關(guān)信息填入隨機(jī)Hash表的步驟：①計(jì)算關(guān)鍵字k的Hash碼i0=i(k)，且令i=i0②

偽隨機(jī)數(shù)序列初始化，令j=1（將取隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）③檢查表中的第i項(xiàng)內(nèi)容：若第i項(xiàng)登記有關(guān)鍵字k，則取出該元素；若為空，表示在Hash表中沒有該關(guān)鍵字的信息；若不空，則令i=mod(i0+RN(j),n)，并令j=j+1,轉(zhuǎn)③繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)24第3章查找與排序技術(shù)

溢出哈希表:將沖突的元素安排在另外的空間，而不占用Hash表本身的空間，就不會(huì)產(chǎn)生沖突，這就是溢出哈希表，它包括哈希表和溢出表兩部分，二者的存儲(chǔ)結(jié)構(gòu)相同（1）溢出Hash表的填入。將關(guān)鍵字k及其相關(guān)信息填入隨機(jī)Hash表的步驟：①計(jì)算關(guān)鍵字k的Hash碼i=i(k)②檢查表中的第i項(xiàng)內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及相關(guān)信息填入該項(xiàng)；若不空，則將關(guān)鍵字k及有關(guān)信息依次填入溢出表的自由項(xiàng)25第3章查找與排序技術(shù)

例3.5將關(guān)鍵字序列（09，31，26，19，01，13，02，11，27，16，05，21）依次填入長度為n=12的線性Hash表。設(shè)Hash碼為i=INT(k/3)+126第3章查找與排序技術(shù)（2）溢出Hash表的取出。將關(guān)鍵字k及其相關(guān)信息填入隨機(jī)Hash表的步驟：①計(jì)算關(guān)鍵字k的Hash碼i=i(k)②

檢查表中的第i項(xiàng)內(nèi)容：若第i項(xiàng)登記有關(guān)鍵字k，則取出該元素；若為空，表示在Hash表中沒有該關(guān)鍵字的信息；若不空，且登記的不是關(guān)鍵字k，則轉(zhuǎn)入在溢出表中進(jìn)行順序查找27第3章查找與排序技術(shù)

拉鏈哈希表:分為外鏈哈希表和內(nèi)鏈哈希表。外鏈哈希表主要由Hash表和表外結(jié)點(diǎn)組成。在Hash表中登記的不是關(guān)鍵字k，而指示登記指針。所有的關(guān)鍵字及其有關(guān)信息分別登記在表外各節(jié)點(diǎn)中，并且每一個(gè)表外結(jié)點(diǎn)還含有一個(gè)指針域，用于鏈接Hash碼相同的各結(jié)點(diǎn)

指標(biāo)哈希表:包括指標(biāo)表和內(nèi)容表兩部分。在指標(biāo)Hash表中，所有的關(guān)鍵字k及相關(guān)信息被登記在內(nèi)容表中。指標(biāo)表指示對(duì)應(yīng)關(guān)鍵字信息在內(nèi)容表中的地址28拉鏈Hash表拉鏈法也稱鏈地址法，是把相互發(fā)生沖突的同義詞用一個(gè)單鏈表鏈接起來，若干組同義詞可以組成若干個(gè)單鏈表。是一種最常用又最有效的Hash表。拉鏈Hash表由Hash表和表外結(jié)點(diǎn)構(gòu)成。Hash表中登記指針，所有的關(guān)鍵字k及其有關(guān)信息登記在表外結(jié)點(diǎn)中。Hash表的第H項(xiàng)登記著Hash函數(shù)為H(k)的所有關(guān)鍵字的表外結(jié)點(diǎn)。

29拉鏈Hash表的舉例

Eg.關(guān)鍵字序列(09,31,26,19,01,13,02,11,27,16,05,21)

將上例的關(guān)鍵字序列填入n=12的拉鏈Hash表中，Hash函數(shù)為

H=INT(k/3)。30拉鏈Hash表的填入設(shè)數(shù)組A（1：n）為Hash表存儲(chǔ)空間，其初始為A(i)=0;則填入步驟：計(jì)算關(guān)鍵字k的Hash函數(shù)H=H(k);取得一個(gè)新結(jié)點(diǎn)p，并將k及相關(guān)信息填入結(jié)點(diǎn)p。將結(jié)點(diǎn)p鏈入以A(H)為頭指針的鏈表。

拉鏈Hash表的取出計(jì)算關(guān)鍵字k的Hash函數(shù)H=H(k);在H(k)為頭指針的鏈表中順序查找關(guān)鍵字為k的結(jié)點(diǎn)。若找到，則從結(jié)點(diǎn)中取出該元素。

拉鏈Hash表31排序排序——將一個(gè)無序序列整理成按值非遞減順序排列的有序序列。排序可以在不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。基本排序是在順序存儲(chǔ)的線性表中實(shí)現(xiàn)的；二叉排序樹利用二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)無序表的有序化。三種基本排序方法：交換排序（如冒泡排序和快速排序）；插入排序（如簡單插入排序和希爾排序）；選擇排序（如簡單選擇排序和堆排序）；32交換排序交換排序的基本思想：兩兩比較待排序記錄的關(guān)鍵值，并交換不滿足順序要求的偶對(duì)，直至全部滿足為止。交換排序的兩種形式冒泡排序快速排序333.3基本的排序技術(shù)3.3.1冒泡排序與快速排序冒泡排序通過相鄰數(shù)據(jù)元素之間的相互交換進(jìn)行排序的一種方法

通過對(duì)待排序序列從后向前（從下標(biāo)較大的元素開始），依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較小的元素逐漸從后部移向前部（從下標(biāo)較大的單元移向下標(biāo)較小的單元），就象水底下的氣泡一樣逐漸向上冒。

343.3基本的排序技術(shù)

冒泡排序的基本過程（1）從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中前面的大于后面的元素，則將它們互換（稱消去了一個(gè)逆序)，這樣不斷地將相鄰兩個(gè)元素中的大者往后移動(dòng)，最后將線性表中的最大者換到了表的最后

（2）然后，從后向前掃描剩下的線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中前面的小于后面的元素，則將它們互換（又消去了一個(gè)逆序)，這樣不斷地將相鄰兩個(gè)元素中的小者往前移動(dòng)，最后將剩下線性表中的最小者換到了表的前面最壞情況下的時(shí)間復(fù)雜度（工作量）為O(n(n-1)/2).例如，n=6，數(shù)組R的六個(gè)排序碼分別為：17，3，25，14，20，9。下面用圖9-3給出冒泡排序算法的執(zhí)行過程。

第四趟排序過程中，沒有進(jìn)行過交換記錄的操作，故判定該冒泡排序結(jié)束。

3.3基本的排序技術(shù)注意

冒泡排序適用與元素基本有序，且n比較小的時(shí)候，元素的排列情況對(duì)冒泡排序的效率影響很大。當(dāng)元素以正序排列時(shí)，整個(gè)過程只進(jìn)行一趟排序，經(jīng)過n-1次關(guān)鍵字比較后排序便宣告結(jié)束。當(dāng)元素以逆序排列時(shí)，整個(gè)過程要進(jìn)行n-1趟排序，經(jīng)過n·(n-1)/2次關(guān)鍵字的比較,時(shí)間復(fù)雜度為o(n^2)。

3.3基本的排序技術(shù)373.3基本的排序技術(shù)

快速排序基本思想

（1）從線性表中選擇一個(gè)元素（設(shè)為T），以T為分界線，將線性表分成前后兩個(gè)字表，且前面子表中的所有元素均大于T，后面子表中的所有元素均小于T。

（2）對(duì)分割后的各子表再按照上述原則進(jìn)行分割下去，直到所有的字表為空為止38

快速排序的提出冒泡排序只能在掃描過程中對(duì)相鄰兩個(gè)元素進(jìn)行比較，消除一個(gè)逆序。能否找到一種辦法，通過一次交換來消除線性表中的多個(gè)逆序，從而大大加快排序的速度。快速排序基本思想

從線性表中選取一個(gè)元素設(shè)為T。然后將線性表后面小于T的元素移到前面，而前面大于T的元素移動(dòng)到后面，這樣將線性表分成兩部分，即進(jìn)行了一次線性表的分割。對(duì)分割后的各子表再按上述原則進(jìn)行分割，一直到所有子表為空，即完成線性表的排序過程。最壞情況下的時(shí)間復(fù)雜度（工作量）為O(n(n-1)/2).3.3基本的排序技術(shù)39快速排序的算法實(shí)現(xiàn)實(shí)現(xiàn)步驟首先，在表的第一個(gè)、中間一個(gè)或最后一個(gè)元素中選取中間項(xiàng)賦予T，設(shè)為P(k),再將表中第一個(gè)元素移到P(k)位置。

設(shè)置兩個(gè)指針i和j分別指向表的起始與中止位置，反復(fù)操作以下兩步：(1)將j指針逐漸減小，并逐次比較P(j)與T，直到發(fā)現(xiàn)一個(gè)P(j)<T為止，將P(j)移到P(i)的位置上；(2)將i指針逐漸增大，并逐次比較P(i)與T，直到發(fā)現(xiàn)一個(gè)P(j)>T為止，將P(i)移到P(j)的位置上；上述操作交替進(jìn)行，直到指針i和j指向同一個(gè)位置(i=j)為止。3.3基本的排序技術(shù)例如，給定排序碼為：（46，55，13，42，94，05，17，70）。3.3基本的排序技術(shù)413.3基本的排序技術(shù)3.3.2簡單插入排序與希爾排序

簡單插入排序：是指將無序序列中的元素依次插入到已經(jīng)有序的線性表中在線性表中，只包含第1個(gè)元素的子表可以看成有序表。從第2個(gè)元素開始直到最后一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面已經(jīng)有序的子表中假設(shè)線性表中前j-1個(gè)元素已經(jīng)有序，現(xiàn)在要將線性表中第j個(gè)元素插入到前面的有序子表中，插入過程如下423.3基本的排序技術(shù)（1）首先將第j個(gè)元素放到一個(gè)變量T中（2）然后從有序子表的最后一個(gè)元素開始。往前逐個(gè)與T比較，將大于T的元素依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，此時(shí)將T插入到剛移動(dòng)出的空位置上最壞情況下的時(shí)間復(fù)雜度（工作量）為O(n(n-1)/2).433.3基本的排序技術(shù)3.3.2簡單插入排序與希爾排序

希爾排序：是屬于插入類排序，其基本思想是：將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序子序列的分割方法：將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序過程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn)行一次插入排序，排序就完成了增量序列一般取，其中n為待排序序列的長度443.3基本的排序技術(shù)（1）n=12（2）h=12/2k=6(k=1)（3）h=12/2k=3(k=2)（4）h=12/2k(k=log212)圖3.6希爾排序示意圖453.3基本的排序技術(shù)3.3.3簡單選擇排序與堆排序

簡單選擇排序基本思想：（1）掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；（2）然后對(duì)剩下的子表采用相同的辦法，直到子表空為止

圖3.7簡單選擇排序例最壞情況下的時(shí)間復(fù)雜度（工作量）為O(n(n-1)/2).46堆排序堆定義：

或

堆的表示一維數(shù)組表示完全二叉樹表示堆頂元素為n個(gè)元素中的最大項(xiàng)堆排序是一種選擇排序3.3基本的排序技術(shù)47只要將序列依次排成一棵完全二叉樹，所有結(jié)點(diǎn)的值都不大于（或不小于）其左右子樹結(jié)點(diǎn)的值，那么該序列就符合堆的定義。

堆舉例（91，85，53，36，47，30，24，12）91855336473024120123456791855336473024123.3基本的排序技術(shù)堆排序?qū)嶋H與一棵完全二叉樹有關(guān)。若將排序碼初始序列組成一棵完全二叉樹，則堆排序可以包含兩個(gè)階段:建立初始堆（使排序碼變成能符合堆的定義的完全二叉樹）利用堆進(jìn)行排序建立初始堆

將排序碼k1，k2，k3，…，kn表示成一棵完全二叉樹，然后從第n/2

個(gè)排序碼(即樹的最后一個(gè)非終端結(jié)點(diǎn))開始篩選，使由該結(jié)點(diǎn)作根結(jié)點(diǎn)組成的子二叉樹符合堆的定義，然后從第n/2-1個(gè)排序碼重復(fù)剛才操作，直到第一個(gè)排序碼止。這時(shí)候，該二叉樹符合堆的定義，初始堆已經(jīng)建立。3.3基本的排序技術(shù)3.3基本的排序技術(shù)50堆排序步驟首先，將無序序列以完全二叉樹表示；將給定的無序序列構(gòu)造堆；將堆頂元素與堆中最后一個(gè)元素交換，然后將最后一個(gè)元素從原堆結(jié)構(gòu)中刪去，再將前面元素構(gòu)成的二叉樹調(diào)整成堆。反復(fù)進(jìn)行第3步，直到堆空為止。最壞情況下的比較次數(shù)為O(nlog2n).3.3基本的排序技術(shù)3.3基本的排序技