第3章查找與排序技術(shù)3.1基本的查找技術(shù)3.2哈希表技術(shù)3.3基本的排序技術(shù)3.4二叉排序樹及其查找所謂查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。查找的效率將直接影響到數(shù)據(jù)處理的效率。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。3.1基本的查找技術(shù)3.1.1順序查找3.1.2有序表的對分查找3.1.3分塊查找順序查找又稱順序搜索。其基本方法是：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示查找成功；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素，即查找失敗。3.1.1順序查找如果線性表為無序表（即表中元素的排列是無序的）,則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),都只能用順序查找即使是有序線性表,如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),也只能用順序查找無序線性表鏈?zhǔn)接行蚓€性表線性表在順序存儲(chǔ)結(jié)構(gòu)下的順序查找輸入線性表長度n以及線性表的存儲(chǔ)空間V;被查找的元素x。輸出被查找元素x在線性表中的序號(hào)k。如果在線性表中不存在元素x,則輸出k=-1PROCEDURESERCH(V,n,x,k)k=1WHILE(k≤n)and(V(k)≠x)DOk=k+1IF(k=n+1)THENk=-1RETURN/*函數(shù)返回被查找元素x在線性表中的序號(hào),如果在線性表中不存在元素值x,則返回-1*/intsearch(ETv[],intn,intx){

intk;k=0;

while((k<n)&&(v[k]≠x))k=k+1;

if(k==n)k=-1;

return(k);}線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的順序查找輸入線性鏈表頭指針HEAD以及存儲(chǔ)空間V,NEXT被查找的元素x輸出被查找元素x的結(jié)點(diǎn)在線性鏈表中的存儲(chǔ)序號(hào)k如果在線性鏈表中不存在元素值為x的結(jié)點(diǎn),則輸出k=-1PROCEDURELSERCH(V,NEXT,HEAD,x,k)k=HEAD

WHILE(k≠0)and(V(k)≠x)DOk=NEXT(k)IF(k=0)THENk=-1RETURNstructnode{ETd;

structnode*next;};/*函數(shù)返回被查找元素x所在結(jié)點(diǎn)的存儲(chǔ)地址,

如果在線性鏈表中不存在元素值為x的結(jié)點(diǎn),則返回NULL*/structnode*lsearch(structnode*head,ETx){structnode*k;k=head;

while((k!=NULL)&&(k->d!=x))k=k->next;

return(k);}對分查找只適用于順序存儲(chǔ)的有序表。本書所說的有序表均指元素按值非遞減排列的線性表。非遞減排列即從小到大排列，但允許相鄰元素相等。3.1.2有序表的對分查找設(shè)有序線性表的長度為n,被查元素為x。將x與線性表的中間項(xiàng)進(jìn)行比較若中間項(xiàng)的值等于x,則說明查到,查找結(jié)束若x小于中間項(xiàng)的值,則在線性表的前半部分以相同的方法進(jìn)行查找若x大于中間項(xiàng)的值,則在線性表的后半部分以相同的方法進(jìn)行查找這個(gè)過程一直進(jìn)行到查找成功或子表長度為0(說明線性表中沒有這個(gè)元素)為止對分查找的效率比順序查找高得多。可以證明，對于長度為n的有序線性表，在最壞情況下，對分查找只需比較log2n次，而順序查找需比較n次。有序線性表在順序存儲(chǔ)結(jié)構(gòu)下的對分查找輸入有序線性表長度n以及線性表的存儲(chǔ)空間V被查找的元素x輸出被查找元素x在有序線性表中的序號(hào)k。

如果在線性表中不存在元素x,則輸出k=-1PROCEDUREBSERCH(V,n,x,k)i=1;j=nWHILE(i<=j)DO

