第3章查找與排序技術(shù)大字黑體

第3章查找與排序技術(shù)3.1基本的查找技術(shù)3.2哈希表技術(shù)3.3基本的排序技術(shù)3.4二叉排序樹及其查找3.5多層索引樹及其查找3.6拓?fù)浞诸?3.1基本的查找技術(shù)3.1.1順序查找3.1.2有序表的對分查找3.1.3分塊查找2

所謂查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。查找的效率將直接影響到數(shù)據(jù)處理的效率。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。33.1.1順序查找順序查找又稱順序搜索。其基本方法是：從線性表的第一個元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示查找成功；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素，即查找失敗。4算法3.1：在順序表中順序查找元素X的下標(biāo)K輸入：線性表長度n

線性表的存儲空間V；被查找的元素x。輸出：元素x在線性表中的序號k。如果表中不存在元素x，則k＝－1。5算法：順序表的順序查找PROCEDURESERCH(V，n，x，k)k＝1

WHILE(k≤n)and(V(k)≠x)DOk＝k＋1IF(k＝n＋1)THENk＝－1RETURN6C語言描述：順序表的順序查找/*函數(shù)返回被查找元素x在線性表中的序號，如果在線性表中不存在元素值x，則返回－1*/int

serch(ETv[]，intn，ETx){intk＝0；

while((k＜n)&&(v[k]≠x))k＝k＋1；

if(k＝＝n)k＝－1；

return(k)；}7算法3.2：鏈表的順序查找輸入：線性鏈表頭指針HEAD

存儲空間V、NEXT；被查找的元素x。輸出：元素x的結(jié)點(diǎn)在線性鏈表中的存儲序號k。如果鏈表中不存在元素x

的結(jié)點(diǎn)，則k＝－1。

8鏈表的順序查找PROCEDURELSERCH(V，NEXT，HEAD，x，k)k＝HEAD

