計算機軟件技術(shù)基礎(chǔ)第3章1

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

3.1基本的查找技術(shù)

3.2哈希表技術(shù)

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

3.4二叉排序樹及其查找

3.1基本的查找技術(shù)

3.1.1順序查找

3.1.2有序表的對分查找

3.1.3分塊查找

3.1.1順序查找

⑴如果線性表為無序表（即表中元素的排列是

無序的），則不管是順序存儲結(jié)構(gòu)還是鏈式存

儲結(jié)構(gòu)，都只能用順序查找。

⑵即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu),

也只能用順序查找。

線性表在順序存儲結(jié)構(gòu)下的順序查找

輸入：線性表長度n以及線性表的存儲空間V；

被查找的元素X。

輸出：被查找元素x在線性表中的序號鼠

如果在線性表中不存在元素x,則輸出k=

—1O

PROCEDURESERCH(V,n,x,k)

k=l

WHILE(kWn)and(V(k)Wx)DOk=k+l

IF(k=n+l)THENk=-l

RETURN

/*函數(shù)返回被查找元素X在線性表中的序號，

如果在線性表中不存在元素值X,則返回一1*/

intsearch(intv[],intn,intx)

{intk；

k=0；

while((k<n)&&(v[k]!=x))k=k+l；

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

return(k)；

線性表在鏈式存儲結(jié)構(gòu)下的順序查找

輸入：線性鏈表頭指針HEAD以及存儲空間V、NEXT；

被查找的元素X。

輸出：被查找元素x的結(jié)點在線性鏈表中的存儲序號k。

如果在線性鏈表中不存在元素值為x的結(jié)點，

則輸出k=-1。

PROCEDURELSERCH(V,NEXT,HEAD,x,k)

k=HEAD

WHILE(kWO)and(V(k)Wx)DOk=NEXT(k)

IF(k=0)THENk=-l

RETURN

structnode

{intd；structnode*next；}；

/*函數(shù)返回被查找元素x所在結(jié)點的存儲地址，

如果在線性鏈表中不存在元素值為x的結(jié)點，則返回

NULL*/

structnode*Iserch(structnode*head,intx)

{structnode*k；

k=head；

while((k!=NULL)&&(k—>d!=x))k=k—>next；

return(k)；

3.1.2有序表的對分查找

設(shè)有序線性表的長度為n,被查元素為x。

將x與線性表的中間項進行比較：

(1)若中間項的值等于x,則說明查到，查找結(jié)束；

(2)若x小于中間項的值，則在線性表的前半部分(即中間項以前

的部分)以相同的方法進行查找；

(3)若x大于中間項的值，則在線性表的后半部分(即中間項以后

的部分)以相同的方法進行查找。

這個過程一直進行到查找成功或子表長度為0(說明線性表中沒有

這個元素)為止。

在最壞情況下，對分查找只需比較log2n次，而順序查找需比較n

次。

有序線性表在順序存儲結(jié)構(gòu)下的對分查找

輸入：有序線性表長度n以及線性表的存儲空間V；被查找的元素X。

輸出：被查找元素x在有序線性表中的序號k。如果在線性表中不存

在兀素x,則輸出k=-1。

PROCEDUREBSERCH(V,n,x,k)

i=l；j=n

WHILE(i<=j)DO

{k=(i+j)/2

IF(V(k)=x)THENRETURN

IF(V(k)>x)THENj=k—1；

ELSEi=k+l；

}

IF(i>j)THENk=-l

RETURN

intbserch(intv[],intn,intx)

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

如果在線性表中不存在元素值x,則返回一1*/

{inti,j,k；

i=l;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+l；

return(—1)；

3.1.3分塊查找（索引順序）

分塊有序表

將長度為n線性表分成m個子表，各子表的長度可以相等，也可以互相不

等，但要求后一個子表中的每一個元素均大于前一個子表中的所有元素o

分塊有序表的結(jié)構(gòu)可以分為兩部分：

⑴線性表本身采用順序存儲結(jié)構(gòu)。

⑵再建立一個索引表。在索引表中，對線性表的每個子表建立一個索

引結(jié)點，每個結(jié)點包括兩個域：一是數(shù)據(jù)域，用于存放對應(yīng)子表中的

最大元素值；二是指針域，用于指示對應(yīng)子表的第一個元素在整個線

性表中的序號。

structindnode

{intkey；/*數(shù)據(jù)域，存放子表中的最大值,

其類型與線性表中元素的數(shù)據(jù)類

型相同*/

intk；/*指針域，指示子表中第一個元素

在線性表中的序號*/

索引表

數(shù)據(jù)域224686

指針域1713

線性表：2213080920334244382446605874478653

⑴首先查找索引表，以便確定被查元素所在的子表。由

于索引表數(shù)據(jù)域中的數(shù)據(jù)是有序的，因此可以采用對

分查找。

⑵然后在相應(yīng)的子表中用順序查找法進行具體的查找。

分塊查找

輸入：長度為n的線性表L的存儲空間V（Ln）；索引表中

的數(shù)據(jù)域存儲空間KEY（1：m）與指針域存儲空間

K（l：m）；被查元素x。

輸出：被查元素x在線性表L中的序號j（即使L（j）

=乂的））。如果x不在線性表L中，則置j=—1。

PROCEDUREINSERCH(V,n,KEY,K,m,x,j)

i=l；j=m

WHILE(j-i>l)DO［對分查找索引表］

{t=(i+j)/2

IF(xWKEY(t))THENj=t

ELSEi=t

)

IF(iWj)and(x>KEY(i))THENi=j

j=K(i)；t=n

IF(iWm)THENt=K(i+l)-l［確定順序查找的終點］

WHILE(jWt)and(V(j)Wx)DOj=j+l［順序查找子表］

IF(j>t)THENj=—1

RETURN

在分塊查找中，為了找到被查元素X所在的子表，需要對分查找索引

表，在最壞情況下需要查找log2（m+l）次。

在相應(yīng)子表中用順序查找法查找元素x,在最壞情況下需要查找n/m

（假設(shè)各子表長度相等）次；而在平均情況下需要查找n/（2m）次。

因此，分塊查找的工作量為：

在最壞情況下需要查找log2（m+l）+n/m次，

平均情況下大約需要查找log2（口+1）+n/（2m）次。

當m=n時，線性表L即為有序表，分塊查找即為對分查找

當m=l時，線性表L為一般的無序表，分塊查找即為順序查找。

分塊查找的效率介于對分查找和順序查找之間。

structindnode

{intkey；/*數(shù)據(jù)域，存放子表中的最大值,

intk；/*指針域，指示子表中第一個

元素在線性表中的序號*/

intinserch(intv[],intn,structindnodes[],intm,intx)

{inti,j,t；

i=l;j=m；

while(j-i>l)/*對分查找索引表*/

{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；t=n；

if(i!=m)t=s[i+l].k—1；/*確定順序查找的終點*/

while((j<=t)&&(V[j]!=x))j=j+1；/*順序查找子表*/

if(j>t)j=-1；

return(j)；

3.2哈希表技術(shù)

3.2.1Hash表的基本概念

基本思想：對被查元素的關(guān)鍵字做某種運算后直接確定

所要查找項目在表中的位置。

3.2.2幾種常用的Hash表

11.線性Hash表

2.隨機Hash表

<3,溢出Hash表

4.拉鏈Hash表

I5.指標Hash表

3.2.1Hash表的基本概念

1.直接查找技術(shù)

設(shè)表的長度為n。如果存在一個函數(shù)i=i(k),對于表中的任

意一個元素的關(guān)鍵字k,滿足以下條件：

(1)KiCn；

(2)對于任意的元素關(guān)鍵字瓦Wk2,恒存在i(kJWiIk?)。

則稱此表為直接查找表。

其中函數(shù)i=i(k)稱為關(guān)鍵字k的映像函數(shù)。

對于直接查找表的操作：

⑴直接查找表的填入

要將關(guān)鍵字為k的元素填入到直接查找表，只

需做以下兩步：

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

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

(2)直接查找表的取出

要在直接查找表中取出關(guān)鍵字k的元素，也只

需做以下兩步：

1)升算美鍵字k的映象函數(shù)i=i(k)；

2)檢查表中第i項：

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

素；

否則取出第i項中的元素即可。

2.Hash表

例

將關(guān)鍵字序列

(09,31,26,19,01,13,02,11,27,16,05,21)

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

映象函數(shù)為i=INT(k/3)+lo

表項序號123<456789101112

?i=INT(k/3)+l01050913161921262731

埴入的關(guān)鍵字k0211

設(shè)表的長度為n。如果存在一個函數(shù)i=i(k),對于表中的

任意一個元素的關(guān)鍵字k,滿足IWiWn,則稱此表為

Hash表。

其中函數(shù)1=i(k)稱為關(guān)鍵字k的Hash碼。

Hash表技術(shù)的關(guān)鍵是處理表中元素的沖突問題，其工作：

(1)構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次數(shù)。

即Hash碼的均勻性要比較好。

⑵當表中元素發(fā)生沖突時，要進行適當?shù)奶幚怼?/p>

3.Hash碼的構(gòu)造

(1)使各關(guān)鍵字盡可能均勻地分布在Hash表中，

即Hash碼的均勻性要好，以便減少沖突發(fā)生的

機會。

⑵Hash碼的計算要盡量簡單。

Hash碼的構(gòu)造方法：

(1)截段法(數(shù)值分析法的一種)

(2)分段疊加法

(3)除法(除留余數(shù)法)

i=mod(k,n)

(4)乘法

i=mod(k*0,n)

0一般取0.618033988747,或0.6125423371,

或0.6161616161。

3.2.2幾種常用的Hash表

1.線性Hash表

⑴線性Hash表的填入

將關(guān)鍵字k及有關(guān)信息填入線性Hash表的步驟如下：

1)計算關(guān)鍵字k的布511碼1=i(k)o

2)檢查表中第i項的內(nèi)容：

若第i項為空，則將關(guān)鍵字k及有關(guān)信息填入該項；

若第i項不空，則令i=mod(i+l,n),轉(zhuǎn)2)繼續(xù)檢查。

只要Hash表尚未填滿，最終總可以找到一個空項，將關(guān)

鍵字

k及有關(guān)信息填入到Hash表中。

(2)線性Hash表的取出

要在線性Hash表中取出關(guān)鍵字k的元素，其步驟如下：

1)計算關(guān)鍵字k的Hash碼i=i(k)。

