數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版）（微課版）課件 梁海英 第7章 查找；第8章 排序

第7章查找教學(xué)要求相關(guān)知識(shí)點(diǎn)順序查找、折半查找算法二叉排序樹(shù)的插入和查找算法哈希表、哈希函數(shù)、哈希地址、裝填因子哈希函數(shù)的選取原則及產(chǎn)生沖突的原因采用開(kāi)放地址法和鏈地址法解決沖突時(shí)，哈希表的建表方法、查找過(guò)程學(xué)習(xí)重點(diǎn)掌握順序查找、折半查找、二叉排序樹(shù)查找以及哈希表查找的基本思想和算法實(shí)現(xiàn)。目錄靜態(tài)查找算法動(dòng)態(tài)查找表

哈希表3查找的基本概念

124本章小結(jié)57.1查找的基本概念7.1查找的基本概念查找的基本概念1.關(guān)鍵字（key）關(guān)鍵字(Key)是數(shù)據(jù)元素中唯一標(biāo)識(shí)該元素的某個(gè)數(shù)據(jù)項(xiàng)的值，使用基于關(guān)鍵字的查找，查找結(jié)果是唯一的。2.查找根據(jù)給定的某個(gè)值，在數(shù)據(jù)集合中尋找一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。結(jié)果分兩種情況：（1）查找成功：數(shù)據(jù)集合中存在相應(yīng)的數(shù)據(jù)元素；（2）查找失?。簲?shù)據(jù)集合中不存在關(guān)鍵字等于給定值的數(shù)據(jù)元素。7.1查找的基本概念3.查找表（searchtable）

由同一數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素構(gòu)成的數(shù)據(jù)集合，可以是一個(gè)數(shù)組或一個(gè)鏈表等數(shù)據(jù)類(lèi)型。

(1)靜態(tài)查找表(StaticSearchTable)如果一個(gè)查找表的操作只涉及查詢(xún)某個(gè)特定的數(shù)據(jù)元素是否在查找表中或者檢索滿(mǎn)足條件的某個(gè)特定的數(shù)據(jù)元素的各屬性值，無(wú)須修改查找表，這類(lèi)查找表稱(chēng)為靜態(tài)查找表。靜態(tài)查找表適用于：查找表一經(jīng)生成，便只對(duì)其進(jìn)行查找，而不進(jìn)行插入和刪除操作，或經(jīng)過(guò)一段時(shí)間的查找之后，集中地進(jìn)行插入和刪除等修改操作。7.1查找的基本概念

(2)動(dòng)態(tài)查找表(DynamicSearchTable)如果對(duì)一個(gè)查找表的操作在查找的同時(shí)需要?jiǎng)討B(tài)地插入或刪除的查找表則稱(chēng)為動(dòng)態(tài)查找表。動(dòng)態(tài)查找表適用于：查找與插入或刪除操作在同一個(gè)階段進(jìn)行，例如，在某些問(wèn)題中，當(dāng)查找成功時(shí)，要?jiǎng)h除查找的記錄，當(dāng)查找不成功時(shí)，要插入被查找的記錄。7.1查找的基本概念4.查找算法的時(shí)間復(fù)雜度衡量查找算法的優(yōu)劣，主要是看要查找的值與關(guān)鍵字的比較次數(shù)。通常把查找過(guò)程中對(duì)關(guān)鍵字的最多比較次數(shù)和平均比較次數(shù)作為衡量一個(gè)查找算法效率優(yōu)劣兩個(gè)基本技術(shù)指標(biāo)。前者叫做最大查找長(zhǎng)度（MaximunSearchLength），簡(jiǎn)記為MSL。后者叫做平均查找長(zhǎng)度（AverageSearchLength），簡(jiǎn)記ASL，計(jì)算公式為：ASL=

其中：

n是查找表長(zhǎng)度；Pi是查找第i個(gè)數(shù)據(jù)元素的概率;Ci是找到第i個(gè)數(shù)據(jù)元素所需進(jìn)行的比較次數(shù)。7.1查找的基本概念5.查找結(jié)構(gòu)各種數(shù)據(jù)結(jié)構(gòu)都涉及查找操作，如線(xiàn)性表、隊(duì)列、棧、樹(shù)與圖等。為提高查找效率，需要專(zhuān)門(mén)為查找操作設(shè)置數(shù)據(jù)結(jié)構(gòu)，這種面向查找操作的數(shù)據(jù)結(jié)構(gòu)成為查找結(jié)構(gòu)(SearchStructure)。本章討論的查找結(jié)構(gòu)有：靜態(tài)查找表、動(dòng)態(tài)查找表和哈希表。7.2靜態(tài)查找算法7.2靜態(tài)查找算法靜態(tài)查找算法通常采用順序查找和折半查找。順序查找順序查找(SequnceSearch)又稱(chēng)線(xiàn)性查找(LinearSearch)，主要用于在線(xiàn)性表中進(jìn)行查找。順序查找通常分為無(wú)序表的順序查找和有序順序表的順序查找。7.2靜態(tài)查找算法1.無(wú)序表的順序查找（1）基本思想從線(xiàn)性表的一端開(kāi)始，逐個(gè)檢查關(guān)鍵字是否滿(mǎn)足給定的條件。若查到某個(gè)元素的關(guān)鍵字滿(mǎn)足給定條件，則查找成功，返回該元素在線(xiàn)性表中的位置；若已經(jīng)查到表的另一端，還沒(méi)有找到符合給定條件的元素，則返回查找失敗的信息。為了提高查找速度，可在算法中設(shè)置“哨兵”。哨兵就是待檢查值，將它放在查找方向的“盡頭”處，這樣免去了在查找過(guò)程中每一次比較完之后都要判斷查找位置是否越界，從而節(jié)省了時(shí)間。7.2靜態(tài)查找算法(2)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)#defineMAXSIZE100typedefintkeyType;typedefstruct{keyTypekey; /*關(guān)鍵字域*/}SElemType;typedefstruct{SElemType*elem;//數(shù)據(jù)元素存儲(chǔ)空間基址

intlength; /*表長(zhǎng)度*/}SeqTable;7.2靜態(tài)查找算法(3)順序查找算法intSearch_Seq(SSTableST,ElemTypekey)