{k=(i+j)/2IF(V(k)=x)THENRETURNIF(V(k)>x)THENj=k-1;ELSEi=k+1;}IF(i>j)THENk=-1RETURNk=（i+j）/2；if(key

>a[k].key)i=k+1；elseif(key<

a[k].key)j=k–1；elsefinditem,break;kij/*函數(shù)返回被查找元素x在線性表中的序號(hào)如果在線性表中不存在元素值x,則返回-1*/intbserch(ET

v[],int

n,ETx){int

i,j,k;i=1;j=n;

while(i<=j){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);}3.1.3分塊查找分塊查找又稱索引順序查找。它是一種順序查找的改進(jìn)方法，用于在分塊有序表中進(jìn)行查找。分塊有序表:將長度為n線性表分成m個(gè)子表,各子表的長度可以相等,也可以互相不等,但要求后一個(gè)子表中的每一個(gè)元素均大于前一個(gè)子表中的所有元素。分塊有序表的結(jié)構(gòu)可以分為兩部分：線性表本身采用順序存儲(chǔ)結(jié)構(gòu)。再建立一個(gè)索引表。在索引表中,對線性表的每個(gè)子表建立一個(gè)索引結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)包括兩個(gè)域：一是數(shù)據(jù)域,用于存放對應(yīng)子表中的最大元素值二是指針域,用于指示對應(yīng)子表的第一個(gè)元素在整個(gè)線性表中的序號(hào)索引表的定義struct

indnode{ETkey;/*數(shù)據(jù)域,存放子表中的最大值,

其類型與線性表中元素的數(shù)據(jù)類型相同*/intk;/*指針域,指示子表中第一個(gè)元素在線性表中的序號(hào)*/};分塊有序表的查找過程：首先查找索引表,以便確定被查元素所在的子表。由于索引表數(shù)據(jù)域中的數(shù)據(jù)是有序的,因此可以采用對分查找然后在相應(yīng)的子表中用順序查找法進(jìn)行具體的查找分塊查找輸入：長度為n的線性表L的存儲(chǔ)空間V(1：n);索引表中的數(shù)據(jù)域存儲(chǔ)空間KEY(1：m)與指針域存儲(chǔ)空間K(1：m);被查元素x。輸出被查元素x在線性表L中的序號(hào)j（即使L(j)=x的j）。如果x不在線性表L中,則置j=-1。struct

indnode{ETkey;

intk;};

/*函數(shù)返回被查找元素x在線性表中的序號(hào),

如果在線性表中不存在元素值x,則返回-1*/intinsearch(ETv[],intn,struct

indnodes[],intm,ETx){inti,j,t;i=1;j=m;while(j-i>1)/*對分查找索引表*/{t=(i+j)/2;if(x<=s[t].key)j=t;elsei=t;}

if((i!=j)&&(x>s[i].key))i=j;j=s[i].k;/*確定起點(diǎn)*/t=n;/*確定i=m的終點(diǎn)*/if(i!=m)t=s[i+1].k-1;

/*確定順序查找的終點(diǎn)*/

while((j<=t)&&(V[j]!=x))j=j+1;

/*順序查找子表*/if(j>t)j=-1;

return(j);}算法分析：分塊查找法因此，分塊查找的工作量為：在最壞情況下需要查找log2(m＋1)＋n/m次，平均情況下大約需要查找log2(m＋1)＋n/(2m)次。當(dāng)m＝1時(shí)，線性表L為一般的無序表，分塊查找即為順序查找。當(dāng)m＝n時(shí)，線性表L即為有序表，分塊查找即為對分查找分塊查找的效率介于對分查找和順序查找之間。3.2哈希表技術(shù)3.2.1Hash表的基本概念3.2.2幾種常用的Hash表前述順序查找、二分查找、分塊查找等查找方法，都是通過比較達(dá)到查找的目的。下面介紹的哈希（Hash）表技術(shù)的基本思想是通過對被查元素的關(guān)鍵字做某種運(yùn)算后直接確定所要查找的項(xiàng)目在表中的位置。在介紹hash表之前，先了解“直接查找表”。3.2.1Hash表的基本概念1.直接查找技術(shù)