2)檢查表中第i項的內(nèi)容：

若第i項登記著關(guān)鍵字k,則取出該項元素即可；

若第i項為空，則表示在Hash表中沒有該關(guān)鍵字的信息;

若第i項不空，且登記的不是關(guān)鍵字k,則令

i=mod(i+l,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。

表項序號123456789101112

關(guān)鍵字kU10205091311191626273121

沖突次數(shù)01100202U004

缺點:

1）在線性Hash表填入的過程中，當發(fā)生沖

突時，首先考慮的是下一項，因此，當

Hash碼的沖突較多時，在線性Hash表中

會存在“堆聚”現(xiàn)象，即許多關(guān)鍵字被

連續(xù)登記在一起，從而會降低查找效率。

2）在線性Hash表的填入過程中，處理沖突

時會帶來新的沖突。

2.隨機Hash表

(1)隨機Hash表的填入

將關(guān)鍵字k及有關(guān)信息填入隨機Hash表的步驟如下：

1)計算關(guān)鍵字k的Hash碼i0=i(k)。且令i=i()。

2)偽隨機數(shù)序列初始化，令j=l(即將取隨機數(shù)指針指向

偽隨機數(shù)序列中的第1個隨機數(shù))。

3)檢查表中第i項的內(nèi)容：

若第i項為空，則將關(guān)鍵字k及有關(guān)信息填入該項；