WHILE(k≠0)and(V(k)≠x)DOk＝NEXT(k)IF(k＝0)THENk＝－1RETURN9C描述：鏈表的順序查找/*函數(shù)返回被查找元素x所在結(jié)點(diǎn)的存儲地址，如果在線性鏈表中不存在元素值為x的結(jié)點(diǎn)，則返回NULL*/structnode{ETd；

structnode*next；}；structnode*lserch(head，x)structnode*head；ETx；10C描述：鏈表的順序查找{structnodek；

k＝head；

while((k≠NULL)&&(k－>d≠x))k＝k－>next；

return(k)；}11對順序查找法的分析在平均情況下，在線性表中順序查找一個元素，大約要與線性表中一半的元素進(jìn)行比較。對于大的線性表來說，順序搜索的效率是很低的。但在下列兩種情況下，只能采用順序查找：12必須采用順序查找的兩種情況：(1)如果線性表為無序表（即表中元素的排列是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序查找。(2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。133.1.2有序表的對分查找對分查找只適用于順序存儲的有序表。本書所說的有序表均指元素按值非遞減排列的線性表。非遞減排列即從小到大排列，但允許相鄰元素相等。14對分查找算法：設(shè)有序表長度為n，被查元素為x。將X與線性表的中間項(xiàng)進(jìn)行比較，分為三種情況：（1）若x等于中間項(xiàng)的值，則說明查到，查找結(jié)束；（2）若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；15對分查找算法：（3）若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。這個過程一直進(jìn)行到查找成功或子表長度為0(說明線性表中沒有這個元素)為止。

16對分查找法的效率對分查找的效率比順序查找高得多?？梢宰C明，對于長度為n的有序線性表，在最壞情況下，對分查找只需比較log2n次，而順序查找需比較n次。17算法3.3有序線性表在順序存儲結(jié)構(gòu)下的對分查找輸入：有序線性表長度n

線性表的存儲空間V；被查找的元素x。輸出：被查找元素x在有序線性表中的序號k。如果在線性表中不存在元素x，則輸出k＝－1。18算法3.3有序線性表在順序存儲結(jié)構(gòu)下的對分查找PROCEDUREBSERCH(V，n，x，k)i＝1；j＝nWHILE(i＜＝j(luò))DO{k＝(i＋j)/2IF(V(k)＝x)THENRETURN

IF(V(k)＞x)THENj＝k－1；

ELSEi＝k＋1；}IF(i＞j)THENk＝－1RETURN19算法3.3的C語言描述：

/*函數(shù)返回被查找元素x在線性表中的序號,如果在線性表中不存在元素值x，則返回－1*/20算法3.3的C語言描述：int

bserch(ETv[]，n，ETx){inti，j，k；

i＝1；j＝n；

while(i＜＝j(luò)){

k＝(i＋j)/2；

if(v[k－1]＝＝x)return(k－1)；

if(v[k－1]＞x)j＝k－1；

elsei＝k＋1；}return(－1)；}21m=（L+h）/2；if(key

>a[m].key)L=m+1；elseif(key<

a[m].key)h=m–1；elsefinditem,break;mLh223.1.3分塊查找分塊查找又稱索引順序查找。它是一種順序查找的改進(jìn)方法，用于在分塊有序表中進(jìn)行查找。23分塊有序表將長度為n線性表分成m個子表（即分塊），各子表的長度可以相等，也可以互相不等，但要求后一個子表中的每一個元素均大于前一個子表中的所有元素（有序）。24分塊有序表的結(jié)構(gòu)

分塊有序表的結(jié)構(gòu)可分為兩部分：(1)線性表本身,采用順序存儲結(jié)構(gòu)。(2)索引表。在索引表中，為線性表的每個子表建立一個索引結(jié)點(diǎn)，索引結(jié)點(diǎn)包括兩個域：一是數(shù)據(jù)域，用于存放對應(yīng)子表中的最大元素值；二是指針域，指示對應(yīng)子表的元素在整個線性表中的第一個存儲位置。25

下圖是將一個長度為n＝18的線性表,分成m＝3個子表的

分塊有序表示意圖。26分塊有序表的查找過程：分塊有序表的查找過程可分為兩步進(jìn)行：(1)首先查找索引表，以便確定被查元素所在的子表。由于索引表數(shù)據(jù)域中的數(shù)據(jù)是有序的，因此可以采用對分查找。(2)然后在相應(yīng)的子表中用順序查找法進(jìn)行具體的查找。27算法分析：分塊查找法在索引表中使用對分查找法，在最壞情況下需要查找log2(m＋1)次。在子表中用順序查找法，在最壞情況下需要查找n/m（假設(shè)各子表長度相等）次；而在平均情況下需要查找n/(2m)次。28算法分析：分塊查找法（續(xù)）因此，分塊查找的工作量為：在最壞情況下需要查找log2(m＋1)＋n/m次，平均情況下大約需要查找log2(m＋1)＋n/(2m)次。29分析：分塊查找法（續(xù)）當(dāng)m＝1時(shí)，線性表L為一般的無序表，分塊查找即為順序查找。當(dāng)m＝n時(shí)，線性表L即為有序表，分塊查找即為對分查找分塊查找的效率介于對分查找和順序查找之間。303.2哈希表技術(shù)3.2.1Hash表的基本概念3.2.2幾種常用的Hash表313.2.1Hash表的基本概念前述順序查找、二分查找、分塊查找等查找方法，都是通過比較達(dá)到查找的目的。本節(jié)介紹的哈希（Hash）表技術(shù)的基本思想是通過對被查元素的關(guān)鍵字做某種運(yùn)算后直接確定所要查找的項(xiàng)目在表中的位置。在介紹hash表之前，先了解“直接查找表”。321.直接查找技術(shù)設(shè)表的長度為n。如果存在一個函數(shù)i＝i(k)，對于表中的任意一個元素的關(guān)鍵字k，滿足以下條件：

(1)1≤i≤n；

(2)對于任意的元素關(guān)鍵字

k1≠k2，恒存在i(k1)≠i(k2)。

則稱此表為直接查找表。其中函數(shù)i＝i(k)稱為關(guān)鍵字k的映象函數(shù)。33(1)直接查找表的填入

對直接查找表的數(shù)據(jù)操作主要有兩種：填入和取出。要將關(guān)鍵字為k的元素填入到直接查找表，只需做以下兩步：

1)計(jì)算關(guān)鍵字k的映象函數(shù)i＝i(k)；

2)將關(guān)鍵字k及有關(guān)元素信息填入到表的第i項(xiàng)。34(2)直接查找表的取出要在直接查找表中取出關(guān)鍵字k的元素，也只需做以下兩步：

1)計(jì)算關(guān)鍵字k的映象函數(shù)i＝i(k)；

2)檢查表中第i項(xiàng)：

若第i項(xiàng)為空，則說明表中沒有關(guān)鍵字為k的元素；

否則取出第i項(xiàng)中的元素即可。

35元素存儲位置的沖突：在直接查找表中，提出了要求：若k1≠k2，則恒存在i(k1)≠i(k2)

。即不允許元素的存儲位置發(fā)生沖突。

但這一要求往往很難滿足。36沖突根源：從較大的關(guān)鍵字空間映射到較小的地址空間元素沖突的例子：例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)

依次填入長度為n＝12的表中。

映象函數(shù)為i＝INT(k/3)＋1。372.Hash表

Hash表技術(shù)是直接查找技術(shù)的推廣，其主要目標(biāo)是提高查找效率。在Hash表中允許沖突存在。Hash表技術(shù)的關(guān)鍵就是要處理好表中元素的沖突問題。38Hash表的定義：設(shè)表的長度為n。如果存在一個函數(shù)i＝i(k)，對于表中的任意一個元素的關(guān)鍵字k，滿足1≤i≤n，則稱此表為Hash表。其中映像函數(shù)i＝i(k)稱為關(guān)鍵字k的Hash碼。39Hash表技術(shù)的關(guān)鍵：