設(shè)表的長度為n。如果存在一個(gè)函數(shù)i=i(k),對于表中的任意一個(gè)元素的關(guān)鍵字k,滿足以下條件1≤i≤n;對于任意的元素關(guān)鍵字k1≠k2,恒存在i(k1)≠i(k2)

則稱此表為直接查找表。其中函數(shù)i=i(k)稱為關(guān)鍵字k的映象函數(shù)(1)直接查找表的填入要將關(guān)鍵字為k的元素填入到直接查找表,只需做以下兩步：1.

計(jì)算關(guān)鍵字k的映象函數(shù)i=i(k);2.

將關(guān)鍵字k及有關(guān)元素信息填入到表的第i項(xiàng)。(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)中的元素即可元素存儲(chǔ)位置的沖突：在直接查找表中，提出了要求：若k1≠k2，則恒存在i(k1)≠i(k2)

。即不允許元素的存儲(chǔ)位置發(fā)生沖突。但這一要求往往很難滿足。2.Hash表例

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

依次填入長度為n=12的表中。映象函數(shù)為i=INT(k/3)+1。表項(xiàng)序號(hào)123456789101112按i=INT(k/3)+1填入的關(guān)鍵字k093126190113021127160521沖突根源：從較大的關(guān)鍵字空間映射到較小的地址空間

Hash表技術(shù)是直接查找技術(shù)的推廣，其主要目標(biāo)是提高查找效率。在Hash表中允許沖突存在。Hash表技術(shù)的關(guān)鍵就是要處理好表中元素的沖突問題。設(shè)表的長度為n。如果存在一個(gè)函數(shù)i=i(k),對于表中的任意一個(gè)元素的關(guān)鍵字k,滿足1≤i≤n,則稱此表為Hash表。其中函數(shù)i=i(k)稱為關(guān)鍵字k的Hash碼。構(gòu)造合適的Hash碼,以便盡量減少表中元素沖突的次數(shù)。即Hash碼的均勻性要比較好當(dāng)表中元素發(fā)生沖突時(shí),要進(jìn)行適當(dāng)?shù)奶幚?.Hash碼的構(gòu)造(1)使各關(guān)鍵字盡可能均勻地分布在Hash表中,即Hash碼的均勻性要好,以便減少?zèng)_突發(fā)生的機(jī)會(huì)(2)Hash碼的計(jì)算要盡量簡單截段法分段疊加法除法

i=mod(k,n)乘法

i=mod(k*φ,n)

φ一般取0.618033988747,或0.6125423371,或0.6161616161。3.2.2幾種常用的Hash表當(dāng)元素發(fā)生沖突時(shí)，采用不同的處理方法就得到不同的Hash表。

1.線性Hash表