若第i項不空,則令i=mod(io+RN(j),n),并令j=j+

1(即將取隨機數(shù)指針指向下一個隨機數(shù))，轉(zhuǎn)3)繼續(xù)

檢查。

其中RN(j)表示偽隨機數(shù)序列RN中的第j個隨機數(shù)。

偽隨機數(shù)序列RN按下列方法產(chǎn)生:

R=1

FORj=lTOnDO

{R=mod(5*R,4n)

RN(j)=INT(R/4)

例

將關(guān)鍵字序列

(09,31,26,19,01,13,02,11,27,16,05,21)

依次填入長度為n=24=16的隨機Hash表中。

設(shè)Hash碼為i=INT(k/3)+1。

偽隨機數(shù)序列為：

1,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0。

表項序號12345678910111213141516

關(guān)鍵字k010205091316192126113127

沖突次數(shù)011000000202

(2)隨機Hash表的取出

要在隨機Hash表中取出關(guān)鍵字k的元素，其步驟如下：

1)計算關(guān)鍵字k的Hash碼i0=i(k)。且令i=i()。

2)偽隨機數(shù)序列初始化，令j=l(即將取隨機數(shù)指針指向偽

隨機數(shù)序列中的第1個隨機數(shù))。

3)檢查表中第i項的內(nèi)容：

若第i項登記著關(guān)鍵字k,則取出該項元素即可；

若第i項空，則表示在Hash表中沒有該關(guān)鍵字信息；