Hash表技術(shù)的關(guān)鍵就是要處理好表中元素的沖突問題，包括兩方面的工作：(1)構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次數(shù)。即Hash碼的均勻性要比較好。(2)當(dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶幚怼?03.Hash碼的構(gòu)造在設(shè)計(jì)Hash碼時(shí)，要考慮兩個方面的因素：(1)使各關(guān)鍵字盡可能均勻地分布在Hash表中，即Hash碼的均勻性要好，以便減少沖突發(fā)生的機(jī)會。(2)Hash碼的計(jì)算要盡量簡單，以減輕查找時(shí)的計(jì)算工作量，提高查找效率。（矛盾統(tǒng)一于追求效率）41構(gòu)造Hash碼的一些簡單方法(1)截段法：截取關(guān)鍵字?jǐn)?shù)字串的一段（一般選低幾位）作為該關(guān)鍵字的Hash碼。(2)分段疊加法：將關(guān)鍵字的編碼串分割成若干段，疊加后再進(jìn)行截段。(3)除法：i＝mod(k，n)均勻性較好，但需做一次除法。(4)乘法：關(guān)鍵字與常數(shù)φ相乘后用除法i＝mod(k*φ，n)，或用截段法。φ一般取0.618033988747，或0.6125423371，或0.6161616161。42構(gòu)造Hash碼構(gòu)造Hash碼的方法很多，用戶可根據(jù)具體情況自行設(shè)計(jì)。再經(jīng)過反復(fù)的試驗(yàn)、修改，從而得到均勻性好、計(jì)算簡單的Hash碼。

433.2.2幾種常用的Hash表當(dāng)元素發(fā)生沖突時(shí)，采用不同的處理方法就得到不同的Hash表。

1.線性Hash表

是一種最簡單的Hash表。當(dāng)線性Hash表發(fā)生沖突時(shí)，首先考慮緊鄰的下一個存儲位置。44(1)線性Hash表的填入將關(guān)鍵字k及有關(guān)信息填入線性Hash表的步驟如下：1)計(jì)算關(guān)鍵字k的Hash碼i＝i(k)。2)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空，則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)；若第i項(xiàng)不空，則令i＝mod(i＋1，n)，轉(zhuǎn)2)繼續(xù)檢查。只要Hash表尚未填滿，最終總可以找到一個空項(xiàng)，將關(guān)鍵字k及有關(guān)信息填入到Hash表中。45(2)線性Hash表的取出要取出關(guān)鍵字k的元素，其步驟如下：1)計(jì)算關(guān)鍵字k的Hash碼i＝i(k)。2)檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k，則取出該項(xiàng)元素即可；若第i項(xiàng)為空，則表示在Hash表中沒有該鍵字的信息；若第i項(xiàng)不空，且登記的不是關(guān)鍵字k，則令i＝mod(i＋1，n)轉(zhuǎn)2)繼續(xù)檢查。46例將關(guān)鍵字序列

(09，31，26，19，01，13，

02，11，27，16，05，21)

依次填入長度為n＝12的線性Hash表中。設(shè)Hash碼為i＝INT(k/3)＋1。47線性Hash表的缺點(diǎn)：1)在線性Hash表填入的過程中，當(dāng)發(fā)生沖突時(shí)，首先考慮的是下一項(xiàng)，因此，當(dāng)Hash碼的沖突較多時(shí)，在線性Hash表中會存在“堆聚”現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記在一起，從而會降低查找效率。2)在線性Hash表的填入過程中，處理沖突時(shí)會帶來新的沖突。482.隨機(jī)Hash表如果發(fā)生元素沖突時(shí)，表項(xiàng)序號i的改變不采用“加1取?！钡姆椒?，而是加上某種偽隨機(jī)數(shù)，這樣就形成了隨機(jī)Hash表。49

偽隨機(jī)數(shù)序列RN[j]按下列方法產(chǎn)生：（j為沖突次數(shù)）

R＝1FORj＝1TOnDO

{R＝mod(5*R，4n)

RN[j]＝INT(R/4)

}