是一種最簡單的Hash表。當(dāng)線性Hash表發(fā)生沖突時(shí)，首先考慮緊鄰的下一個(gè)存儲(chǔ)位置。(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表尚未填滿,最終總可以找到一個(gè)空項(xiàng),將關(guān)鍵字k及有關(guān)信息填入到Hash表中(2)線性Hash表的取出要在線性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表中沒有該關(guān)鍵字的信息;若第i項(xiàng)不空,且登記的不是關(guān)鍵字k,則令

i=mod(i+1,n)轉(zhuǎn)2繼續(xù)檢查例將關(guān)鍵字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入長度為n=12的線性Hash表中設(shè)Hash碼為i=INT(k/3)+1表項(xiàng)序號(hào)123456789101112關(guān)鍵字k沖突次數(shù)093126190113021127160521000000120214線性Hash表的缺點(diǎn)在線性Hash表填入的過程中,當(dāng)發(fā)生沖突時(shí),首先考慮的是下一項(xiàng),因此,當(dāng)Hash碼的沖突較多時(shí),在線性Hash表中會(huì)存在“堆聚”現(xiàn)象,即許多關(guān)鍵字被連續(xù)登記在一起,從而會(huì)降低查找效率在線性Hash表的填入過程中,處理沖突時(shí)會(huì)帶來新的沖突2.隨機(jī)Hash表

如果發(fā)生元素沖突時(shí)，表項(xiàng)序號(hào)i的改變不采用“加1取模”的方法，而是加上某種偽隨機(jī)數(shù)，這樣就形成了隨機(jī)Hash表。(1)隨機(jī)Hash表的填入

將關(guān)鍵字k及有關(guān)信息填入隨機(jī)Hash表的步驟如下1.計(jì)算關(guān)鍵字k的Hash碼i0=i(k)。且令i=i02.偽隨機(jī)數(shù)序列初始化,令j=1（即將取隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）3.檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)為空,則將關(guān)鍵字k及有關(guān)信息填入該項(xiàng)若第i項(xiàng)不空,則令i=mod(i0+RN(j),n),并令j=j+1（即將取隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)）,轉(zhuǎn)3繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)例將關(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表項(xiàng)序號(hào)12345678910111213141516關(guān)鍵字k沖突次數(shù)093126190113021127160521000000122010(2)隨機(jī)Hash表的取出要在隨機(jī)Hash表中取出關(guān)鍵字k的元素,其步驟如下1.計(jì)算關(guān)鍵字k的Hash碼i0=i(k)。且令i=i0。2.偽隨機(jī)數(shù)序列初始化,令j=1（即將取隨機(jī)數(shù)指針指向偽隨機(jī)數(shù)序列中的第1個(gè)隨機(jī)數(shù)）。3.檢查表中第i項(xiàng)的內(nèi)容：若第i項(xiàng)登記著關(guān)鍵字k,則取出該項(xiàng)元素即可;若第i項(xiàng)空,則表示在Hash表中沒有該關(guān)鍵字信息;若第i項(xiàng)不空,且登記的不是關(guān)鍵字k,則令

i=mod(i0+RN(j),n),并令j=j+1（即將取隨機(jī)數(shù)指針指向下一個(gè)隨機(jī)數(shù)）,轉(zhuǎn)3繼續(xù)檢查。其中RN(j)表示偽隨機(jī)數(shù)序列RN中的第j個(gè)隨機(jī)數(shù)線性Hash表和隨機(jī)Hash表均存在一個(gè)缺點(diǎn)：在填入過程中不顧后效，沖突的元素仍然被填入到Hash表的存儲(chǔ)空間中，而又無法預(yù)測被占用的空間以后是否有元素正常填入，從而填入過程中沖突的機(jī)會(huì)不斷增多。如果將沖突的元素安排在另外的空間里，而不占用hash表本身的空間，則就不會(huì)產(chǎn)生新的沖突。這就是溢出Hash表。3.溢出Hash表溢出Hash表包括Hash表和溢出表兩部分。

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

溢出表是一個(gè)順序查找表。(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)不空,則將關(guān)鍵字k及有關(guān)信息依次填入溢出表中的自由項(xiàng)。(2)溢出Hash表的取出要在溢出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表中沒有該關(guān)鍵字信息;若第i項(xiàng)不空,且登記的不是關(guān)鍵字k,則轉(zhuǎn)入在溢出表中進(jìn)行順序查找例將關(guān)鍵字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入長度為n=12的溢出Hash表中。設(shè)Hash碼為i=INT(k/3)+1。i123456789101112k093126190113021127160521i1234…k溢出Hash表的效率在Hash碼比較均勻、沖突不多的情況下，溢出表中實(shí)際上只有很少幾項(xiàng)，即使采用順序查找，效率也不會(huì)很低。4.拉鏈Hash表

是最常用最有效的Hash表

拉鏈Hash表又分為外鏈Hash表與內(nèi)鏈Hash表。(1)外鏈Hash表的填入將關(guān)鍵字k及有關(guān)信息填入外鏈Hash表的步驟如下1.計(jì)算關(guān)鍵字k的Hash碼i=i(k)2.取得一個(gè)新結(jié)點(diǎn)p,并將關(guān)鍵字k及有關(guān)信息填入結(jié)點(diǎn)p3.將結(jié)點(diǎn)p鏈入以H(i)為頭指針的鏈表的鏈頭例將關(guān)鍵字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入長度為n=12的外鏈Hash表中。設(shè)Hash碼為i=INT(k/3)+1。(2)外鏈Hash表的取出要在外鏈Hash表中取出關(guān)鍵字k的元素,其步驟如下1.計(jì)算關(guān)鍵字k的Hash碼i=i(k)。2.在以H(i)為頭指針的鏈表中順序查找關(guān)鍵字為k的結(jié)點(diǎn)。若找到,則從結(jié)點(diǎn)中取出該元素。5.指標(biāo)Hash表

指標(biāo)Hash表包括指標(biāo)表與內(nèi)容表兩部分。

3.3基本的排序技術(shù)3.3.1冒泡排序與快速排序3.3.2簡單插入排序與希爾排序3.3.3簡單選擇排序與堆排序什么是排序？排序也是數(shù)據(jù)處理的重用內(nèi)容。所謂排序是指將一個(gè)無序序列整理成按值遞增（或遞減）排列的有序序列。排序可以在各種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。本節(jié)介紹的排序?qū)ο笠话阏J(rèn)為是順序存儲(chǔ)的線性表，在程序設(shè)計(jì)語言上就是一維數(shù)組。排序算法一般的評價(jià)依據(jù)平均的比較次數(shù)元素搬移的次數(shù)需要的輔助空間算法的穩(wěn)定性：對相同排序碼的元素之間相對位置的維持12，10，11，10，1510，10，11，12，1510，10，11，12，153.3.1冒泡排序與快速排序冒泡排序與快速排序?qū)儆诨Q類的排序方法。