若第i項不空，且登記的不是關(guān)鍵字k,則令

i=mod(i0+RN(j),n),并令j=j+l(即將取隨機數(shù)指

針指向下一個隨機數(shù))，轉(zhuǎn)3)繼續(xù)檢查。

其中RN(j)表示偽隨機數(shù)序列RN中的第j個隨機數(shù)。

3.溢出Hash表

溢出Hash表包括Hash表和溢出表兩部分。

在Hash表的填入過程中，將沖突的元素順序填入溢出

表，而當查找過程中發(fā)現(xiàn)沖突時，就在溢出表中進行

順序查找。

溢出表是一個順序查找表。

(1)溢出Hash表的填入

將關(guān)鍵字k及有關(guān)信息填入溢出Hash表的步

驟如下：

1)計算關(guān)鍵字k的Hash碼i=i(k)。

2)檢查表中第i項的內(nèi)容：

若第i項為空，則將關(guān)鍵字k及有關(guān)信息

填入該項；

若第i項不空，則將關(guān)鍵字k及有關(guān)信息

依次填入溢出表中的自由項。

(2)溢出Hash表的取出

要在溢出Hash表中取出關(guān)鍵字k的元素，其步驟如

下：

1)計算關(guān)鍵字k的Hasl^^=i(k)o

2)檢查表中第i項的內(nèi)容：

若第i項登記著關(guān)鍵字k,則取出該項元素即可;

若第i項為空，則表示在Hash表中沒有該關(guān)鍵字

信息；

工正;項不空，且登記的不是關(guān)鍵字k,則轉(zhuǎ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。

Hash表

1123456789101112

k01050913161921262731

溢出表

1234???

k0211

4.拉鏈Hash表

拉鏈Hash表又分為外鏈Hash表與內(nèi)鏈Hash表。

(1)外鏈Hash表的填入

將關(guān)鍵字k及有關(guān)信息填入外鏈Hash表的步驟如

下：

1)計算關(guān)鍵字k的Hash碼i=i(k)。

2)取得一個新結(jié)點p,并將關(guān)鍵字k及有關(guān)信息填

入結(jié)點P。

3)將結(jié)點p鏈入以H(i)為頭指針的鏈表的鏈頭。

iH(i)

例：z02010

050

將關(guān)鍵字序列(09,31,26,19,30

01,13,02,11,27,16,05,21)4z11090

依次填入長度為n=12的外鏈Hash表5f13

中。616_0_

設(shè)Hash碼為i=INT(k/3)+1。7f190_

8

210

9—>260

10—>27_0_

11T310

120

(2)外鏈Hash表的取出

要在外鏈Hash表中取出關(guān)鍵字k的元素，其

步驟如下：

1)計算關(guān)鍵字k的Haslr^i=i(k)。

2)在以H(i)為頭指針的鏈表中順序查找關(guān)

鍵字力k的結(jié)點。若找到，則從結(jié)點中取

出該元素。

若哈希函數(shù)為H,編寫在拉鏈Hash表a中查找關(guān)鍵字為K的數(shù)據(jù)元素

的算法

typedefstructchain{intkey;intdate;structchain*next;}node;

node*hash_search(node*a口，intk)

{——

node*p;

inti;i=H(k);p=a[i];

while(p!=NULL&&p->key!=k)p=p->next;

if(p==NULL)

{printff'searchingfailed,5);

return(NULL);

)

else

return(p);

設(shè)哈希函數(shù)為H(k)=kmodll,哈希函數(shù)長度為11(地址空間為070)

,給定表(SUN,MON,TUE,WED,TJHU,FRI,SAT)取單詞的第一個字母

在英語字母表中的序號為關(guān)鍵字K,構(gòu)造哈希表，并用拉鏈法解決

地址沖突。

5.指標Hash表

針對表項空間長度不等的情況。

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

內(nèi)容表：所有關(guān)鍵字及有關(guān)信息。

指標表：表項存放關(guān)鍵字信息在內(nèi)容表中的地址。

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

3.3.1冒泡排序與快速排序

3.3.2簡單插入排序與希爾排序

3.3.3簡單選擇排序與堆排序

3.3.4其他排序方法簡介

3.3.1冒泡排序與快速排序

1.冒泡排序

(1)首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰

兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則

將它們互換，稱之為消去了一個逆序。顯然，在掃描過程中，不斷地將

兩相鄰元素中的大者往后移動，最后就將線性表中的最大者換到了表的

最后O

(2)然后從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較

相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素小于前面的元素,

則將它們互換，這樣就又消去了一個逆序。顯然，在掃描過程中，不斷

地將兩相鄰元素中的小者往前移動，最后就將剩下線性表中的最小者換

到了表的最前面。

(3)對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此

時的線性表已經(jīng)變?yōu)橛行颉?/p>