隨機(jī)Hash表的填入和取出應(yīng)采用同一個偽隨機(jī)序列。50例將關(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，0。513.溢出Hash表前述的線性Hash表和隨機(jī)Hash表均存在一個缺點(diǎn)：在填入過程中不顧后效，沖突的元素仍然被填入到Hash表的存儲空間中，而又無法預(yù)測被占用的空間以后是否有元素正常填入，從而填入過程中沖突的機(jī)會不斷增多。52溢出Hash表如果將沖突的元素安排在另外的空間里，而不占用hash表本身的空間，則就不會產(chǎn)生新的沖突。這就是溢出Hash表。53溢出Hash表溢出Hash表包括Hash表和溢出表兩部分。

在Hash表的填入過程中，將沖突的元素順序填入溢出表，而當(dāng)查找過程中發(fā)現(xiàn)沖突時(shí)，就在溢出表中進(jìn)行順序查找。

溢出表是一個順序查找表。54例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n＝12的溢出Hash表中。設(shè)Hash碼為i＝INT(k/3)＋1。55溢出Hash表的效率在Hash碼比較均勻、沖突不多的情況下，溢出表中實(shí)際上只有很少幾項(xiàng)，即使采用順序查找，效率也不會很低。564.拉鏈Hash表拉鏈Hash表是一種最常用又最有效的Hash表。拉鏈Hash表可由Hash表及表外結(jié)點(diǎn)組成。在Hash表內(nèi)存放的并不是關(guān)鍵字K及相關(guān)信息，而是指針。57拉鏈Hash表所有的關(guān)鍵字K及有關(guān)信息分別被存儲在表外各結(jié)點(diǎn)中。每一個表外結(jié)點(diǎn)還含有一個指針域，用以鏈接Hash碼相同的其他結(jié)點(diǎn)，形成單鏈表。

Hash表內(nèi)第i項(xiàng)存放的指針，指向所有關(guān)鍵字的hash碼為i的表外結(jié)點(diǎn)組成的單鏈表。58例將關(guān)鍵字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入長度為n＝12的外鏈Hash表中。設(shè)Hash碼為i＝INT(k/3)＋1。59新的結(jié)點(diǎn)鏈接到鏈頭在填入關(guān)鍵字k及有關(guān)信息的過程中，一般總是將新的結(jié)點(diǎn)鏈接到相應(yīng)鏈表的鏈頭，而不是鏈接到鏈尾。這樣處理的優(yōu)點(diǎn)是速度快，并且在實(shí)際應(yīng)用中，往往是后填入的結(jié)點(diǎn)使用頻率比先填入的高，因此，這種處理也能提高查找效率。603.3基本的排序技術(shù)3.3.1冒泡排序與快速排序3.3.2簡單插入排序與希爾排序3.3.3簡單選擇排序與堆排序3.3.4其他排序方法簡介61什么是排序？排序也是數(shù)據(jù)處理的重用內(nèi)容。所謂排序是指將一個無序序列整理成按值遞增（或遞減）排列的有序序列。排序可以在各種存儲結(jié)構(gòu)上實(shí)現(xiàn)。本節(jié)介紹的排序?qū)ο笠话阏J(rèn)為是順序存儲的線性表，在程序設(shè)計(jì)語言上就是一維數(shù)組。62排序算法一般的評價(jià)依據(jù)平均的比較次數(shù)元素搬移的次數(shù)需要的輔助空間算法的穩(wěn)定性：

對相同排序碼的元素之間相對位置的維持12，10，11，10，1510，10，11，12，1510，10，11，12，15633.3.1冒泡排序與快速排序冒泡排序與快速排序?qū)儆诨Q類的排序方法。