/*在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。若找到返回該元素在表中的位置；否則返回-1*/{

ST.elem[ST.TableLen]=key;/*"哨兵"*/

for(i=0;ST.elem[i].key!=key;++i);

/*從前往后找*/

if(i<ST.TableLen)returni;

elsereturn-1;/*未找到，返回-1*/}7.2靜態(tài)查找算法對(duì)于有n個(gè)元素的表，給定值key與表中第i個(gè)元素的關(guān)鍵字相等，即定位第i個(gè)元素時(shí)，需要進(jìn)行n-i+1次關(guān)鍵字的比較，即Ci=n-i+1，等概率Pi=1/n。查找成功時(shí)，平均長(zhǎng)度為：ASL成功=查找不成功時(shí)，與表中各關(guān)鍵字的比較次數(shù)顯然是n+1次，從而順序查找不成功的平均查找長(zhǎng)度為ASL失敗=n+1。平均查找長(zhǎng)度為：ASL平均=(ASL成功+ASL失敗)/2=(n+1)*3/47.2靜態(tài)查找算法缺點(diǎn)：當(dāng)元素個(gè)數(shù)較大時(shí)，平均查找長(zhǎng)度較大，查找效率低，它的時(shí)間復(fù)雜度為O(n)。優(yōu)點(diǎn)：對(duì)數(shù)據(jù)元素的存儲(chǔ)沒(méi)有要求，順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)皆可。對(duì)表中數(shù)據(jù)元素關(guān)鍵字的大小是否有序也沒(méi)有要求，無(wú)論數(shù)據(jù)元素是否按關(guān)鍵字有序均可應(yīng)用。同時(shí)還需要注意，對(duì)線(xiàn)性鏈表只能進(jìn)行順序查找。7.2靜態(tài)查找算法2.有序順序表的順序查找如果在查找之前已知表是按關(guān)鍵字排序的，那么當(dāng)查找失敗時(shí)可以不必再比較到表的另一端就能返回查找失敗的信息，這樣能降低順序查找失敗的平均查找長(zhǎng)度。若表L是按關(guān)鍵字從小到大排列的，查找的順序是從前往后，待查找元素的關(guān)鍵字為key，當(dāng)查找到第i個(gè)元素時(shí)，發(fā)現(xiàn)第i個(gè)元素對(duì)應(yīng)的關(guān)鍵字小于key，但第i+1個(gè)元素對(duì)應(yīng)的關(guān)鍵字大于key，這時(shí)就可以返回查找失敗的信息了，因?yàn)榈趇個(gè)元素之后的元素的關(guān)鍵字均大于key，所以表中不存在關(guān)鍵字為key的元素。7.2靜態(tài)查找算法圓形節(jié)點(diǎn)表示有序順序表中存在的元素矩形節(jié)點(diǎn)稱(chēng)為失敗節(jié)點(diǎn)7.2靜態(tài)查找算法折半查找折半查找(BinarySearch)查找又稱(chēng)為二分查找，它的效率較高。但有一定的條件限制：要求線(xiàn)性表必須采用順序存儲(chǔ)結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序。1.折半查找的基本思想首先將給定值key與有序表中間位置元素的關(guān)鍵字相比較，若相等，則查找成功，返回該元素的存儲(chǔ)位置；若不等，則所需查找的元素只能在中間元素以外的前半部分或后半部分中，然后在縮小的范圍中繼續(xù)進(jìn)行同樣的查找，如此重復(fù)直到找到為止，或者確定表中沒(méi)有所需要查找的元素，查找不成功，返回查找失敗的信息。7.2靜態(tài)查找算法2.折半查找的具體操作過(guò)程假設(shè)順序表ST是有序的。設(shè)兩個(gè)指針，一個(gè)是low，指示查找表第一個(gè)記錄的位置；另一個(gè)是high，指示查找表最后一個(gè)記錄的位置。初始時(shí)low=0，high=ST.TableLen-1。設(shè)要查找的記錄的關(guān)鍵字為key。當(dāng)low<=high時(shí)，反復(fù)執(zhí)行以下步驟：(1)計(jì)算中間記錄的位置mid，mid=(low+high)/2；7.2靜態(tài)查找算法(2)將待查記錄的關(guān)鍵字key和r[mid].key進(jìn)行比較：①若key==r[mid].key，查找成功，mid所指元素即為要查找的元素。②若key<r[mid].key，說(shuō)明若存在要查找的元素，該元素一定在查找表的前半部分。修改查找范圍的上界：high=mid-1，轉(zhuǎn)①；③若key>r[mid].key，說(shuō)明若存在要查找的元素，該元素一定在查找表的后半部分。修改查找范圍的下界：low=mid+1，轉(zhuǎn)①；(3)重復(fù)以上過(guò)程，當(dāng)low>high時(shí)，表示查找失敗。7.2靜態(tài)查找算法【例7.1】已知由11個(gè)數(shù)據(jù)元素構(gòu)成的有序表(關(guān)鍵字即為數(shù)據(jù)元素的值)如下：{4，12，20，21，35，58，63，77，81，87，98}現(xiàn)要查找值為21的數(shù)據(jù)元素。假設(shè)指針low和high分別指示待檢查元素所在范圍的下界和上界，指針mid指示區(qū)間的中間位置，即mid=(low+high)/2=(0+10)/2=5。則在此例中，low和high的初值分別為0和10，即[0,10]為待檢查范圍。

7.2靜態(tài)查找算法key=21時(shí)的查找過(guò)程01234567891041220

21

355863

77

81

8798↑low↑mid

↑high查找范圍中間位置的數(shù)據(jù)元素的關(guān)鍵字與給定值key相比較，因?yàn)榍罢叽?，說(shuō)明待查找元素若存在，必在區(qū)間[low,mid-1]的范圍內(nèi)，令指針high指向第mid-1個(gè)元素，重新求得mid=(0+4)/2=2。012345678910412

20

21

35586377

81

8798↑low

↑mid

↑high7.2靜態(tài)查找算法仍以ST.elem[mid].key和key相比，因?yàn)镾T.elem[mid].key<key，說(shuō)明待檢查元素若存在，必在[mid+1,high]范圍內(nèi)，則令指針low指向第mid+1個(gè)元素，求得mid的新值為3；ST.elem[mid].key和key相等，則查找成功，所查元素在表中的序號(hào)等于指針mid的值。01234567891041220213558

63

77

818798

↑low↑high

↑mid7.2靜態(tài)查找算法3.折半查找算法intBinary_Search(SSTableL,ElemTypekey)

/*在有序表L中查找關(guān)鍵字為key的元素，若存在則返回其位置，不存在則返回-1*/{

intlow=0,high=L.TableLen-1;//置區(qū)間初值

intmid；

while(low<=high)

{

mid=(low+high)/2;/*取中間位置*/7.2靜態(tài)查找算法

if(L.elem[mid].key==key) returnmid;/*查找成功返回所在位置*/

elseif(L.elem[mid].key>key)high=mid-1;/*從前半部分繼續(xù)查找*/

elselow=mid+1;/*從后半部分繼續(xù)查找*/

}

return-1;/*順序表中不存在待查元素*/}7.2靜態(tài)查找算法4.折半查找的性能分析長(zhǎng)方形節(jié)點(diǎn)為判定樹(shù)外部節(jié)點(diǎn)，由判定樹(shù)中所有節(jié)點(diǎn)的空指針域上的指針指向它葉節(jié)點(diǎn)表示查找不成功的情況圓形節(jié)點(diǎn)表示一個(gè)記錄，節(jié)點(diǎn)中的值為該記錄在表中的位置7.2靜態(tài)查找算法4.折半查找的性能分析判定樹(shù)特點(diǎn)：中序序列是一個(gè)有序序列，為二分查找的初始序列，所有的根節(jié)點(diǎn)值大于左子樹(shù)而小于右子樹(shù)。與根節(jié)點(diǎn)比較時(shí)若相等則查找成功，若待找的值小于根節(jié)點(diǎn)，則進(jìn)入左子樹(shù)繼續(xù)查找，否則進(jìn)入右子樹(shù)查找，若找到葉子結(jié)點(diǎn)時(shí)還沒(méi)有找到所需元素，則查找失敗。7.2靜態(tài)查找算法查找成功時(shí)的查找長(zhǎng)度為從根節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)，而查找失敗時(shí)的查找長(zhǎng)度為從根節(jié)點(diǎn)到對(duì)應(yīng)失敗節(jié)點(diǎn)的父節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)。故用折半查找法查找到給定值的比較次數(shù)最多不會(huì)超過(guò)樹(shù)的高度，時(shí)間復(fù)雜度為O(log2n)。折半查找的優(yōu)點(diǎn)是比較次數(shù)較順序查找要少，查找速度較快，執(zhí)行效率較高；缺點(diǎn)是表的存儲(chǔ)結(jié)構(gòu)只能為順序存儲(chǔ)，不能為鏈?zhǔn)酱鎯?chǔ)，且表中元素必須是有序的。7.3動(dòng)態(tài)查找表7.3動(dòng)態(tài)查找表二叉排序樹(shù)1.二叉排序樹(shù)的定義二叉排序樹(shù)(BinarySortTree)又稱(chēng)二叉查找樹(shù)。定義：或者是一棵空樹(shù)，或者是具有如下特性的二叉樹(shù)：若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；它的左、右子樹(shù)也分別是二叉排序樹(shù)。7.3動(dòng)態(tài)查找表2.二叉排序樹(shù)的存儲(chǔ)定義二叉排序樹(shù)用二叉鏈表來(lái)存儲(chǔ)，其存儲(chǔ)結(jié)構(gòu)描述如下：typedefintKeyType;typedefstructBTNode{

KeyTypekey;/*關(guān)鍵字域*/

structBTNode*lchild,*rchild; /*左、右孩子指針*/}BTNode,*BiTree7.3動(dòng)態(tài)查找表3.二叉排序樹(shù)的查找算法二叉排序樹(shù)的查找是從根節(jié)點(diǎn)開(kāi)始，沿某一個(gè)分支逐層向下進(jìn)行比較：（1）若查找樹(shù)為空，查找失敗，結(jié)束查找過(guò)程。（2）查找樹(shù)非空，將給定值key與查找樹(shù)的根結(jié)點(diǎn)關(guān)鍵字比較。（3）若相等，查找成功，結(jié)束查找過(guò)程，否則：①