輸入：無序序列P(Ln)o

輸出：有序序列P(Ln)o

PROCEDUREBUBSORT(P,n)

k=1；m=n

WHILE(k<m)DO［子表未空］

{j=m—1；m=0

FORi=kTOjDO［從前往后掃描子表］

IF(p(i)>p(i+l))THEN［發(fā)現(xiàn)逆序進行交換］

{d=p⑴;p(i)=p(i+l)；p(i+l)=d；m=i}

j=k+l；k=0

FORi=mTOjBY-1DO［從后往前掃描子表］

IF(p(i-l)>p(i))THEN［發(fā)現(xiàn)逆序進行交換］

{d=p⑴;p(i)=p(i—1)；p(i-1)=d；k=i}

RETURN

原序列51731694286

第1遍以前往后）5-<-->17^~~---->69-*~~>4-2**~~>8-*—>6

結(jié)果153167428回9

以后往前）15-<~->16—7<*~->4^^>28-<—>69

結(jié)果11回326746回；9

第2遍以前往后）115—3—267—4—689

結(jié)果111Tl2564叵|789

以后往前）115*--*6*->46789

結(jié)果1121Tl456回789

第3遍以前往后）11234566789

最后結(jié)果

11?■:*1*./2，.3fk?-4566789

bubsort(intp[],intn)

intm,k,j,i；

intd；

k=0；m=n—1；

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

{j=m—1；m=0；

for(i=k；i〈=j；i++)/*從前往后掃描*/

if(p：i]>p：i+l])/*發(fā)現(xiàn)逆序進行交換*/

{d=p[i]；

p[i]=p[i+l];

p[i+l]=d；

m=i；}

j=k+l；k=0；

for(i=m；i>=j；i--)/*從后往前掃描*/

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

{

d=p[i]；

p[i]=p[i-l];

p[i-l]=d；k=i；

return；

2.快速排序

通過一次交換消除多個逆序。

分副

無

序<T

分割—

線--->JL

性

表分割

首先，在表的第一個、中間一個與最后一個元素中選取中

項，

設(shè)為P(k),并將P(k)賦給T,再將表中的第一個元素移到

P(k)的位置上。

然后設(shè)置兩個指針i和j分別指向表的起始與最后的位置。

反復作以下兩步：

⑴將j逐漸減小,并逐次比較P(j)與T,直到發(fā)現(xiàn)一個

P(j)<T為止,將P(j)移到P(i)的位置上。

(2)將i逐漸增大,并逐次比較P(i)與T,直到發(fā)現(xiàn)一個

P⑴〉T為止,將P(i)移到P(j)的位置上。

上述兩個操作交替進行，直到指針i與j指向同一個位置

(即i=j)為止，此時將T移到P(i)的位置上。

線性表的分割

輸入：待分割的子表P(m：n)o

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

PROCEDURESPLIT(P,m,n,i)

選取P(k)其中mWkWn

T=P(k)；P(k)=P(m)

i=m；j=n

winjH

1=(J)d

{1一「=「'(Dd=(Dd}

N9HI(r>I)HI

l+!=!OQ(「>I)PUEQW⑴d)miHM

I+I=J，(「)d=(I)d

N3HI(P>I)HI

i—「=「oa(P>i)p?(i^(Dd)aniHM)

oad)miHM

快速排序的遞歸算法

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

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

PROCEDUREQKSORT1(P,m,n)

IF(n>m)THEN［子表不空］