所謂互換排序是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。641.冒泡排序基本思想：逐個交換次序不當(dāng)?shù)南噜彵眄?xiàng)，多趟掃描后得到排序表319241310交換192交換194交換13191019交換65冒泡排序的基本過程(1)首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個元素的大小。若前面的元素大于后面的元素，則將它們互換，稱之為消去一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的大者往后移動，最后就將線性表中的最大者換到了表的最后。這也是線性表中最大元素應(yīng)有的位置。66冒泡排序的基本過程(2)然后從后到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的小者往前移動，最后就將剩下線性表中的最小者換到了表的最前面，這也是線性表中最小元素應(yīng)有的位置。67冒泡排序的基本過程(3)對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行?。在上述排序過程中，對線性表的每一次來回掃描，都將其中的最大者沉到了表的底部，最小者像氣泡一樣冒到表的前頭。冒泡排序由此而得名（又稱下沉排序）。68算法3.5對無序序列P(1:n）

進(jìn)行冒泡排序輸入：無序序列P(1：n)。輸出：有序序列P(1：n)。

69PROCEDUREBUBSORT(P，n)[雙向冒泡排序]k＝1；m＝n[子表為P(k,m)]WHILE(k＜m)DO[子表未空就循環(huán)下去]{j＝m－1；m＝0FORi＝kTOjDO[從前往后掃描子表]

IF(p(i)＞p(i＋1))THEN[發(fā)現(xiàn)逆序進(jìn)行交換]

{d＝p(i)；p(i)＝p(i＋1)；p(i＋1)＝d；m＝i}

j＝k＋1；k＝n

[技巧:進(jìn)一步減小運(yùn)算量↑↓]

FORi＝mTOjBY－1DO[從后往前掃描子表]

IF(p(i－1)＞p(i))THEN[發(fā)現(xiàn)逆序進(jìn)行交換]

{d＝p(i)；p(i)＝p(i－1)；p(i－1)＝d；k＝i}

}[endwhile]

RETURN70有方框的位置表示掃描過程中最后一次發(fā)生交換的位置。71bubsort(p，n)/*雙向冒泡排序程序*/intn；ETp[]；{intm，k，j，i；

ETd；

k＝0；m＝n－1；

while(k＜m)/*子表未空*/

{j＝m－1；m＝0；

for(i＝k；i＜＝j(luò)；i＋＋)/*從前往后掃描*/

if(p[i]＞p[i＋1])/*發(fā)現(xiàn)逆序進(jìn)行交換*/

{d＝p[i]；p[i]＝p[i+1]；p[i+1]＝d；

m＝i；}j＝k＋1；k＝n－1；//書上印錯為k＝0

for(i＝m；i＞＝j(luò)；i－－)/*從后往前掃描*/

if(p[i－1]＞p[i])/*發(fā)現(xiàn)逆序進(jìn)行交換*/

{d＝p[i]；p[i]＝p[i-1]；p[i-1]＝d；k＝i；}

}

return；

}72冒泡排序的效率分析假設(shè)線性表長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍從前往后的掃描以及n/2遍從后往前的掃描，需要的比較次數(shù)為n(n-1)/2。

一般情況下要小于這個工作量。對于基本有序的序列，效率較高。如圖3.3所示的例子只用了兩遍掃描就完成了。732.快速排序快速排序也是一種互換式的排序方法，又稱為分區(qū)交換排序。由于它比冒泡排序速度快，因此稱為快速排序。74理解:快速排序思想kki

<kk<kjk兩端的子表不一定有序基本思想：從表中任意選取一個元素(一般取第一個)，把它放在排序表中它應(yīng)該在的位置。75112942420ijT：13611快速排序過程演示76快速排序快速排序的基本思想如下：從線性表中選取一個元素，設(shè)為T。然后將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果就將線性表分成了兩部分（稱為兩個子表），T插入到其分界線的位置處。這個過程稱為分割。77快速排序

分割后以T為分界線，將線性表分成了前后兩個子表，且前面子表的所有元素均不大于T，而后面子表中的所有元素均不小于T。對分割后的各子表再按上述原則進(jìn)行分割，直到所有子表為空為止，此時(shí)線性表就變成了有序表。78快速排序過程圖解79實(shí)際分割的步驟：首先，在表的第一個、中間一個與最后一個元素中選取中項(xiàng)，設(shè)為P(k)，并將P(k)賦給T，再將表中的第一個元素移到P(k)的位置上。（第一個位置為“空”。）

然后設(shè)置兩個指針i和j分別指向表的起始與最后的位置。80實(shí)際分割的步驟：反復(fù)作以下兩步：(1)將j逐漸減小，并逐次比較P(j)與T，直到發(fā)現(xiàn)一個P(j)＜T為止，將P(j)移到P(i)的位置上。(2)將i逐漸增大，并逐次比較P(i)與T，直到發(fā)現(xiàn)一個P(i)＞T為止，將P(i)移到P(j)的位置上。81實(shí)際分割的步驟：上述兩個操作交替進(jìn)行，直到指針i與j指向同一個位置（即i＝j(luò)）為止，此時(shí)將T移到P(i)的位置上。至此完成一次分割。

82112942420ijT：13611快速排序過程演示83算法：線性表的分割算法（自學(xué)）輸入：待分割的子表P(m：n)。

輸出：分割后的分界線位置i。

PROCEDURESPLIT(P，m，n，i)

選取P(k)其中m≤k≤n

T＝P(k)；P(k)＝P(m)

i＝m；j＝n84WHILE(i≠j)DO{WHILE(P(j)≥T)and(i＜j)DOj＝j(luò)－1

IF(i＜j)THEN

{P(i)＝P(j)；i＝i＋1

WHILE(P(i)≤T)and(i＜j)DOi＝i＋1

IF(i＜j)THEN

{P(j)＝P(i)；j＝j(luò)－1}

}}

P(i)＝TRETURN85快速排序的遞歸算法

輸入：待排序的子表P(m：n)。

輸出：有序子表P(m：n)。

PROCEDUREQKSORT1(P，m，n)

IF(n＞m)THEN[子表不空]

{SPLIT(P，m，n，i)；[分割]

QKSORT1(P，m，i－1)；[對前面子表進(jìn)行快速排序]

QKSORT1(p，i＋1，n)；[對后面子表進(jìn)行快速排序]

}

RETURN86

qksort1(p，m，n)

intm，n；ETp[]；

{inti；

if(n＞m)/*子表不空*/

{i＝split(p，m，n)；/*分割*/

qksort1(p，m，i－1)；/*對前子表進(jìn)行快速排序*/

qksort1(p，i＋1，n)；/*對后子表進(jìn)行快速排序*/

}

return；

}87

staticintsplit(p，m，n)/*返回分界線位置*/

intm，n；ETp[]；

{inti，j，k，u；

ETt；

i＝m－1；j＝n－1；k＝(i＋j)/2；

if((p[i]＞＝p[j])&&(p[j]＞＝p[k]))

u＝j(luò)；/*選取一個元素*/

elseif((p[i]＞＝p[k])&&(p[k]＞＝p[j]))u＝k；

elseu＝i；

t＝p[u]；p[u]＝p[i]；88while(i!＝j(luò))

{while((i＜j)&&(p[j]＞＝t))j＝j(luò)－1；

if(i＜j)

{p[i]＝p[j]；i＝i＋1；

while((i＜j)&&(p[i]＜＝t))i＝i＋1；

if(i＜j)

{p[j]＝p[i]；j＝j(luò)－1；}

}

}

p[i]＝t；return(i)；

}89快速排序的非遞歸算法輸入：待排序的子表P(m：n)。輸出：有序子表P(m：n)。

PROCEDUREQKSORT2(P，m，n)

建立一個棧，并初始化[棧中每一個元素有兩個數(shù)據(jù)項(xiàng)：子表第一個元素下標(biāo)與最后一個元素下標(biāo)]

將下標(biāo)m與n進(jìn)棧[子表進(jìn)棧]

WHILE棧非空

DO[還有子表需要分割]

{從棧中退出兩個下標(biāo)m與n[從棧中退出一個子表進(jìn)行分割]

WHILE(n＞m)DO[子表不空]

{SPLIT(P，m，n，i)[進(jìn)行分割]

將下標(biāo)i＋1與n進(jìn)棧[將分割出的后一個子表進(jìn)棧]

n＝i－1[對分割出前一個子表繼續(xù)進(jìn)行分割]

}

}

RETURN90性能分析：快速排序從平均時(shí)間性能來看，快速排序最佳，其時(shí)間復(fù)雜度為O(nlog2n)。但在最壞情況下，即對幾乎是排好序的輸入序列，該算法的效率很低，近似為O(n2)。另外，該算法對較大的n值效果較好。在對于關(guān)鍵值無序時(shí)的多種排序方法中，快速排序被認(rèn)為是一種最好的排序方法。913.3.2簡單插入排序與希爾排序

插入排序的基本思想是：每步將一個待排序序列的元素按其關(guān)鍵字的大小插入到已經(jīng)排好序的序列中的適當(dāng)位置，直到全部記錄插入完畢為止。常用的插入排序方法有簡單插入排序、折半插入排序、希爾排序等。921.簡單插入排序線性表中，僅僅包含第1個元素的子表顯然是有序表。然后，從第2個元素開始直到最后一個元素，逐次把每個元素插入到前面已經(jīng)有序的子表中，就完成了排序。31429351731694286

↑j＝215731694286

↑j＝3157

31694286

↑j＝413571694286

↑j＝511357694286

↑j＝611356794286

↑j＝711356794286

↑j＝811345679286

↑j＝99411234567986

↑j＝1011234567896

↑j＝1111234566789如果尋找在有序表中的插入位置時(shí)，使用二分查找，就形成了改進(jìn)的插入排序方法：折半插入排序95算法3.9簡單插入排序輸入：待排序序列P(1：n)。

輸出：有序序列P(1：n)。

PROCEDUREINSORT(P，n)

FORj＝2TOnDO

{T＝P(j)；k＝j(luò)－1

WHILE(k＞0)and(P(k)＞T)DO

{P(k＋1)＝P(k)；k＝k＋1}

P(k＋1)＝T

}

RETURN96C語言描述：簡單插入排序

insort(p，n)

intn；ETp[]；

{intj，k；

ETt；

for(j＝1；j＜n；j＋＋)

{t＝p[j]；k＝j(luò)－1；

while((k＞＝0)&&(p[k]＞t))

{p[k＋1]＝p[k]；k＝k－1；}

p[k＋1]＝t；

}

return；

}97算法分析：簡單插入排序在簡單插入排序中，每一次比較后最多去掉一個逆序，因此，這種排序方法的效率與冒泡排序相同。在最壞情況下，簡單插入排序需要n(n-1)/2次比較。從空間來看，只需占用一個元素的附加空間。O(1)982.希爾排序（縮小增量排序法）基本思想是：在整個無序序列中，將相隔增量h的元素構(gòu)成一個子序列，在每個子序列分別進(jìn)行插入排序。然后減小增量h的值，重復(fù)以上過程。直到增量h減為1時(shí)，所有元素合成一組，再進(jìn)行一次插入排序，排序完成。增量序列可取hk＝n/2K，

k＝1,2,3，…

其中n為待排序序列的長度。99希爾排序示意圖100算法：3.10希爾排序（自學(xué)）輸入：待排序序列P(1：n)。

輸出：有序序列P(1：n)。

PROCEDURESHLSORT(P，n)

h＝n/2WHILE(h＞0)DO

{FORj＝h＋1TOnDO

{t＝P(j)；i＝j(luò)－h(huán)

WHILE(i＞0)and(P(i)＞t)DO

{P(i＋h)＝P(i)；i＝i－h(huán)}

P(i＋h)＝t

}

h＝h/2

}

RETURN101C語言描述：希爾排序算法（自學(xué)）

shlsort(p，n)

intn；ETp[]；

{inth，j，i；

ETt；

h＝n/2；

while(h＞0)

{for(j＝h；j＜＝n－1；j＋＋)

{t＝p[j]；i＝j(luò)－h(huán)；

while((i＞＝0)&&(p[i]＞t))

{p[i＋h]＝p[i]；i＝i－h(huán)；}

p[i＋h]＝t；

}

h＝h/2；

}

return；

}102算法分析：希爾排序在希爾排序中，在子表中進(jìn)行的每一次比較都有可能去除掉整個線性表的多個逆序，從而改善了整個排序的性能。103算法分析：希爾排序希爾排序是一個復(fù)雜問題，到目前為止還沒有找到一種最好的增量序列。通過大量試驗(yàn)證實(shí)，希爾排序的時(shí)間復(fù)雜度為O(nlog2n)。其空間復(fù)雜度仍為O(1)。1043.3.3簡單選擇排序與堆排序1.簡單選擇排序基本思想：從無序表中選出最小的元素，把它交換到表的最前面，然后對剩下的子表采用相同的方法，直到子表空為止。對于長度為n的序列，選擇排序需要掃描n－1遍。3142已排序子表未排序子表105簡單選擇排序例子106算法3.11對無序序列P(1:n)進(jìn)行簡單選擇排序輸入：無序序列P(1：n)。輸出：有序序列P(1：n)。

PROCEDUDESELESORT(P，n)

FORi＝1TOn－1DO

{k＝i

FORj＝i＋1TOnDO

IFP(j)＜P(k)THENk＝j(luò)

IF(k≠i)THEN{d＝P(i)；P(i)＝P(k)；P(k)＝d}

}

RETURN107C語言描述：簡單選擇排序算法

selesort(p，n)

intn；ETp[]；

{inti，j，k；

ETd；

for(i＝0；i＜＝n－2；i＝i＋1)

{k＝i；

for(j＝i＋1；j＜＝n－1；j＝j(luò)＋1)

if(p[j]＜p[k])k＝j(luò)；

if(k!＝i){d＝p[i]；p[i]＝p[k]；

[k]＝d；}

}

return；

}108算法分析：簡單選擇排序簡單選擇排序算法的主要部分是二重for循環(huán)，需要比較n(n-1)/2次，時(shí)間復(fù)雜度為O(n2)。簡單選擇算法簡單、直觀，對于小規(guī)模的無序表是一種很常用的排序方法。109簡單插入與簡單選擇算法比較：簡單插入算法搬移元素的次數(shù)較多。簡單選擇算法比較元素的次數(shù)較多，但搬移次數(shù)少。對于一個基本有序的表，傾向使用

算法對于一個順序混亂的表，傾向使用

算法簡單插入簡單選擇例：1234576110堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。503845402836322018281.大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。2.較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。2.堆排序（自學(xué)）111首先將待排序的記錄序列構(gòu)造成一個堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。需解決的關(guān)鍵問題?⑴如何由一個無序序列建成一個堆（即初始建堆）？⑵如何處理堆頂記錄？⑶如何調(diào)整剩余記錄，成為一個新堆（即重建堆）？堆排序基本思想1123.3.4其他排序方法簡介1.歸并排序

是將兩個或兩個以上有序序列合并成一個有序序列的過程。

基本思想：若序列有n個元素，則看成n個子序列，先將每相鄰的兩個子序列合并，得到n/2個子序列，再兩兩合并，如此反復(fù)，直到最后合成一個有序序列。1131142.基數(shù)排序基本思想是：設(shè)線性表中各元素的關(guān)鍵字具有k位有效數(shù)字，從有效數(shù)字的最低位開始直到最高位，按每一位有效數(shù)字對線性表進(jìn)行重新排列。115116應(yīng)該從以下幾個方面綜合考慮：⑴時(shí)間復(fù)雜性；⑵空間復(fù)雜性；⑶穩(wěn)定性；⑷算法簡單性；⑸待排序記錄個數(shù)n的大??；⑹記錄本身信息量的大??；⑺關(guān)鍵碼的分布情況。各種排序方法的比較117排序方法最壞情況平均情況最好情況直接插入排序O(n2)O(n2)O(n)希爾排序O(n2)O(nlog2n)O(n1.3)起泡排序O(n2)O(n2)O(n)快速排序O(n2)O(nlog2n)O(nlog2n)簡單選擇排序O(n2)O(n2)O(n2)堆排序O(nlog2n)O(nlog2n)O(nlog2n)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)時(shí)間復(fù)雜度比較118排序方法輔助空間直接插入排序O(1)希爾排序O(1)起泡排序O(1)快速排序O(log2n)~O(n)簡單選擇排序O(1)堆排序O(1)歸并排序O(n)空間復(fù)雜度比較119所有排序方法可分為兩類，（1）一類是穩(wěn)定的，包括直接插入排序、起泡排序、直接選擇排序和歸并排序；（2）另一類是不穩(wěn)定的，包括希爾排序、快速排序和堆排序。穩(wěn)定性比較120從算法簡單性看，（1）一類是簡單算法，包括直接插入排序、直接選擇排序和起泡排序，（2）另一類是改進(jìn)后的算法，包括希爾排序、堆排序、快速排序和歸并排序，這些算法都很復(fù)雜。算法簡單性比較121從待排序的記錄個數(shù)n的大小看，n越小，采用簡單排序方法越合適，n越大，采用改進(jìn)的排序方法越合適。因?yàn)閚越小，O(n2)同O(nlog2n)的差距越小，并且輸入和調(diào)試簡單算法比輸入和調(diào)試改進(jìn)算法要少用許多時(shí)間。待排序的記錄個數(shù)比較122排序方法最好情況最壞情況平均情況直接插入排序O(n)O(n2)O(n2)起泡排序0O(n2)O(n2)直接選擇排序0O(n)O(n)記錄本身信息量越大，移動記錄所花費(fèi)的時(shí)間就越多，所以對記錄的移動次數(shù)較多的算法不利。記錄本身信息量比較1233.4二叉排序樹及其查找3.4.1二叉排序樹及其構(gòu)造3.4.2二叉排序樹查找124二叉排序樹的作用：前面提到，對分查找的效率比順序查找高，但是只能用于順序存儲的有序表。本節(jié)介紹一種對于無序表的查找方法，當(dāng)采用了一種合適的存儲結(jié)構(gòu)后，其查找效率與有序表的對分查找基本接近，這就是二叉排序樹查找。1253.4.1二叉排序樹及其構(gòu)造所謂二叉排序樹是指滿足下列條件的二叉樹：