當(dāng)key小于根結(jié)點(diǎn)關(guān)鍵字，查找將在以左孩子為根的子樹(shù)上繼續(xù)進(jìn)行，轉(zhuǎn)（1）②

當(dāng)key大于根結(jié)點(diǎn)關(guān)鍵字，查找將在以右孩子為根的子樹(shù)上繼續(xù)進(jìn)行，轉(zhuǎn)（1）7.3動(dòng)態(tài)查找表3.二叉排序樹(shù)的查找算法算法7.3二叉排序樹(shù)的遞歸查找算法BiTreeSearchBST(BTNodeT,KeyTypekey)/*在二叉排序樹(shù)T中查找關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功返回指向該數(shù)據(jù)元素節(jié)點(diǎn)的指針，否則返回空指針*/{if(!T||key==T->key))return(T);elseif(key<T->key))return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}7.3動(dòng)態(tài)查找表算法7.4改進(jìn)的二叉排序樹(shù)查找算法BTNode*SearchBST(BTNode*T,KeyTypekey,int*f)/*若查找成功，則返回該數(shù)據(jù)元素節(jié)點(diǎn)并使*f=1;否則返回查找路徑上訪(fǎng)問(wèn)的最后一節(jié)點(diǎn)并使*f=0*/{BTNode*p,*pre;

*f=0;if(!T){*f=0;returnT;}

p=T;pre=T; /*pre指向p的雙親*/7.3動(dòng)態(tài)查找表

while(p!=NULL&&key!=p->key)

{pre=p;

if(key<p->key)p=p->lchild; /*在左子樹(shù)中查找*/

elsep=p->rchild;/*在右子樹(shù)中查找*/

}

if(p!=NULL&&key==p->key){*f=1;returnp;} /*查找成功*/

else{*f=0;returnpre;}/*查找失敗*/}7.3動(dòng)態(tài)查找表4.二叉排序樹(shù)的插入算法二叉排序樹(shù)是一種動(dòng)態(tài)查找表，樹(shù)的結(jié)構(gòu)通常不是一次生成的，而是在查找的過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的節(jié)點(diǎn)時(shí)再進(jìn)行插入。由于二叉排序樹(shù)是遞歸定義的，因此插入節(jié)點(diǎn)的過(guò)程是，若原二叉樹(shù)為空，則直接插入節(jié)點(diǎn)；否則，若關(guān)鍵字key小于根節(jié)點(diǎn)關(guān)鍵字，則插入到左子樹(shù)中，若關(guān)鍵字key大于根節(jié)點(diǎn)關(guān)鍵字，則插入到右子樹(shù)中。二叉排序樹(shù)的插入見(jiàn)算法7.5中的描述。7.3動(dòng)態(tài)查找表算法7.3二叉排序樹(shù)的插入算法BTNode*InsertBST(BTNode*T,KeyTypekey)/*當(dāng)二叉排序樹(shù)T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，插入key返回二叉排序樹(shù)的根結(jié)點(diǎn)。*/{BTNode*p,*s; intf=0; p=SearchBST(T,key,&f); if(!f)/*查找不成功*/ {s=(BTNode*)malloc(sizeof(BTNode)); s->key=key;7.3動(dòng)態(tài)查找表s->lchild=s->rchild=NULL;if(!p) returns;/*插入為根結(jié)點(diǎn)*/elseif(key<p->key)p->lchild=s; elsep->rchild=s; } returnT;}7.3動(dòng)態(tài)查找表5.二叉排序樹(shù)的查找分析二叉排序樹(shù)查找最壞的情況下，需要的查找時(shí)間取決于樹(shù)的深度，當(dāng)二叉排序樹(shù)接近于滿(mǎn)二叉樹(shù)時(shí)，其深度為O(log2n)+l，最壞情況下的查找時(shí)間為O(log2n)，與折半查找是同數(shù)量級(jí)的；當(dāng)二叉排序樹(shù)單枝樹(shù)時(shí)，其深度為n，最壞情況下查找時(shí)間為O(n)，與順序查找屬于同一數(shù)量級(jí)。為了保證二叉排序樹(shù)查找有較高的查找速度，希望該二叉樹(shù)接近于滿(mǎn)二叉樹(shù)，也即希望二叉樹(shù)的每一個(gè)結(jié)點(diǎn)的左、右子樹(shù)盡量相等。7.4哈希表7.4哈希表哈希表的定義哈希(Hash)法又稱(chēng)為散列法、雜湊法或關(guān)鍵字地址計(jì)算法，相應(yīng)的表稱(chēng)為哈希表、散列表或雜湊表等，哈希表是一種重要的查找技術(shù)，既適用于靜態(tài)查找，又適用于動(dòng)態(tài)查找，并且查找效率非常高。哈希表的構(gòu)造方法：對(duì)于存儲(chǔ)的m個(gè)數(shù)據(jù)元素，確定一個(gè)稱(chēng)為哈希函數(shù)的函數(shù)H(key)，將要存儲(chǔ)元素的關(guān)鍵字key按照該函數(shù)進(jìn)行計(jì)算后得到該元素的存儲(chǔ)地址，并將該數(shù)據(jù)元素存儲(chǔ)到存儲(chǔ)地址對(duì)應(yīng)的內(nèi)存單元中。7.4哈希表例如，數(shù)據(jù)元素集合為{25，6，1，20，22，27，10，13，41}，內(nèi)存長(zhǎng)度為100，取H(key)=k，在100個(gè)內(nèi)存單元中只存放9個(gè)元素，利用率很低。若將內(nèi)存單元的個(gè)數(shù)減少為11，取哈希函數(shù)H(key)=key%n，則有：H(25)=25%11=3，H(6)=6%11=6，H(1)=1%11=1，H(20)=20%11=9，H(22)=22%11=0，H(27)=27%11=5，H(10)=10%11=10，H(13)=13%11=2，H(41)=41%11=801234567891022113252764120107.4哈希表如果內(nèi)存單元的個(gè)數(shù)為10，仍取哈希函數(shù)H(key)=key%n，則有：H(25)=25%10=5，H(6)=6%10=6，H(1)=1%10=1，H(20)=20%10=0，H(22)=22%10=2，H(27)=27%10=7，H(10)=10%10=0，H(13)=13%10=3，H(41)=41%10=1此時(shí)，有H(1)=H(41)=1，H(20)=H(10)=0，產(chǎn)生了沖突。7.4哈希表在構(gòu)造哈希表時(shí)，對(duì)于兩個(gè)不同的關(guān)鍵字key1≠key2，有H(key1)=H(key2)，即兩個(gè)不同記錄需要存放在同一個(gè)存儲(chǔ)位置中，這種現(xiàn)象稱(chēng)為沖突(Collision)具有相同函數(shù)值的關(guān)鍵字對(duì)該哈希函數(shù)來(lái)說(shuō)稱(chēng)作同義詞在構(gòu)造哈希表時(shí)，除了需要選擇一個(gè)盡可能少產(chǎn)生沖突的哈希函數(shù)之外，還需要找到一種處理沖突的方法7.4哈希表哈希函數(shù)的構(gòu)建1.構(gòu)造哈希函數(shù)的注意事項(xiàng)(1)哈希函數(shù)的定義必須包含全部需要存儲(chǔ)的關(guān)鍵字，而值域的范圍則依賴(lài)于哈希表的大小或地址范圍；(2)哈希函數(shù)計(jì)算出來(lái)的地址應(yīng)該能等概率地、均勻地分布在整個(gè)地址空間，從而減少?zèng)_突的發(fā)生；(3)哈希函數(shù)應(yīng)盡量簡(jiǎn)單，能夠在較短的時(shí)間內(nèi)計(jì)算出任一關(guān)鍵字對(duì)應(yīng)的哈希地址。7.4哈希表2.常見(jiàn)的哈希函數(shù)(1)直接定址法直接取關(guān)鍵字的某個(gè)線(xiàn)性函數(shù)值為散列地址，散列函數(shù)為：H(key)=a×key+b(a、b為常數(shù))例如：關(guān)鍵字集合{10，20，40，50，60，90}，選取哈希函數(shù)為H(key)=key/10，構(gòu)造的哈希表：0123456789102040506090直接定址法計(jì)算簡(jiǎn)單，不會(huì)產(chǎn)生沖突，適合關(guān)鍵字分布基本連續(xù)的情況，若關(guān)鍵字分布不連續(xù)，將造成存儲(chǔ)空間的浪費(fèi)。7.4哈希表(2)除留取余法該方法是將關(guān)鍵字key除以一個(gè)不大于哈希表長(zhǎng)度的正整數(shù)p，將所得余數(shù)作為哈希表的地址。通常情況下，為了有效減少哈希沖突，確定哈希表長(zhǎng)度m后，p選取不大于m的最大的質(zhì)數(shù)，利用哈希函數(shù)H(key)=key%p把關(guān)鍵字轉(zhuǎn)換成哈希地址。例如，元素集合{78，7，99，24，25，53，59，19}，若m=11，當(dāng)p取11時(shí)，不產(chǎn)生哈希沖突；但當(dāng)p取10時(shí)，就會(huì)產(chǎn)生2次哈希沖突；當(dāng)p取7時(shí)，就會(huì)產(chǎn)生3次沖突。7.4哈希表3.選用哈希函數(shù)要考慮的因素(1)計(jì)算哈希函數(shù)所需的時(shí)間(2)關(guān)鍵字的長(zhǎng)度(3)哈希表的大小(4)關(guān)鍵字的分布情況(5)記錄的查找頻率7.4哈希表處理沖突方法處理沖突是為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址處理沖突方法開(kāi)放定址法、鏈地址法、再哈希法、建立公共溢出區(qū)1.開(kāi)放定址法為產(chǎn)生沖突的地址H(key)求地址序列：