所謂互換排序是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。1.冒泡排序基本思想：逐個(gè)交換次序不當(dāng)?shù)南噜彵眄?xiàng)，多趟掃描后得到排序表319241310交換192交換194交換13191019交換1.冒泡排序首先,從表頭開始往后掃描線性表,在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中,前面的元素大于后面的元素,則將它們互換,稱之為消去了一個(gè)逆序。顯然,在掃描過程中,不斷地將兩相鄰元素中的大者往后移動(dòng),最后就將線性表中的最大者換到了表的最后。演示單向冒泡排序然后從后到前掃描剩下的線性表,同樣,在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中,后面的元素小于前面的元素,則將它們互換,這樣就又消去了一個(gè)逆序。顯然,在掃描過程中,不斷地將兩相鄰元素中的小者往前移動(dòng),最后就將剩下線性表中的最小者換到了表的最前面對剩下的線性表重復(fù)上述過程,直到剩下的線性表變空為止,此時(shí)的線性表已經(jīng)變?yōu)橛行颉Ｓ蟹娇虻奈恢帽硎緬呙柽^程中最后一次發(fā)生交換的位置。bubsort(ETp[],intn)

{intm,k,j,i;

ETd;

k=0;m=n-1;

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

{j=m-1;m=0;

for(i=k;i<=j;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=0;

for(i=m;i>=j;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;

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

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

<kk<kjk兩端的子表不一定有序基本思想：從表中任意選取一個(gè)元素(一般取第一個(gè))，把它放在排序表中它應(yīng)該在的位置。112942420ijT：13611快速排序過程演示分割算法1

在表的第一個(gè)、中間一個(gè)與最后一個(gè)元素中選取中項(xiàng),設(shè)為P(k),并將P(k)賦給T,再將表中的第一個(gè)元素移到P(k)的位置上。2然后設(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(i)>T為止,將P(i)移到P(j)的位置上上述兩個(gè)操作交替進(jìn)行,直到指針i與j指向同一個(gè)位置（即i=j）為止,此時(shí)將T移到P(i)的位置上舉例：5,3,9,6,4,1,3,773146935ijjiiiiji線性表的分割輸入：待分割的子表P(m：n)。輸出：分割后的分界線位置i。PROCEDURESPLIT(P,m,n,i)

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

T=P(k);P(k)=P(m)

i=m;j=n

WHILE(i≠j)DO

{WHILE(P(j)≥T)and(i<j)DOj=j-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-1}

}

}

P(i)=T

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

/*返回分界線位置*/

staticintsplit(ETp[],intm,intn){

inti,j,k,u;

ETt;

i=m-1;j=n-1;k=(i+j)/2;

/*選取一個(gè)中間值元素*/

if((p[i]>=p[j])&&(p[j]>=p[k]))

u=j;elseif((p[i]>=p[k])&&(p[k]>=p[j]))u=k;

elseu=i;

t=p[u];

p[u]=p[i];

while(i!=j)

{while((i<j)&&(p[j]>=t))j=j-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-1;}

}

}

p[i]=t;

return(i);

}voidqksort1(ETp[],intm,intn)

{inti;

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

{i=split(p,m,n);/*分割*/

qksort1(p,m,i-1);/*對前子表進(jìn)行快速排序*/

qksort1(p,i+1,n);/*對后子表進(jìn)行快速排序*/

}

return;

}性能分析：快速排序從平均時(shí)間性能來看，快速排序最佳，其時(shí)間復(fù)雜度為O(nlog2n)。但在最壞情況下，即對幾乎是排好序的輸入序列，該算法的效率很低，近似為O(n2)。另外，該算法對較大的n值效果較好。在對于關(guān)鍵值無序時(shí)的多種排序方法中，快速排序被認(rèn)為是一種最好的排序方法。3.3.2簡單插入排序與希爾排序插入排序的基本思想是：每步將一個(gè)待排序序列的元素按其關(guān)鍵字的大小插入到已經(jīng)排好序的序列中的適當(dāng)位置，直到全部記錄插入完畢為止。常用的插入排序方法有簡單插入排序、折半插入排序、希爾排序等。1.簡單插入排序

線性表中，僅僅包含第1個(gè)元素的子表顯然是有序表。然后，從第2個(gè)元素開始直到最后一個(gè)元素，逐次把每個(gè)元素插入到前面已經(jīng)有序的子表中，就完成了排序。輸入待排序序列P(1：n)。輸出有序序列P(1：n)。314251731694286

↑j=215731694286

↑j=315731694286

↑j=413571694286

↑j=511357694286

↑j=6

11356794286

↑j=711356794286

↑j=811345679286

↑j=911234567986

↑j=1011234567896

↑j=1111234566789演示簡單插入排序voidinsort(ETp[],intn)

{intj,k;ETt;for(j=1;j<n;j++){t=p[j];k=j-1;while((k>=0)&&(p[k]>t)){p[k+1]=p[k];k=k-1;}p[k+1]=t;}return;}算法分析：簡單插入排序在簡單插入排序中，每一次比較后最多去掉一個(gè)逆序，因此，這種排序方法的效率與冒泡排序相同。在最壞情況下，簡單插入排序需要n(n-1)/2次比較。從空間來看，只需占用一個(gè)元素的附加空間。O(1)2.希爾排序（縮小增量排序法）將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序子序列的分割方法如下：將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序過程中,逐次減小這個(gè)增量,最后當(dāng)h減到1時(shí),進(jìn)行一次插入排序,排序就完成。增量序列一般取ht=n/2k(k=1,2,…,[log2n]),其中n為待排序序列的長度。演示希爾排序輸入：待排序序列P(1：n)。輸出：有序序列P(1：n)。shlsort(ETp[],intn)

{inth,j,i;ETt;h=n/2;while(h>0){for(j=h;j<=n-1;j++){t=p[j];i=j-h;while((i>=0)&&(p[i]>t)){p[i+h]=p[i];i=i-h;}

p[i+h]=t;}h=h/2;}

}算法分析：希爾排序在希爾排序中，在子表中進(jìn)行的每一次比較都有可能去除掉整個(gè)線性表的多個(gè)逆序，從而改善了整個(gè)排序的性能。

希爾排序是一個(gè)復(fù)雜問題，到目前為止還沒有找到一種最好的增量序列。通過大量試驗(yàn)證實(shí)，希爾排序的時(shí)間復(fù)雜度為O(nlog2n)。其空間復(fù)雜度仍為O(1)。3.3.3簡單選擇排序與堆排序1.簡單選擇排序基本思想：從無序表中選出最小的元素，把它交換到表的最前面，然后對剩下的子表采用相同的方法，直到子表空為止。對于長度為n的序列，選擇排序需要掃描n－1遍。3142已排序子表未排序子表例子輸入：無序序列P(1：n)輸出：有序序列P(1：n)selesort(ETp[]，intn)

{inti,j,k;ETd;for(i=0;i<=n-2;i=i+1)//掃描n-1遍

{k=i;for(j=i+1;j<=n-1;j=j+1)if(p[j]<p[k])k=j;//找到最小

if(k!=i){d=p[i];p[i]=p[k];p[k]=d;}

//把最小元素?fù)Q到字表最前面

}return;}算法分析：簡單選擇排序簡單選擇排序算法的主要部分是二重for循環(huán)，需要比較n(n-1)/2次，時(shí)間復(fù)雜度為O(n2)。簡單選擇算法簡單、直觀，對于小規(guī)模的無序表是一種很常用的排序方法。

簡單插入算法搬移元素的次數(shù)較多。簡單選擇算法比較元素的次數(shù)較多，但搬移次數(shù)少。對于一個(gè)基本有序的表，傾向使用

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

算法簡單插入簡單選擇2.堆排序堆的定義：具有n個(gè)元素的序列(h1,h2,…,hn),

當(dāng)且僅當(dāng)滿足

(i=1,2,…,n/2)時(shí)稱之為堆。

由堆的定義可以看出,堆頂元素(即第一個(gè)元素)必為最大項(xiàng)。或

具有n個(gè)元素的序列(h1,h2,…,hn),

當(dāng)且僅當(dāng)滿足

(i=1,2,…,n/2)時(shí)稱之為堆

序列(91,85,53,36,47,30,24,12)是一個(gè)堆調(diào)整建堆在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹（用一維數(shù)組H(1：n)表示）中,假設(shè)結(jié)點(diǎn)H(m)的左右子樹均為堆,現(xiàn)要將以H(m)為根結(jié)點(diǎn)的子樹也調(diào)整為堆。4791538530361224調(diào)整建堆輸入完全二叉樹數(shù)組H(1：n)。其中結(jié)點(diǎn)H(m)的左右子樹均為堆。輸出以H(m)為根結(jié)點(diǎn)的子樹為堆。堆排序算法1首先將一個(gè)無序序列建成堆。2然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。不考慮已經(jīng)換到最后的那個(gè)元素,只考慮前n-1個(gè)元素構(gòu)成的子序列,顯然,該子序列已不是堆,但左、右子樹仍為堆,可以將該子序列調(diào)整為堆。反復(fù)做2,直到剩下的子序列為空為止。

堆排序輸入無序序列H(1：n)輸出有序序列H(1：n)staticsift(ETh[],intn,intm){intj;ETt;t=h[m];j=2*(m+1)-1;while(j<=n){if((j<n)&&(h[j]<h[j+1]))j=j+1;if(t<h[j]){h[m]=h[j];m=j;j=2*(m+1)-1;}elsej=n+1;}

h[m]=t;}heapsort(ETp[],intn)

{inti,k;ETt;k=n/2;for(i=k-1;i>=0;i--)sift(p,n-1,i);/*無序序列建堆*/for(i=n-1;i>=1;i--){/*堆頂元素?fù)Q到最后*/

t=p[0];p[0]=p[i];p[i]=t;sift(p,i-1,0);/*調(diào)整建堆*/

}}應(yīng)該從以下幾個(gè)方面綜合考慮：⑴時(shí)間復(fù)雜性；⑵空間復(fù)雜性；⑶穩(wěn)定性；⑷算法簡單性；⑸待排序記錄個(gè)數(shù)n的大小；⑹記錄本身信息量的大小；⑺關(guān)鍵碼的分布情況。各種排序方法的比較排序方法最壞情況平均情況最好情況直接插入排序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ù)雜度比較排序方法輔助空間直接插入排序O(1)希爾排序O(1)冒泡排序O(1)快速排序O(log2n)~O(n)簡單選擇排序O(1)堆排序O(1)歸并排序O(n)空間復(fù)雜度比較所有排序方法可分為兩類，（1）一類是穩(wěn)定的，包括直接插入排序、冒泡排序、直接選擇排序和歸并排序；（2）另一類是不穩(wěn)定的，包括希爾排序、快速排序和堆排序。穩(wěn)定性比較從算法簡單性看，（1）一類是簡單算法，包括直接插入排序、直接選擇排序和冒泡排序，（2）另一類是改進(jìn)后的算法，包括希爾排序、堆排序、快速排序和歸并排序，這些算法都很復(fù)雜。算法簡單性比較從待排序的記錄個(gè)數(shù)n的大小看，n越小，采用簡單排序方法越合適，n越大，采用改進(jìn)的排序方法越合適。因?yàn)閚越小，O(n2)同O(nlog2n)的差距越小，并且輸入和調(diào)試簡單算法比輸入和調(diào)試改進(jìn)算法要少用許多時(shí)間。待排序的記錄個(gè)數(shù)比較排序方法最好情況最壞情況平均情況直接插入排序O(n)O(n2)O(n2)冒泡排序0O(n2)O(n2)直接選擇排序0O(n)O(n)記錄本身信息量越大，移動(dòng)記錄所花費(fèi)的時(shí)間就越多，所以對記錄的移動(dòng)次數(shù)較多的算法不利。記錄本身信息量比較3.4二叉排序樹及其查找3.4.1二叉排序樹及其構(gòu)造3.4.2二叉排序樹查找前面提到，對分查找的效率比順序查找高，但是只能用于順序存儲(chǔ)的有序表。本節(jié)介紹一種對于無序表的查找方法，當(dāng)采用了一種合適的存儲(chǔ)結(jié)構(gòu)后，其查找效率與有序表的對分查找基本接近，這就是二叉排序樹查找。3.4.1二叉排序樹及其構(gòu)造(1)左子樹上的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值(2)右子樹上的所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值(3)左、右子樹也滿足上述兩個(gè)條件例如：結(jié)點(diǎn)值為數(shù)字的二叉排序樹依次讀入給定序列中的每一個(gè)元素：1

若當(dāng)前的二叉排序樹為空,則讀入的元素為根結(jié)點(diǎn);2

若讀入的元素值小于根結(jié)點(diǎn)值,則將元素插入到左子樹中;3

若讀入的元素值不小于根結(jié)點(diǎn)值,則將元素插入到右子樹中。無論是插入到左子樹還是右子樹,同樣按照上述方法處理80,82,85,75,82,68,71,77,88808285758268717788二叉排序樹的另一種形態(tài)注意：構(gòu)造形態(tài)不唯一對于同一組元素，如果讀入的順序不同，構(gòu)造出的二叉排序樹形態(tài)也不同。（第一個(gè)讀入的就是根結(jié)點(diǎn)）二叉排序樹的特性：中序遍歷二叉排序