{SPLIT(P,m,n,i)；［分割］

QKSORT1(P,m,i—1)；［對前面子表進行快速排序］

QKSORTl(p,i+1,n)；［對后面子表進行快速排序］

RETURN

qksortl(intp[],intm,intn)

{inti；

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

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

qksortl(p,m,i—1)；/*對前子表進行快速排序*/

qksortl(p,i+1,n)；/*對后子表進行快速排序*/

}

return；

staticintsplit(intp[],intm,intn)

/*返回分界線位置*/

{inti,j,k,u；

intt；

i=m—1；j=n—1；k=(i+j)/2；

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+l；

while((i<j)&&(p[i]<=t))i=i+l；

if(i<j)

{j=j-1;}

p[i]=t；return(i+1)；

快速排序的非遞歸算法

輸入：待排序的子表P(in：n)0

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

PROCEDUREQKSORT2(P,m,n)

建立一個棧，并初始化［棧中每一個元素有兩個數(shù)據(jù)項：子表第一個

元素下標與最后一個元素下標］

將下標m與n進棧［子表進棧］

WHILE棧非空DO［還有子表需要分割］

(從棧中退出兩個下標m與n［從棧中退出一個子表進行分割］

WHILE(n>m)DO［子表不空］

{SPLIT(P,m,n,i)［進行分割］

將下標i+1與n進棧［將分割出的后一個子表進棧］

n=i-l［對分割出前一個子表繼續(xù)進行分割］

}

RETURN

習題:利用快速排序方法對一組記錄的關(guān)鍵碼(54,38,96,23,

15,72,60,45,83)以第一個關(guān)鍵碼作為劃分基準進行排序,分析

遞歸調(diào)用的過程和每次遞歸調(diào)用是對那一組數(shù)據(jù)。

初始序列：543896231572604583

第一趟后:453815235472609683

第一次遞歸調(diào)用

第二趟后：233815455472609683

第二次遞歸調(diào)用

第三趟后：152338455472609683

第三次遞歸調(diào)用

第四趟后：152338455460729683

第四次遞歸調(diào)用

第五趟后：152338455460728396

習題:利用快速排序方法對一組記錄的關(guān)鍵碼(503,87,512,61,908,

170,897,275,653,462)以第一個關(guān)鍵碼作為劃分基準進行排序,

分析遞歸調(diào)用的過程和每次遞歸調(diào)用是對那一組數(shù)據(jù)。

初始序列：5038751261908170897275653462

第一趟后：4628727561170503897908653512

第二趟后：1708727561462503897908653512

第三趟后：6187170275462503897908653512

第四趟后：6187170275462503897908653512

第五趟后：6187170275462503512653897908

第六趟后：6187170275462503512653897908

3.3.2簡單插入排序與希爾排序

L簡單插入排序

將無序序列中的各元素依次插入到已經(jīng)有序的線

桂行市。

輸入：待排序序列P(Ln)o

輸出：有序序列P(Ln)o

PROCEDUREINSORT(P,n)

FORj=2TOnDO

{T=P(j)；k=j—1

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

{P(k+1)=P(k)；k=k+l}

P(k+1)=T

RETURN

II

insort(intp口，intn)

{intj,k；

intt；

for(j=l；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+l]=t；

return；

2.希爾排序

基本思想：將整個無序序列分割成若干小子序列分別進行插入

排序。

子序列的分割方法如下：

將相隔某個增量h的元素構(gòu)成一個子序列。在排序

過程中，逐次減小這個增量，最后當h減到1時，進

行一次插入排序，排序就完成。

增量序列一般取ht=n/2k(k=l,2,…，[log2n]),

其中n為待排序序列的長度。

6___6___

ZCM

g____

coCO-13

CO____2當

9

了__

co

OO____6-66

CU

送一自一2

g____00―國一"6

LD_00

co巴一

22___3-CT)

區(qū)一?區(qū)一S-'

cn___00_S-'t-

匕一4后一1￡一ir.i

co

II

A

輸入：待排序序列P(Ln)o

輸出：有序序列P(l：n)o

PROCEDURESHLSORT(P,n)

h—n/2

WHILE(h>0)DO

{FORj=h+lTOnDO

{t=P(j)；i=j—h

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

{P(i+h)=P⑴;i=i—h}

P(i+h)=t

}

h=h/2

RETURN

voidshlsort(intp[],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；

return；

3.3.3簡單選擇排序與堆排序

1.簡單選擇排序

原序列8921564885161947

第1遍選擇|16|21564885891947

第2遍選擇16|19|564885;8921：47

第3遍選擇1619|21|4885895647

第4遍選擇161921|47|85895648

第5遍選擇1619:2147|48|895685

第6遍選擇1619：214748|56|8985

第7遍選擇161921474856|15|89

輸入：無序序列P(Ln)o

輸出：有序序列P(Ln)o

PROCEDUDESELESORT(P,n)

FORi=lTOn-1DO

{k=i

FORj=i+lTOnDO

IFP(j)<P(k)THENk=j

IF(kWi)THEN

{d=P⑴;P(i)=P(k)；P(k)=d}

RETURN

selesort(intp口，intn)

{inti,j,k；

intd；

for(i=0；i<=n—2；i=i+l)

{k=i；

for(j=i+l；j<=n—1；j=j+1)

if(ptj]<p[k])k=j；

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

return；

2.堆排序

堆的定義：

具有n個元素的序列(％,h2,hn),

當且僅當滿足

hh

li^21+l

(i=l,2,n/2)時稱之為堆。

由堆的定義可以看出，堆頂元素

(即第一個元素)必為最大項。

具有n個元素的序列(%,h2,

h1,

當且僅當滿足

‘3Vh2i

<

、兒-

h2i+i

(i=b2,n/2)時稱之為堆。

實際處理時，可以用一維數(shù)組H(l:n)來存儲堆序列中

的元素，也可以用完全二叉樹來直觀表示堆的結(jié)構(gòu)。

序列(91,85,53,36,47,30,24,12)是一個堆

調(diào)整建堆

在一棵具有n個結(jié)點的完全二叉樹(用一維數(shù)組

H(Ln)表示)中，假設(shè)結(jié)點H(m)的左右子樹均

為堆，現(xiàn)要將以H(m)為根結(jié)點的子樹也調(diào)整為堆

co

調(diào)整建堆

輸入：完全二叉樹數(shù)組H(l：n)o其中結(jié)點H(m)的左右子樹均為堆。

輸出：以H(m)為根結(jié)點的子樹為堆。

PROCEDURESIFT(H,n,m)

t=H(m)；j=2m

WHILE(jWn)DO

{IF(j<n)and(H(j)<H(j+l))THENj=j+l

IF(t<H(j))THEN

{H(m)=H(j)；m=j；j=2m}

elsej=n+1

)

H(m)=t

RETURN

根據(jù)堆的定義，可以得到堆排序的方法：

（1）首先將一個無序序列建成堆。

⑵然后將堆頂元素（序列中的最大項）與堆中最

后一個元素交換（最大項應(yīng)該在序列的最后）。

不考慮已經(jīng)換到最后的那個元素，只考慮前

n—1個元素構(gòu)成的子序列，顯然，該子序列已

不是堆，但左、右子樹仍為堆，可以將該子序

列調(diào)整為堆。

反復做第⑵步，直到剩下的子序列為空為止。

堆排序

輸入：無序序列H(Ln)o

輸出：無序序列H(Ln)o

PROCEDUREHEAPSORT(H,n)

k=n/2

FORi=kTO1BY-1DO

SIFT(H,n,i)［無序序列建堆］

FORi=nTO2BY-1DO

{t=H⑴;H(l)=H(i)；H(i)=t［堆頂元素換到最后］

SIFT(H,i-1,1)［調(diào)整建堆］

RETURN

heapsort(intp[],intn)

{inti,k；

intt；

k=n/2；

for(i=k—1；i>=0；i---)

sift(p,n—1,i)；/*無序序列建堆*/

for(i=n—1；i>=l；i---)

{t=p[0]；p[0]=p[i]；p[i]=t；/*堆頂元素換到最后*/

sift(p,i—1,0)；/*調(diào)整建堆*/

return；

staticsift(inth口，intn,intm)

{intj；

ETt；

t=h[m]；j=2*(m+l)—1；

while(j<=n)

{if((j<n)&&(h[j]<h[j+l]))j=j+1；

if(t<h[j])

{h[m]=h[j]；m=j；j=2*(m+1)—1；

elsej=n+1；

)

h[m]=t；

return；

334其他排序方法簡介

1.歸并排序

將兩個或兩個以上的有序表合并成一個新的有序表。

設(shè)線性表L(l：n)中的某段L(low：high)已經(jīng)部分有序,

即它的兩個子裝L(low：mid)與L(mid+1：high)(其

中l(wèi)owSmidWhigh)已經(jīng)有序，現(xiàn)要將這兩個有序子表

歸并成一個有序子表L(low：high)o

實現(xiàn)上述兩個子表歸并的基本做法如下：

(1)開辟一個與線性表L同樣大小的表空間A。

⑵設(shè)置三個指針i,j,k,其初始狀態(tài)分別指向兩個有序子

表的首部及表空間A中與L中需要進行排序段相對應(yīng)空間

的首部。即i=low,j=mid+l,k=low0

⑶沿兩個有序子表掃描：

若L⑴WL(j),則A(k)=L⑴，且i與k指針均加1；

否則A(k)=L(j),且j與k指針均加1。

如此反復，直到有一個子表的指針已經(jīng)指到末端(即子

表內(nèi)的元素已經(jīng)取空)為止。

(4)將未取空的子表中的剩余元素依次放入表空間A中。

(5)將A中的對應(yīng)段復制到L中。

兩個相鄰有序子表的合并

輸入：兩個相鄰有序子表L(low：mid)與L(mid+Lhigh)

(其中l(wèi)owWmidWhigh)；工作數(shù)組A(low：high)o

輸出：有序子表L(low：high)o

PROCEDUREMERGE(L,low,mid,high,A)

i=low,j=mid+l,k=low

WHILE(i^mid)and(jChigh)DO

{IFL(i)<L(j)THEN{A(k)=L(i)；i=i+l}

ELSE{A(k)=L(j)；j=j+1}

k=k+l

IF(iCmid)THEN

{FORj=iTOmidDO{A(k)=L(j)；k=k+l}

ELSE

{IF(jWhigh)THEN

FORi=jTOhighDO

{A(k)=L(i)；k=k+l}

}

FORi=lowTOhighDOL(i)=A(i)

RETURN

排序前(⑼(⑶(05)如(01)⑸⑶)(⑹

II4I

(⑶⑼95,27)(0326)(舊31)

II

(053339,27)91,16」26,31)

I

(01,05,13,16i19,26,27J31)

,,??.1?|?*\?.?,-'-.????***4?*?/.

歸并排序的非遞歸算法

輸入：無序序列P(Ln)o

輸出：有序序列P(Ln)o

PROCEDUREMERGSORT(P,n)

定義工作數(shù)組A(1：n)

m=1

WHILE(m<n)DO

{k=2m

FORj=lTOnBYkDO

{low=j；high=j+k—1；mid=j+m—1

IF(high>n)THENhigh=n

IF(high>mid)THEN

MERGE(P,low,mid,high,A)

}

m=k

RETURN

ttinclude〃stdlib.h〃

mergsort(intp口，intn)

{intm,k,j,low,high,mid；

ET*a；

a=malloc(n*sizeof(int))；

m=1；

while(m<n)

{k=2*m；

for(j=l；j<=n；j=j+k)

{low=j；high=j+k—1；mid=j+m—1；

if(high>n)high=n；

if(high>mid)

merge(p,low,mid,high,a)；

}

m=k；

free(a)；

return；

staticmerge(intp口，intlow,intmid,inthigh,inta口)

{inti,j,k；

i=low；j=mid+l；k=low；

while((i<=mid)&&(j<=high))

{if(p[i—1]<=p[j—1])

{a[k—1]=p[i-1]；i=i+l；}

else

{a[k-1]=p[j-1]；j=j+1；}

k=k+l；

if(i<=mid)

for(j=i；j<=mid；j++)

{a[k—1]=p[j—1]；k=k+l；}

else

{if(j<=high)

{for(i=j；i<=high；i++)

{a[k—1]=p[i-1]；k=k+l；

}

)

for(i=low；i<=high；i++)

p[i—1]=a[i—1]；

return；

2基數(shù)排序

設(shè)線性表中各元素的關(guān)鍵字具有k位有效數(shù)字,

則基數(shù)排序的基本思想是：

從有效數(shù)字的最低位開始直到最高位，對于每

一位有效數(shù)字對線性表進行重新排列，其調(diào)整

的原則為：

(1)將線性表依當前位的有效數(shù)字為序排列；

(2)當前位的有效數(shù)字相同時，按原次序排歹人

這種基數(shù)排序法稱為最低位優(yōu)先法

(LSD---LeastSignificantDigitfirst)

排序前按末位排序連接按首位排序連接

19(0)01(0)01,02,05,0901

13(1)01,31,11,2131(1)11,13,16,1902

05C2)0211(2)21,26,2T05

27(3),1321(3)31'09

01(4工02:⑷11

?IS.V-*

26⑸0513；(5)；13

31(6)26,1605(6)16

16CT)2726CT)19

02(8)：16：(8)：21

09(9)19,0927(9)；26

1119”；27

210931

基數(shù)排序的最高位優(yōu)先法

(MSD----MostSignificantDigitfirst)。

在這種方法中，是從有效數(shù)字的最高位開始直

到最低位進行調(diào)整。在這種情況下，必須將線

性表按有效位從高到低逐層分割成若干子表，

然后對各子表獨立進行排序。

冒泡排序n(n—1)/2

快速排序n(n—1)/2

簡單插入排序n(n—1)/2

希爾排序0(nL5