H1,H2,…,Hk

其中：1≤k≤m-1Hi=(H(key)+di)%m，

其中：H(key)為哈希函數(shù); m為哈希表長(zhǎng);di為增量序列7.4哈希表開(kāi)放定址法對(duì)增量di的兩種取法(1)線(xiàn)性探測(cè)法當(dāng)di=1，2，…，m-1時(shí)稱(chēng)為線(xiàn)性探測(cè)法沖突發(fā)生時(shí)，順序查看表的下一單元（當(dāng)探測(cè)到表尾地址m-1時(shí)，下一個(gè)探測(cè)地址是表首地址0）直到找出一個(gè)空閑單元，存放該關(guān)鍵字。線(xiàn)性探測(cè)法可能會(huì)使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址中，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素就爭(zhēng)奪第i+2個(gè)哈希地址的元素的地址，以此類(lèi)推，從而造成大量元素在相鄰的哈希地址上“聚集”(或堆積)起來(lái)，大大降低了查找效率。7.4哈希表例如，哈希表表長(zhǎng)m為10，以關(guān)鍵字的末尾數(shù)字作為哈希地址(即H(key)=key%10)，依次插入45、22、13、65、29、42、79、2共8個(gè)記錄。若發(fā)生沖突則采用線(xiàn)性探測(cè)法。H1=(H(65)+1)%10=6H2=(H(42)+2)%10=4H1=(H(79)+1)%10=0H5=(H(2)+5)%10=701234567892213456529427927.4哈希表(2)平方探測(cè)再散列(二次探測(cè)法)di=12，-12，22，-22，…，k2，-k2，其中k≤m/2，m必須是一個(gè)可以表示成4k+3的質(zhì)數(shù)時(shí)，稱(chēng)為平方探測(cè)法，又稱(chēng)二次探測(cè)法。平方探測(cè)法是一種較好的處理沖突的方法，可以避免出現(xiàn)“堆積”問(wèn)題，它的缺點(diǎn)是不能探測(cè)到哈希表上的所有單元，但至少能探測(cè)到一半的單元。7.4哈希表例如，若有關(guān)鍵字集合{47，7，29，11，16，92，22，8，3}，哈希表表長(zhǎng)m為11，哈希函數(shù)為H(key)=key%11，用二次探測(cè)法處理沖突。012345678910114792167292283關(guān)鍵字3，H(3)=3，哈希地址發(fā)生沖突，有H1=(H(3)+12)%11=4，仍然沖突；H2=(H(3)-12)%11=2，找到空的哈希地址，將3存入。7.4哈希表2.鏈地址法鏈地址法是把具有相同散列地址的關(guān)鍵字(它們都是同義詞)記錄用一個(gè)單鏈表鏈在一起，組成同義詞鏈表，用此方法解決散列過(guò)程中出現(xiàn)的沖突問(wèn)題。這時(shí)，若有m個(gè)散列地址，鏈地址法中就要設(shè)置m個(gè)同義詞鏈表，每個(gè)同義詞鏈表的標(biāo)頭指針被集中存放在一個(gè)一維數(shù)組中。關(guān)鍵字序列為{32，27，23，1，29，20，84，40，55，11，10，66}，由于數(shù)據(jù)元素集合中有12個(gè)元素，故哈希表的內(nèi)存單元個(gè)數(shù)m為13，哈希函數(shù)為H(key)=key%13，用拉鏈法處理沖突7.4哈希表2.鏈地址法7.4哈希表哈希表的查找和性能在哈希表上進(jìn)行查找的過(guò)程和構(gòu)造哈希表的過(guò)程基本一致。對(duì)于一個(gè)給定的關(guān)鍵字key，根據(jù)哈希函數(shù)可以計(jì)算出初始哈希地址Addr=Hash(key)，然后按以下步驟執(zhí)行。(1)檢測(cè)查找表中地址為Addr的位置上是否有記錄，若沒(méi)有記錄，返回查找失??；若有記錄，比較它與key的值；若相等，返回查找成功標(biāo)志，否則執(zhí)行步驟(2)。(2)用給定的處理沖突的方法計(jì)算“下一個(gè)哈希地址”，并把Addr置為此地址，轉(zhuǎn)入步驟(1)。7.4哈希表例如，有關(guān)鍵字序列{32，27，23，1，29，20，84，40，55，11，10，67}，按哈希函數(shù)H(key)=key%13和線(xiàn)性探測(cè)法處理沖突得到的哈希表L。給定值84的查找過(guò)程：首先求得哈希地址H(84)=6，因L[6]不空且L[6]≠84，則找到第一次處理沖突后的地址H1=(6+1)%13=7，而L[7]不空且L[7]≠84，則找到第二次處理沖突后的地址H2=(6+2)%13=8，L[8]不空且L[8]=84，表示查找成功，返回記錄在表中序號(hào)801234567891011122701294055322084672311107.4哈希表哈希表的查找和性能從哈希表的查找可見(jiàn)：(1)雖然哈希表在關(guān)鍵字和記錄的存儲(chǔ)位置之間建立了直接映像，但由于“沖突”的產(chǎn)生，使得哈希表的查找過(guò)程仍然是一個(gè)給定值與關(guān)鍵字進(jìn)行比較的過(guò)程。因此，仍需以比較次數(shù)來(lái)衡量哈希表的查找效率。(2)查找過(guò)程中需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于下列三個(gè)因素：哈希函數(shù)、處理沖突的方法和哈希表的裝填因子。7.5本章小結(jié)7.5本章小結(jié)線(xiàn)性表的查找順序查找、折半查找的基本思想折半查找對(duì)存儲(chǔ)結(jié)構(gòu)及關(guān)鍵字的要求樹(shù)的查找二叉排序樹(shù)和平衡二叉樹(shù)的定義和特點(diǎn)二叉排序樹(shù)的插入、建立和查找算法平衡二叉樹(shù)的插入時(shí)平失衡的調(diào)整的基本思想哈希表哈希表、哈希函數(shù)、哈希地址等有關(guān)概念哈希函數(shù)的選取原則及產(chǎn)生沖突的原因采用線(xiàn)性探測(cè)法、平方探測(cè)法和鏈地址法解決沖突時(shí)，哈希表的建表方法、查找過(guò)程第8章排序教學(xué)要求相關(guān)知識(shí)點(diǎn)排序的定義和基本術(shù)語(yǔ)各種內(nèi)部排序方法的基本思想、算法特點(diǎn)、排序過(guò)程和它們的時(shí)間復(fù)雜度分析穩(wěn)定排序方法和不穩(wěn)定排序方法的定義及判斷學(xué)習(xí)重點(diǎn)簡(jiǎn)單插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序的排序方法、算法描述和性能分析；各種排序方法的比較目錄插入排序算法交換排序算法選擇排序算法3排序的基本概念124歸并排序算法5排序算法的比較6本章小結(jié)78.1排序的基本概念8.1排序的基本概念排序的基本概念1.排序