(1)左子樹上的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值；

(2)右子樹上的所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值；

(3)左、右子樹也滿足上述兩個條件。126例如：結(jié)點(diǎn)值為數(shù)字的二叉排序樹127例如：結(jié)點(diǎn)值為字母的二叉排序樹128構(gòu)造二叉排序樹

依次讀入給定序列中的每一個元素：(1)若當(dāng)前的二叉排序樹為空，則讀入的元素為根結(jié)點(diǎn)；(2)若讀入的元素值小于根結(jié)點(diǎn)值，則將元素插入到左子樹中；(3)若讀入的元素值不小于根結(jié)點(diǎn)值，則將元素插入到右子樹中。無論是插入到左子樹還是右子樹，同樣按照上述方法處理。129例：二叉排序樹的構(gòu)造如學(xué)生成績分別為71、65、40、88、67、90、60、70、77……，建立二叉排序樹。716540886790607077130注意：構(gòu)造形態(tài)不唯一對于同一組元素，如果讀入的順序不同，構(gòu)造出的二叉排序樹形態(tài)也不同。（第一個讀入的就是根結(jié)點(diǎn)）131二叉排序樹的特性：中序遍歷二叉排序樹可以得到有序序列。因此，由無序序列構(gòu)造二叉排序樹的過程，實(shí)際上就是將一個無序序列變成有序序列的過程。由于插入的新結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，所以在插入運(yùn)算時(shí)不需要移動其他結(jié)點(diǎn)，效率較高。132算法：由無序序列構(gòu)造二叉排序樹（自學(xué)）輸入：長度為n的無序序列A(1：n)。輸出：二叉排序樹的頭指針BT。PROCEDUREINBSORT(A，n，BT)BT＝0FORk＝1TOnDO{NEW(p)[取得一個新結(jié)點(diǎn)]V(p)＝A(k)；L(p)＝0；R(p)＝0j＝BTIF(j＝0)THENBT＝p[若二叉排序樹為空]ELSE[二叉排序樹不空]133

{WHILE(L(j)≠p)and(R(j)≠p)DO[未到葉子結(jié)點(diǎn)]{IF(A(k)＜V(j))THEN[插入到左子樹]{IF(L(j)≠0)THENj＝L(j)ELSEL(j)＝p}ELSE[插入到右子樹]{IF(R(j)≠0)THENj＝R(j)ELSER(j)＝p}}}}RETURN134#include"stdlib.h"/*malloc

函數(shù)需要包含頭文件stdlib.h*/struct

btnode