假設(shè)一組含有n個(gè)記錄的序列為{r0，r1，…，rn-1}，它們相應(yīng)的關(guān)鍵字序列為{k0，k2，…，kn-1}，這些關(guān)鍵字相互之間可以進(jìn)行比較，使得它們滿(mǎn)足以下的非遞減(或非遞增)的關(guān)系，即n個(gè)記錄的序列重新排列成一個(gè)按關(guān)鍵字有序的序列，上述操作即為排序。本章介紹的算法均以升序?yàn)槔?，降序方法?lèi)似，只需要將算法中的大于符號(hào)和小于符號(hào)互換即可。8.1排序的基本概念2.排序算法的穩(wěn)定性

如果在數(shù)據(jù)元素序列中有兩個(gè)數(shù)據(jù)元素ri和rj，它們的關(guān)鍵字ki==kj，且在排序之前，記錄ri排在rj前面。如果在排序之后，記錄ri仍在rj的前面,則稱(chēng)這個(gè)排序方法是穩(wěn)定的,否則稱(chēng)這個(gè)排序方法是不穩(wěn)定的。3.內(nèi)排序與外排序內(nèi)排序是指在排序期間數(shù)據(jù)元素全部存放在內(nèi)存的排序；外排序是指在排序期間全部元素個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過(guò)程的要求，不斷在內(nèi)存與外存之間移動(dòng)的排序。8.1排序的基本概念4.記錄存儲(chǔ)描述數(shù)據(jù)元素之間按照關(guān)鍵字的“大小”進(jìn)行比較，并且這個(gè)“大小”的含義是廣義的，可以理解為關(guān)鍵字之間存在某種“領(lǐng)先”的關(guān)系。數(shù)據(jù)元素稱(chēng)為“記錄”，可用C語(yǔ)言描述如下：typedefintKeyType;/*定義關(guān)鍵字類(lèi)型為整型*/typedefstruct{

KeyTypekey; /*關(guān)鍵字項(xiàng)*/

InfoTypeotherinfo; /*其他數(shù)據(jù)項(xiàng)*/}RcdType; /*記錄類(lèi)型*/8.2插入排序算法8.2插入排序算法插入排序（InsertionSort）的基本思想是，每次將一個(gè)待排序的記錄，按其關(guān)鍵字的大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。直接插入排序直接插入排序（StraightInsertionSort）的基本方法是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。8.2插入排序算法直接插入排序?yàn)榱藴p少排序過(guò)程中元素的比較次數(shù)，在插入排序算法中引入r[0]作為哨兵，其主要作用是：(1)在進(jìn)入查找插入位置循環(huán)之前，它保存第i個(gè)記錄r[i]的副本，使不至于因記錄后移而丟失r[i]的內(nèi)容。(2)在查找插入位置的過(guò)程中避免數(shù)組下標(biāo)出界。一旦出界，因?yàn)閞[0].key和自己相比較，循環(huán)判定條件不成立，使得查找插入位置的循環(huán)過(guò)程結(jié)束，從而避免了在該循環(huán)內(nèi)每一次都要檢測(cè)數(shù)組下標(biāo)是否越界。引入哨兵后使得測(cè)試查找循環(huán)條件的時(shí)間大約減少了一半，所以對(duì)于記錄數(shù)較大的序列所節(jié)約的時(shí)間就相當(dāng)可觀了。8.2插入排序算法直接插入排序算法voidInsertSort(RecordTyper[],intn)//對(duì)表r中的第1到第n個(gè)記錄進(jìn)行直接插入排序，r[0]為哨兵{ inti,j; for(i=2;i<=n;i++)

//初始r[1]為有序序列，i從2開(kāi)始 {r[0]=r[i];/*設(shè)置監(jiān)視哨*/ j=i-1; while(r[0].key<r[j].key) {r[j+1]=r[j];j--;}/*記錄后移*/ r[j+1]=r[0];//把r[0]中原記錄插入正確位置 }}8.2插入排序算法直接插入排序算法【例8.1】已知序列{70，83，100，65，65}，給出采用直接插入排序算法做升序排列的排序過(guò)程（小括號(hào)內(nèi)的是哨兵，方括號(hào)內(nèi)的數(shù)據(jù)序列為有序序列）。初始時(shí)：(哨兵)[70] 83 100 65 65第1趟: (83) [70 83] 100 65 65第2趟: (100) [70 83 100] 65

65第3趟: (65) [65 70 83 100] 65第4趟: (65) [65 65 70 83 100]8.2插入排序算法算法分析設(shè)待排序元素個(gè)數(shù)為n,則該算法的主程序執(zhí)行n-1趟。排序關(guān)鍵字比較次數(shù)和元素移動(dòng)次數(shù)與元素排序關(guān)鍵字的初始排列有關(guān)。最好情況下,初始排序關(guān)鍵字已經(jīng)有序，for循環(huán)進(jìn)行一輪關(guān)鍵字比較，內(nèi)循環(huán)中while的條件均不滿(mǎn)足，因此共比較n-1次，移動(dòng)0次，算法的時(shí)間復(fù)雜度為O(n)。8.2插入排序算法最壞情況下，待排序序列完全逆序，for循環(huán)共運(yùn)行n-1次，while循環(huán)總的比較次數(shù)為：2+3+…+n=(n+2)(n-1)/2。因?yàn)榇判蛐蛄型耆嫘?，故需要移?dòng)i-1步，這樣總的移動(dòng)次數(shù)為：1+2+3+…+n-1=n(n-1)/2。平均情況下，比較和移動(dòng)次數(shù)為(n(n-1)/2+(n-1)(n+2)/2)/2=((n-1)(2n+2)/2)/2=(n2-1)/2次。直接插入排序的時(shí)間復(fù)雜度為o(n2)。當(dāng)待排序記錄數(shù)較少且已基本有序時(shí)，使用直接插入排序速度較快。直接插入排序是一種穩(wěn)定的排序方法。8.2插入排序算法折半插入排序當(dāng)待排序的記錄數(shù)很大時(shí)，不宜再用直接插入排序，需要使用更快的排序算法。直接插入排序有兩個(gè)基本操作，比較記錄的關(guān)鍵字和移動(dòng)記錄。折半插入排序?qū)Ρ容^記錄關(guān)鍵字的整個(gè)基本操作進(jìn)行了改進(jìn)。在直接插入排序算法中查找插入位置時(shí)，采用的是順序查找。折半插入排序就是用折半查找方法來(lái)代替直接插入算法中順序查找方法。8.2插入排序算法算法8.2折半插入排序算法voidBinarySort(RecordTyper[],intn) /*對(duì)順序表L進(jìn)行折半插入排序*/{inti,j; intlow,high,m; for(i=1;i<=n;i++) {r[0]=r[i]; /*將要插入的元素置于r[0]中*/ low=1; high=i-1; while(low<=high)/*在有序段中查找*/ {m=(low+high)/2; /*使用折半查找*/8.2插入排序算法if(r[0].key<r[m].key) /*與有序段前半段的最大值相比較*/ high=m-1; elselow=m+1; } for(j=i-1;j>=high+1;--j)/*移動(dòng)元素*/ r[j+1]=r[j]; r[high+1]=r[0]; }}8.2插入排序算法【例8.2】對(duì)數(shù)據(jù)序列{70，83，100，65，65}給出折半插入排序的操作過(guò)程。初始值：[70]，83，100，65，65第1趟：[70，83]，100，65，65第2趟：[70，83，100]，65，65第3趟：[65，70，83，100]，650第4趟：[65，65，70，83，100]8.2插入排序算法算法8.2折半插入排序算法折半插入排序所需的存儲(chǔ)空間和直接插入排序一樣與直接插入排序唯一不同的就是在有序段搜索插入位置時(shí)，使用折半查找方法，關(guān)鍵字之間的比較次數(shù)減少了，但是記錄的移動(dòng)次數(shù)不變，故算法的時(shí)間復(fù)雜度同樣為O(n2)。折半插入排序法也是一種穩(wěn)定的排序方法。8.2插入排序算法希爾排序希爾排序（ShellSort）又稱(chēng)為縮小增量排序。希爾排序的基本思想(1)將整個(gè)待排記錄序列按下標(biāo)的一定增量分成若干個(gè)子序列，n=n1+n2+……nk；(2)分別對(duì)每個(gè)子序列進(jìn)行直接插入排序，使得整個(gè)序列基本有序；(3)將增量縮小，劃分子序列，分別進(jìn)行直接插入排序；(4)如此重復(fù)進(jìn)行，最后對(duì)整個(gè)序列進(jìn)行一次直接插入排序。8.2插入排序算法算法8.3希爾排序算法voidShellSort(RecordTyper[],intn)//對(duì)表r中第1到第n個(gè)記錄進(jìn)行希爾排序，r[0]為哨兵{inti,j,d; for(d=n/2;d>0;d=d/2)/*初始增量為n/2，每次縮小增量值為d/2*/{for(i=d+1;i<=n;i++) {r[0]=r[i]; j=i-d;//前后記錄位置的增量是d,而不是1/*將r[i]插入有序增量子表*/8.2插入排序算法while(j>=0&&r[0].key<r[j].key)//將r[i]插入有序子表 {r[j+d]=r[j];j=j-d;}//查找插入位置r[j+d]=r[0];/*插入*/}}}8.2插入排序算法對(duì)序列{70，83，100，65，10，32，7，65，9}按增量序列{3，2，1}進(jìn)行希爾排序的過(guò)程。8.2插入排序算法希爾排序希爾排序算法的分析是一個(gè)復(fù)雜的問(wèn)題，因?yàn)樗臅r(shí)間是所取“增量”序列的函數(shù)。到目前為止尚未有人求得一種最好的增量序列，但大量的研究已得出一些局部結(jié)論。注意：增量序列的取法應(yīng)使增量序列中的值沒(méi)有除1之外的公因子，并且最后一個(gè)增量值必須等于1。希爾排序算法在空間上只需要一個(gè)輔助單元，所以空間復(fù)雜度S(n)=O(1)。希爾排序比較適合處理大批量的雜亂無(wú)章的數(shù)據(jù)序列。希爾排序算法是不穩(wěn)定的。8.3交換排序算法8.3交換排序算法冒泡排序算法的基本思想：在n個(gè)元素中，將從頭開(kāi)始相鄰的兩個(gè)記錄的關(guān)鍵字進(jìn)行比較，若大小順序與要求的順序正好相反(即逆序)，則將兩個(gè)記錄交換位置，然后向下移動(dòng)一個(gè)記錄，再依次比較下兩個(gè)相鄰記錄的關(guān)鍵字。以此類(lèi)推，直至最后兩個(gè)相鄰記錄的關(guān)鍵字進(jìn)行比較為止。上述過(guò)程稱(chēng)作第一趟冒泡排序，結(jié)果使關(guān)鍵字最大(當(dāng)要求升序排序時(shí))的記錄被安置到最后一個(gè)記錄的位置上。然后進(jìn)行第二趟冒泡排序。整個(gè)排序過(guò)程需要進(jìn)行k(1≤k<n)趟冒泡排序，判斷冒泡排序結(jié)束的條件是“在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作”。8.3交換排序算法算法8.4冒泡排序算法voidBubble_sort(RecordTyper[],intn)/*對(duì)表r第1個(gè)到第n個(gè)記錄進(jìn)行冒泡排序，r[0]為臨時(shí)交換空間*/{inti,j;intisExcheng;/*交換標(biāo)志*/

for(i=1;i<n;i++){isExcheng=0;/*isExcheng=0為未交換*/

for(j=1;j<=n-i;j++){if(r[j].key>r[j+1].key)//如前者大于后，交換{r[0]=r[j+1];r[j+1]=r[j];r[j]=r[0];

isExcheng=1;/*isExcheng=1為發(fā)生交換*/}}if(isExcheng==0)break;/*未交換，排序結(jié)束*/}}8.3交換排序算法【例8.4】給出對(duì)序列{70，83，100，65，65}進(jìn)行冒泡排序的過(guò)程。初始時(shí)

70 83 100 65 65第1趟 70 83 65 65

100第2趟 70 65 65

83第3趟 65 65

70第4趟 65 658.3交換排序算法冒泡排序若初始序列為“正序”序列，則只需進(jìn)行一趟排序，在排序過(guò)程中進(jìn)行n-1次關(guān)鍵字間的比較，且不移動(dòng)記錄；反之，若初始序列為“逆序”序列，則需進(jìn)行n-1趟排序，需進(jìn)行次比較，并作等量級(jí)的記錄移動(dòng)?？偟臅r(shí)間復(fù)雜度為T(mén)(n)=O(n2)。該算法僅需要一個(gè)交換記錄的存儲(chǔ)空間，因此算法的空間復(fù)雜度為S(n)=O(1)。冒泡排序是穩(wěn)定的。8.3交換排序算法快速排序(1)快速排序的基本思想任取待排序的n個(gè)記錄中的某個(gè)記錄作為基準(zhǔn)，通過(guò)一趟排序，將待排序記錄分成左右兩個(gè)子序列，左子序列記錄的關(guān)鍵字均小于或等于該基準(zhǔn)記錄的關(guān)鍵字，右子序列記錄的關(guān)鍵字均大于或等于該基準(zhǔn)記錄的關(guān)鍵字，從而得到該記錄最終排序的位置，然后該記錄不再參加排序，此一趟排序稱(chēng)為第一趟快速排序。然后對(duì)所分的左右子序列分別重復(fù)上述方法，直到所有的記錄都處在它們的最終位置，此時(shí)排序完成。8.3交換排序算法(2)快速排序的過(guò)程設(shè)待排序序列為r[s]到r[t]，為了實(shí)現(xiàn)一次劃分，可設(shè)置兩個(gè)指針low和high，它們的初值分別為s和t。以r[s]為基準(zhǔn)，在劃分的過(guò)程中：①

首先從high端開(kāi)始，依次向前掃描，并將掃描到的每一個(gè)記錄的關(guān)鍵字同基準(zhǔn)記錄r[s]的關(guān)鍵字進(jìn)行比較，直到r[high].key<r[s].key時(shí)，將r[high]賦值到low所指的位置；②

然后從low端開(kāi)始依次向后掃描，并將掃描到的每一個(gè)記錄的關(guān)鍵字同r[s]的關(guān)鍵字進(jìn)行比較，直到r[low].key>r[s].key時(shí)，將r[low]賦值到high所指的位置;8.3交換排序算法③如此交替改變掃描方向，重復(fù)第①和②兩個(gè)步驟，從兩端各自向中間位置靠攏，直到low等于或大于high。經(jīng)過(guò)此次劃分后得到的左右兩個(gè)子序列分別為r[s]到r[low-1]和r[low+1]到r[t]。排序首先從r[1..n]開(kāi)始，按上述方法劃分為r[s]到r[low-1]、r[low]和r[low+1]到r[t]三個(gè)序列，然后對(duì)r[s]到r[low-1]和r[low+1]到r[t]分別按上述方法進(jìn)行再次劃分，依次重復(fù)，直到每個(gè)序列只剩一個(gè)元素為止。8.3交換排序算法(3)快速排序算法任意子系列r[low]到r[high]的一趟劃分算法intPartition(RecordTyper[],intlow,inthigh)/*對(duì)表r中的第low到第high個(gè)記錄進(jìn)行一次快速排序的劃分，把關(guān)鍵字小于r[low].key的記錄放在r[low]前面，大于r[low].key的記錄放在r[low]后面*/{r[0]=r[low];/*把r[low]放在r[0]*/while(low<high)/*用r[low]進(jìn)行一趟劃分*/{//在high端,尋找比r[low].key小的記錄放入lowwhile(low<high&&r[high].key>=r[0].key)--high;8.3交換排序算法r[low]=r[high];//在low端,尋找比r[low].key大的記錄放入highwhile(low<high&&r[low].key<=r[0].key)++low;r[high]=r[low];}r[low]=r[0];returnlow;//返回劃分后的基準(zhǔn)記錄的位置}8.3交換排序算法/*快速排序算法*/voidQuicksort(RecordTyper[],intlow,inthigh){intloc;

if(low<high){//對(duì)第low個(gè)到第high個(gè)記錄進(jìn)行一次劃分loc=Partition(r,low,high);Quicksort(r,low,loc-1);//劃分前半?yún)^(qū)Quicksort(r,loc+1,high);//劃分后半?yún)^(qū)}}8.3交換排序算法【例8.5】對(duì)序列{70，83，100，65，65}進(jìn)行快速排序的過(guò)程。8.3交換排序算法8.3交換排序算法在一趟快速排序中，關(guān)鍵字比較的次數(shù)和記錄移動(dòng)的次數(shù)均不超過(guò)n，時(shí)間復(fù)雜度主要取決于遞歸的深度，而深度與記錄初始序列有關(guān)。最壞情況是初始序列已基本有序，則遞歸的深度接近于n，算法時(shí)間復(fù)雜度T(n)=O(n2)。最好情況是初始序列非常均勻，則遞歸的深度接近于n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度log2n+1算法的時(shí)間復(fù)雜度T(n)=O(nlog2n)。空間上，因?yàn)槭怯眠f歸實(shí)現(xiàn)的，所以也要看遞歸的深度。最好情況下S(n)=O(log2n)，最壞情況下S(n)=O(n2)。8.3交換排序算法快速排序算法主要適合于關(guān)鍵字大小分布比較均勻的記錄序列。就平均時(shí)間而言，快速排序是目前被認(rèn)為是最好的一種內(nèi)部排序方法。由于關(guān)鍵字相同的記錄可能會(huì)交換位置，因此快速排序算法是不穩(wěn)定的排序方法。8.4選擇排序算法8.4選擇排序算法選擇排序主要是每一趟從待排序記錄序列中選取一個(gè)關(guān)鍵字最小的記錄，依次放在已排序記錄序列的最后，直至全部記錄排完為止。直接選擇排序

1.基本思想設(shè)A={a1a2.........an}A’={}每次從A中選一個(gè)最小元素，放入A’尾端，直到A為空集。8.4選擇排序算法2.排序過(guò)程設(shè)待排序列為:a1a2.........an

首次在a1..an

中找最小值記錄與a1交換。第二次在a2..an

中找最小值記錄與a2交換；第i次在ai..an

中找最小值記錄與ai交換；第n-1次在an-1..an

中找最小值記錄與an-1交換。8.4選擇排序算法算法8.6直接選擇排序算法voidSelectsort(RecordTyper[],intn)/*對(duì)表r中的第1個(gè)到第n個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，r[0]為臨時(shí)交換空間*/{ inti,j,min;

for(i=1;i<n;i++)

{min=i;//在i到n范圍內(nèi)尋找一個(gè)最小元素并放入r[i]中

for(j=i+1;j<=n;++j)

if(r[min].key>r[j].key)min=j;8.4選擇排序算法if(min!=i)

{r[0]=r[min];r[min]=r[i];r[i]=r[0];}}

}8.4選擇排序算法【例8.6】給出對(duì)整數(shù)序列{70，83，100，65，65}進(jìn)行直接選擇排序的過(guò)程。8.4選擇排序算法直接選擇排序在直接選擇排序中，第一次排序要進(jìn)行n-1次比較，第二次排序要進(jìn)行n-2次比較，第n-1次要進(jìn)行1次比較，所以總的比較次數(shù)為n(n-1)/2。當(dāng)待排序記錄序列為正序時(shí)，不需要移動(dòng)記錄；當(dāng)待排序記錄序列為逆序時(shí)，需要n-1次交換操作，而每次交換操作需移動(dòng)數(shù)據(jù)3次，所以需要3(n-1)次數(shù)據(jù)移動(dòng)操作。所以直接選擇排序算法的時(shí)間復(fù)雜度T(n)=O(n2)。直接選擇排序只需要一個(gè)輔助空間用于交換記錄，對(duì)于儲(chǔ)存空間沒(méi)有過(guò)高的要求，空間復(fù)雜度S(n)=O(1)。另外，直接選擇排序是一種穩(wěn)定的排序方法。8.4選擇排序算法堆排序堆排序是J.Willioms在1964年提出的一種選擇排序方法。堆排序是將記錄序列存儲(chǔ)在一個(gè)一維數(shù)組空間中，并將該序列看成一棵完全二叉樹(shù)中的節(jié)點(diǎn)序列{r1，r2，…，rn}，若編號(hào)分別滿(mǎn)足如下要求：

則稱(chēng)該結(jié)構(gòu)分別為小(頂)堆和大(頂)堆。由此，若上述數(shù)列是堆，則r1必是數(shù)列中的最小值或最大值，故分別稱(chēng)為小(頂)堆或大(頂)堆。8.4選擇排序算法根據(jù)完全二叉樹(shù)的性質(zhì)，當(dāng)n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)由上至下，從左至右編號(hào)后，編號(hào)為i的結(jié)點(diǎn)其左孩子結(jié)點(diǎn)編號(hào)為2i（2i≤n），其右孩子編號(hào)為2i+1（2i+1≤n）。因此，可以借助完全二叉樹(shù)來(lái)描述堆：若完全二叉樹(shù)中任一非葉結(jié)點(diǎn)的值均小于等于（或大于等于）其左、右孩子結(jié)點(diǎn)的值，則從根結(jié)點(diǎn)開(kāi)始按結(jié)點(diǎn)編號(hào)排列所得的結(jié)點(diǎn)序列就是一個(gè)堆。8.4選擇排序算法1.堆排序基本思想(1)先建立一個(gè)小頂堆，即先選得一個(gè)關(guān)鍵字為最小的記錄，然后與序列中的最后一個(gè)記錄交換，即若a1，a2，…，an為堆，則a1最小，將a1和an交換；(2)再對(duì)序列中的前n-1個(gè)記錄進(jìn)行“篩選”，重新將它調(diào)整成為一個(gè)小頂堆，再將堆頂記錄和第n-1個(gè)記錄交換。即將剩余的a1，a2，…，an-1當(dāng)作新的序列，調(diào)整為堆；(3)重復(fù)(1)和(2)，直到所有記錄都調(diào)整完為止。8.4選擇排序算法2.建堆的方法(1)將給定序列看成是一棵完全二叉樹(shù)；(2)從第i=n/2個(gè)節(jié)點(diǎn)開(kāi)始，與子樹(shù)節(jié)點(diǎn)相比較，若直接子節(jié)點(diǎn)中較小者小于節(jié)點(diǎn)i，則交換，直到葉節(jié)點(diǎn)或不再交換；(3)i=i-1，重復(fù)(2)直到i=1。8.4選擇排序算法算法8.7調(diào)整建堆算法voidCreatheap(RecordTyper[],intm,intn)/*對(duì)表r中的結(jié)點(diǎn)編號(hào)為m到n的元素進(jìn)行建堆，r[0]為臨時(shí)交換空間*/{ inti,j,flag=0; i=m; j=2*i;/*j為i的左孩子*/ r[0]=r[i]; while(j<=n&&flag!=1)/*沿值小的分支篩選*/ { if(j<n&&r[j].key>r[j+1].key) j++;/*選取孩子中值較小的分支*/8.4選擇排序算法 if(r[0].key<r[j].key)flag=1; else{r[i]=r[j];i=j;j=2*i;/*繼續(xù)向下篩選*/r[i]=r[0];} }}8.4選擇排序算法算法8.8堆排序算法voidHeapsort(RecordTypex[],intn)/*對(duì)表r中的第1到第n個(gè)記錄進(jìn)行堆排序，r[0]為臨時(shí)交換空間*/{ inti; for(i=n/2;i>=1;i--) Creatheap(x,i,n);/*初始化堆*/ printf("Outputx[]:"); /*輸出堆頂元素，并將最后一個(gè)元素放到堆頂位置，重新建堆*/

8.4選擇排序算法 for(i=n;i>=1;i--) { printf("%4d",x[1]);/*輸出堆頂元素*/ x[1]=x[i];/*將堆尾元素移至堆頂*/ Creatheap(x,1,i);/*整理堆*/ } printf("\n");}8.4選擇排序算法【例8.7】給出對(duì)整數(shù)序列{70，83，100，65，65}進(jìn)行堆排序的過(guò)程。8.4選擇排序算法堆排序?qū)ι疃葹閗的堆，篩選進(jìn)行的比較次數(shù)至多為2(k-1)；對(duì)n個(gè)關(guān)鍵字要建立深度為log2n+1的堆進(jìn)行的比較的次數(shù)至多為4n；調(diào)整堆頂n-1次，總共進(jìn)行的比較的次數(shù)不超過(guò)2(log2n-1+log2n-2+…+log22)<2n(log2n)因此，堆排序的時(shí)間復(fù)雜度T(n)+O(nlog2n)?？臻g上只需要一個(gè)記錄的輔助空間，因此空間復(fù)雜度S(n)+O(1)。堆排序比較適合于排序數(shù)據(jù)量大且無(wú)序的記錄序列，而不適合于小的記錄序列。堆排序算法是不穩(wěn)定的排序方法。8.5歸并排序算法8.5歸并排序算法歸并排序的基本思想把待排序的記錄序列分成若干個(gè)子序列，先將每個(gè)子序列的記錄排序，再將已排序的子序列合并，得到完全排序的記錄序列。歸并排序可分為多路歸并排序和兩路歸并排序。這里僅對(duì)兩路歸