數(shù)據(jù)結(jié)構(gòu)（Java語言實(shí)現(xiàn)） 課件 陳銳 第7、8章 查找、排序

第7章查找結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS7.1

查找的基本概念7.2靜態(tài)查找7.3動(dòng)態(tài)查找7.6小結(jié)7.4B-樹和B+樹7.5哈希表7.1查找的基本概念1.查找表：是由同一種類型的數(shù)據(jù)元素構(gòu)成的集合。查找表中的數(shù)據(jù)元素是完全松散的，數(shù)據(jù)元素之間沒有直接的聯(lián)系。2.查找：根據(jù)關(guān)鍵字在特定的查找表中找到一個(gè)與給定關(guān)鍵字相同的數(shù)據(jù)元素的操作。如果在表中找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的。。7.1查找的基本概念關(guān)鍵字與主關(guān)鍵字：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值。如果該關(guān)鍵字可以將所有的數(shù)據(jù)元素區(qū)別開來，也就是說可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，則該關(guān)鍵字被稱為主關(guān)鍵字，否則被稱為次關(guān)鍵字。靜態(tài)查找：指的是僅僅在數(shù)據(jù)元素集合中查找是否存在與關(guān)鍵字相等的數(shù)據(jù)元素。在靜態(tài)查找過程中的存儲(chǔ)結(jié)構(gòu)稱為靜態(tài)查找表。動(dòng)態(tài)查找：在查找過程中，同時(shí)在數(shù)據(jù)元素集合中插入數(shù)據(jù)元素，或者在數(shù)據(jù)元素集合中刪除某個(gè)數(shù)據(jù)元素，這樣的查找稱為動(dòng)態(tài)查找。動(dòng)態(tài)查找過程中所使用的存儲(chǔ)結(jié)構(gòu)稱為動(dòng)態(tài)查找表。7.1查找的基本概念學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力平均查找長(zhǎng)度：是指在查找過程中，需要比較關(guān)鍵字的平均次數(shù)，它是衡量查找算法的效率標(biāo)準(zhǔn)。平均查找長(zhǎng)度的數(shù)學(xué)定義為：ASL=。其中，Pi表示查找表中第i個(gè)數(shù)據(jù)元素的概率，Ci表示在找到第i個(gè)數(shù)據(jù)元素時(shí)，與關(guān)鍵字比較的次數(shù)。。7.2靜態(tài)查找學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力publicclassSSTable{DataTypelist[];intlength;finalintMAXSIZE=50;SSTable(intlength)

{list=newDataType[length+1];this.length=length;}}7.2.1順序表的查找順序表的查找是指從表的一端開始，逐個(gè)與關(guān)鍵字進(jìn)行比較，如果某個(gè)數(shù)據(jù)元素的關(guān)鍵字與給定的關(guān)鍵字相等，則查找成功，函數(shù)返回該數(shù)據(jù)元素所在的順序表的位置；否則查找失敗，返回0。7.2靜態(tài)查找學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力publicintSeqSearch(DataTypex)

//在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0

{

inti=1;

while(i<=length&&list[i].key!=x.key)//從順序表的第一個(gè)元素開始比較

i++;

if(i>length)

return0;

else

returni;

}7.2靜態(tài)查找publicintSeqSearch2(DataTypex)

//設(shè)置監(jiān)視哨list[0]，在順序表中查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0

{

inti=length;

list[0]=x;//將關(guān)鍵字存放在第0號(hào)位置，防止越界

while(list[i].key!=x.key)//從順序表的最后一個(gè)元素開始向前比較

i--;

returni;

}7.2靜態(tài)查找假設(shè)表中有n個(gè)數(shù)據(jù)元素，且數(shù)據(jù)元素在表中出現(xiàn)的概率都相等即，則順序表在查找成功時(shí)的平均查找長(zhǎng)度為：ASL成功===即查找成功時(shí)平均比較次數(shù)約為表長(zhǎng)的一半。在查找失敗時(shí)，即要查找的元素沒有在表中，則每次比較都需要進(jìn)行n+1次。7.2靜態(tài)查找7.2.2有序順序表的查找對(duì)于有序順序表的查找有兩種方法：順序查找和折半查找。1.順序查找有序順序表的順序查找算法與順序表的查找算法類似。但是在通常情況下，不需要比較表中的所有元素。如果要查找的元素在表中，則返回該元素的序號(hào)，否則返回0。7.2靜態(tài)查找publicintSeqSearch3(DataTypex)

//在有序順序表中查找關(guān)鍵字為x的元素，監(jiān)視哨為list[0]，如果找到返回該元素在表中的位置，否則返回0

{

inti=length;

list[0]=x;//將關(guān)鍵字存放在第0號(hào)位置，防止越界

while(list[i].key>x.key)//從有序順序表的最后一個(gè)元素開始向前比較

i--;

returni;

}7.2靜態(tài)查找假設(shè)表中有n個(gè)元素且要查找的數(shù)據(jù)元素在數(shù)據(jù)元素集合中出現(xiàn)的概率相等，查找成功時(shí)查找失敗時(shí)7.2靜態(tài)查找2.折半查找折半查找的前提條件是表中的數(shù)據(jù)元素有序排列。依次與表中間的元素進(jìn)行比較，如果找到與關(guān)鍵字相等的元素，則說明查找成功，否則利用中間位置將表分成兩段。如果查找關(guān)鍵字小于中間位置的元素值，則進(jìn)一步與前一個(gè)子表的中間位置元素比較；否則與后一個(gè)子表的中間位置元素進(jìn)行比較。重復(fù)以上操作，直到找到與關(guān)鍵字相等的元素，表明查找成功。如果子表為空表，表明查找失敗。折半查找又稱為二分查找。7.2靜態(tài)查找例如，一個(gè)有序順序表為(9,23,26,32,36,47,56,63,79,81)，如果要查找56。7.2靜態(tài)查找publicintBinarySearch(DataTypex)

//在有序順序表中折半查找關(guān)鍵字為x的元素，如果找到返回該元素在表中的位置，否則返回0

{

intlow=1;//設(shè)置待查找元素范圍的下界（左邊界）

inthigh=length;//設(shè)置待查找元素范圍的上界（右邊界）

while(low<=high){

intmid=(low+high)/2;

if(list[mid].key==x.key)//如果找到元素，則返回該元素所在的位置

returnmid;

elseif(list[mid].key<x.key)//如果mid所指示的元素小于關(guān)鍵字，則修改low指針

low=mid+1;

elseif(list[mid].key>x.key)//如果mid所指示的元素大于關(guān)鍵字，則修改high指針

high=mid-1;

}

return0;

}7.2靜態(tài)查找查找過程可以用圖7.2所示的二叉判定樹來表示。對(duì)于具有n個(gè)結(jié)點(diǎn)的有序表剛好能夠構(gòu)成一個(gè)深度為h的滿二叉樹，則有h=

。二叉樹中第i層的結(jié)點(diǎn)個(gè)數(shù)是2i-1，假設(shè)表中每個(gè)元素的查找概率相等，7.2靜態(tài)查找7.2.3索引順序表的查找通常將為順序表提供索引的表稱為索引表，索引表分為兩個(gè)部分：一個(gè)用來存儲(chǔ)順序表中每個(gè)單元的最大的關(guān)鍵字，另一個(gè)用來存儲(chǔ)順序表中每個(gè)單元的第一個(gè)元素的下標(biāo)。一個(gè)索引順序表如圖7.3所示。7.2靜態(tài)查找假設(shè)主表中的元素個(gè)數(shù)為n，并將該主表平均分為b個(gè)單元，且每個(gè)單元有s個(gè)元素，即b=n/s。如果表中的元素查找概率相等，則每個(gè)單元中元素的查找概率就是1/s，主表中每個(gè)單元的查找概率是1/b。如果用順序查找法查找索引表中的元素，則索引順序表查找成功時(shí)的平均查找長(zhǎng)度為：7.2靜態(tài)查找如果主表中每個(gè)單元中的元素個(gè)數(shù)不相等的時(shí)候，就需要在索引表中增加一項(xiàng)，即用來存儲(chǔ)主表中每個(gè)單元元素的個(gè)數(shù)。將這種利用索引表示的順序表稱為不等長(zhǎng)索引順序表。例如，一個(gè)不等長(zhǎng)的索引表如圖7.4所示。7.3動(dòng)態(tài)查找二叉排序樹也稱為二叉查找樹。二叉排序樹的查找是一種常用的動(dòng)態(tài)查找方法。1.二叉排序樹的定義與查找所謂二叉排序樹，或者是一棵空二叉樹，或者二叉樹具有以下性質(zhì)：（1）如果二叉樹的左子樹不為空，則左子樹上的每一個(gè)結(jié)點(diǎn)的值都小于其對(duì)應(yīng)根結(jié)點(diǎn)的值；（2）如果二叉樹的右子樹不為空，則右子樹上的每一個(gè)結(jié)點(diǎn)的值都大于其對(duì)應(yīng)根結(jié)點(diǎn)的值；（3）該二叉樹的左子樹和右子樹也滿足性質(zhì)（1）和（2），即左子樹和右子樹也是一棵二叉排序樹。7.3.1二叉排序樹7.3動(dòng)態(tài)查找圖7.5所示為一棵二叉排序樹。圖中的每個(gè)結(jié)點(diǎn)是對(duì)應(yīng)元素關(guān)鍵字的值。采用二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，二叉排序樹的類型定義如下：classBTNode{intdata;BTNodelchild,rchild;BTNode(intdata)

{this.data=data;this.lchild=this.rchild=null;}BTNode()

{}}7.3動(dòng)態(tài)查找publicBTNodeBSTSearch(intx)

//二叉排序樹的查找，如果找到元素x，則返回指向結(jié)點(diǎn)的指針，否則返回null

{

BTNodep=root;

if(root!=null)//如果二叉排序樹不為空

p=root;

while(p!=null){

if(p.data==x)//如果找到，則返回指向該結(jié)點(diǎn)的指針

returnp;

elseif(x<p.data)//如果關(guān)鍵字小于p指向的結(jié)點(diǎn)的值，則在左子樹中查找

p=p.lchild;

else

p=p.rchild;//如果關(guān)鍵字大于p指向的結(jié)點(diǎn)的值，則在右子樹中查找

}

returnnull;

}7.3.1二叉排序樹的查找7.3動(dòng)態(tài)查找左邊的圖的平均查找長(zhǎng)度為ASL成功=1/7×(1+2×2+4×3)=17/7，右邊的圖的平均查找長(zhǎng)度為ASL成功=1/7×(1+2+3+4+5+6+7)=28/7圖7.6所示為兩棵二叉排序樹，其元素的關(guān)鍵字序列分別是{57,21,71,12,51,67,76}和{12,21,51,57,67,71,76}。7.3動(dòng)態(tài)查找假設(shè)當(dāng)前結(jié)點(diǎn)指針cur為空，則說明查找失敗，需要插入結(jié)點(diǎn)。如果parent.data小于要插入的結(jié)點(diǎn)x，則需要將parent的左指針指向x，使x成為parent的左孩子結(jié)點(diǎn)。如果parent.data大于要插入的結(jié)點(diǎn)x，則需要將parent的右指針指向x，使x成為parent的右孩子結(jié)點(diǎn)。如果二叉排序樹為空樹，則使當(dāng)前結(jié)點(diǎn)成為根結(jié)點(diǎn)。插入操作都是在葉子結(jié)點(diǎn)處進(jìn)行的。2.二叉排序樹的插入操作7.3動(dòng)態(tài)查找對(duì)于一個(gè)關(guān)鍵字序列{37,32,35,62,82,95,73,12,5}，二叉樹的創(chuàng)建過程如下2.二叉排序樹的插入操作7.3動(dòng)態(tài)查找publicvoidBSTInsert2(intx)

//叉排序樹的插入操作，如果樹中不存在元素x，則將x插入到正確的位置

{

BTNodep,cur,parent=null;

cur=root;

while(cur!=null){

if(cur.data==x)

return;

parent=cur;

if(x<cur.data)//如果關(guān)鍵字x小于cur指向的結(jié)點(diǎn)的值，則在左子樹中查找

cur=cur.lchild;

else//如果關(guān)鍵字x大于cur指向的結(jié)點(diǎn)的值，則在右子樹中查找

cur=cur.rchild;}

p=newBTNode(x);

if(parent==null)

root=p;

elseif(x<parent.data)

parent.lchild=p;

else

parent.rchild=p;

}7.3動(dòng)態(tài)查找二叉排序樹的各種刪除情形如圖7.8所示。（1）如果s指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，其左子樹和右子樹為空，刪除葉子結(jié)點(diǎn)不會(huì)影響到樹的結(jié)構(gòu)特性，因此只需要修改p的指向即可。（2）如果s指向的結(jié)點(diǎn)只有左子樹或只有右子樹，在刪除了結(jié)點(diǎn)*s后，只需要將s的左子樹sL或右子樹sR作為f的左孩子即p.lchild=s.lchild或p.lchid=s.rchild。（3）如果s左子樹和右子樹都存在，在刪除結(jié)點(diǎn)S之前，二叉排序樹的中序序列為{…QLQ…XLXYLYSSRP…}，因此，在刪除了結(jié)點(diǎn)S之后，有兩種方法調(diào)整使該二叉樹仍然保持原來的性質(zhì)不變。3.二叉排序樹的刪除操作7.3動(dòng)態(tài)查找3.二叉排序樹的刪除操作7.3動(dòng)態(tài)查找【例7.1】給定一組元素序列{37,32,35,62,82,95,73,12,5}，利用二叉排序樹的插入算法創(chuàng)建一棵二叉排序樹，然后查找元素值為32的元素，并刪除該元素，然后以中序序列輸出該元素序列。中序遍歷二叉排序樹得到的序列為：51232353762738295請(qǐng)輸入要查找的元素：32二叉排序樹查找，關(guān)鍵字32存在！刪除32后，二叉樹排序樹元素序列：5123537627382957.3動(dòng)態(tài)查找1.平衡二叉樹的定義平衡二叉樹或者是一棵空二叉樹，或者是具有以下性質(zhì)的二叉樹：平衡二叉樹的左子樹和右子樹的深度之差的絕對(duì)值小于等于1，且左子樹和右子樹也是平衡二叉樹。平衡二叉樹也稱為AVL樹。7.3.2平衡二叉樹7.3動(dòng)態(tài)查找失去平衡的二叉排序樹類型及調(diào)整方法可以歸納為以下四種情形。（1）LL型。LL型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的左子樹的左子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.13所示?？梢允菇Y(jié)點(diǎn)A作為結(jié)點(diǎn)B的右子樹，結(jié)點(diǎn)B的右子樹作為結(jié)點(diǎn)A的左子樹。這樣就恢復(fù)了該二叉排序樹的平衡，這相當(dāng)于以結(jié)點(diǎn)B為軸，對(duì)結(jié)點(diǎn)A進(jìn)行順時(shí)針旋轉(zhuǎn)。7.3.2二叉排序樹的平衡化處理7.3動(dòng)態(tài)查找（2）LR型。LR型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的左子樹的右子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.14所示。使結(jié)點(diǎn)B作為結(jié)點(diǎn)C的左子樹，結(jié)點(diǎn)C的左子樹作為結(jié)點(diǎn)B的右子樹。將結(jié)點(diǎn)C作為新的根結(jié)點(diǎn)，結(jié)點(diǎn)A作為C的右子樹的根結(jié)點(diǎn)，結(jié)點(diǎn)C的右子樹作為A的左子樹。這相當(dāng)于以結(jié)點(diǎn)B為軸，對(duì)結(jié)點(diǎn)C先做了一次逆時(shí)針旋轉(zhuǎn)；然后以結(jié)點(diǎn)C為軸對(duì)結(jié)點(diǎn)A做了一次順時(shí)針旋轉(zhuǎn)。7.3動(dòng)態(tài)查找（3）RL型。RL型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的右子樹的左子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.15所示。7.3動(dòng)態(tài)查找（4）RR型。RR型是指在離插入點(diǎn)最近的失衡結(jié)點(diǎn)的右子樹的右子樹中插入結(jié)點(diǎn)，導(dǎo)致二叉排序樹失去平衡。如圖7.16所示。為了使二叉樹恢復(fù)平衡且保持二叉排序樹的性質(zhì)不變，可以使結(jié)點(diǎn)結(jié)點(diǎn)A作為B的左子樹的根結(jié)點(diǎn)，結(jié)點(diǎn)B的左子樹作為A的右子樹。這樣就恢復(fù)了該二叉排序樹的平衡。這相當(dāng)于以結(jié)點(diǎn)B為軸，對(duì)結(jié)點(diǎn)A做了一次逆時(shí)針旋轉(zhuǎn)。7.3動(dòng)態(tài)查找1．紅黑樹的定義紅黑樹是一棵具有以下特點(diǎn)的二叉查找樹：（1）每個(gè)結(jié)點(diǎn)不是紅色，就是黑色；（2）根結(jié)點(diǎn)的顏色為黑色；（3）葉子結(jié)點(diǎn)是空節(jié)點(diǎn)且為黑色；（4）若一個(gè)結(jié)點(diǎn)是紅色的，則孩子結(jié)點(diǎn)一定是黑色的，即從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中，不存在連續(xù)的紅色結(jié)點(diǎn)；（5）從任何一個(gè)結(jié)點(diǎn)出發(fā)到葉子結(jié)點(diǎn)的路徑上，包含相同數(shù)目的黑色結(jié)點(diǎn)。7.3動(dòng)態(tài)查找1）紅黑樹的插入

假設(shè)插入的結(jié)點(diǎn)為T，其雙親結(jié)點(diǎn)P為紅色的，則P的雙親結(jié)點(diǎn)是黑色的。（1）T的雙親結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)U是黑色的情況以P為軸進(jìn)行一次順時(shí)針旋轉(zhuǎn)，使P成為G的雙親結(jié)點(diǎn)，G成為P的右孩子結(jié)點(diǎn)，并將P和G重新著色。7.3動(dòng)態(tài)查找1）紅黑樹的插入對(duì)于LR型紅黑樹，以P為軸進(jìn)行逆時(shí)針旋轉(zhuǎn)，再以T為軸進(jìn)行順時(shí)針旋轉(zhuǎn)，使T成為P的雙親結(jié)點(diǎn)，P和G分別成為T的左、右孩子結(jié)點(diǎn)，將T和G重新著色，T著色為黑色，G著色為紅色7.3動(dòng)態(tài)查找1）紅黑樹的插入（2）T的雙親結(jié)點(diǎn)P的兄弟結(jié)點(diǎn)U是紅色的情況7.3動(dòng)態(tài)查找2）紅黑樹的刪除若刪除的結(jié)點(diǎn)D的左孩子結(jié)點(diǎn)DL或右孩子結(jié)點(diǎn)DR為紅色，在刪除D后，使DL或DR替換結(jié)點(diǎn)D的結(jié)點(diǎn)，并標(biāo)記為黑色結(jié)點(diǎn)。7.3動(dòng)態(tài)查找2）紅黑樹的刪除若刪除的結(jié)點(diǎn)D為黑色結(jié)點(diǎn)，且其兄弟結(jié)點(diǎn)S也是黑色的。7.4B-樹與B+樹7.4.1B-樹1.B-樹的定義B-是一種平衡的排序樹，也稱為m路（階）查找樹。一棵m階B-樹或者是一棵空樹，或者是滿足以下性質(zhì)的m叉樹：（1）樹中的任何一個(gè)結(jié)點(diǎn)最多有m棵子樹。（2）如果根結(jié)點(diǎn)或者是葉子結(jié)點(diǎn)，或者至少有兩棵子樹。（3）除了根結(jié)點(diǎn)之外，所有的非葉子結(jié)點(diǎn)至少應(yīng)有棵子樹。（4）所有的葉子結(jié)點(diǎn)處于同一層次上，且不包括任何關(guān)鍵字信息。（5）所有的非葉子結(jié)點(diǎn)的結(jié)構(gòu)如下：7.4B-樹與B+樹例如，一棵深度為4的4階B-樹如圖7.17所示。7.4B-樹和B+樹3.B-樹的插入操作例如，圖7.18所示為一棵3階B-樹（省略了葉子結(jié)點(diǎn)），在該B-樹中依次插入關(guān)鍵字35、25、78和43。7.4B-樹和B+樹3.B-樹的插入操作插入關(guān)鍵字35：首先需要從根結(jié)點(diǎn)開始，確定關(guān)鍵字42應(yīng)插入的位置應(yīng)該是結(jié)點(diǎn)E。插入后B-樹如圖7.19所示。7.4B-樹和B+樹3.B-樹的插入操作插入關(guān)鍵字25：從根結(jié)點(diǎn)開始確定關(guān)鍵字25應(yīng)插入的位置為結(jié)點(diǎn)D。結(jié)點(diǎn)D分裂為兩個(gè)結(jié)點(diǎn)，關(guān)鍵字24被插入到雙親結(jié)點(diǎn)B中，關(guān)鍵字12被保留在結(jié)點(diǎn)D中，關(guān)鍵字25被插入到新生成的結(jié)點(diǎn)D’中，并使關(guān)鍵字24的右指針指向結(jié)點(diǎn)D’。7.4B-樹和B+樹4.B-樹的刪除操作B-樹的刪除操作有以下三種可能：（1）要?jiǎng)h除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于等于[m/2]

，則只需要將關(guān)鍵字Ki和對(duì)應(yīng)的指針Pi從該結(jié)點(diǎn)中刪除即可。7.4B-樹和B+樹3.B-樹的刪除操作（2）要?jiǎng)h除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)等于-1，而與該結(jié)點(diǎn)相鄰的兄弟結(jié)點(diǎn)（左兄弟或右兄弟）中的關(guān)鍵字個(gè)數(shù)大于-1將關(guān)鍵字89刪除后，需要將關(guān)鍵字73向上移動(dòng)到雙親結(jié)點(diǎn)C中，并將關(guān)鍵字83下移到結(jié)點(diǎn)H中，得到如圖7.28所示的B-樹。7.4B-樹和B+樹3.B-樹的刪除操作（3）要?jiǎng)h除的關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)等于-1，而與該結(jié)點(diǎn)相鄰的兄弟結(jié)點(diǎn)（左兄弟或右兄弟）中的關(guān)鍵字個(gè)數(shù)也等于-1將關(guān)鍵字83刪除后，需要將關(guān)鍵字83的左兄弟結(jié)點(diǎn)的關(guān)鍵字69與其雙親結(jié)點(diǎn)中的關(guān)鍵字73合并到一起，得到如圖7.29所示的B-樹。7.4B-樹和B+樹7.4.2B+樹B+樹是B-樹的一種變型。它與B-樹的主要區(qū)別在于：（1）如果一個(gè)結(jié)點(diǎn)有n棵子樹，則該結(jié)點(diǎn)也必有n個(gè)關(guān)鍵字，即關(guān)鍵字個(gè)數(shù)與結(jié)點(diǎn)的子樹個(gè)數(shù)相等。（2）所有的非葉子結(jié)點(diǎn)包含子樹的根結(jié)點(diǎn)的最大或者最小的關(guān)鍵字信息，因此所有的非葉子結(jié)點(diǎn)可以作為索引。（3）葉子結(jié)點(diǎn)包含所有關(guān)鍵字信息和關(guān)鍵字記錄的指針，所有葉子結(jié)點(diǎn)中的關(guān)鍵字按照從小到大的順序依次通過指針鏈接。7.5哈希表7.5.1哈希表的定義用key表示元素的關(guān)鍵字，f表示對(duì)應(yīng)關(guān)系，則f(key)表示元素的存儲(chǔ)地址，將這種對(duì)應(yīng)關(guān)系f稱為哈希（Hash）函數(shù)，利用哈希函數(shù)可以建立哈希表。哈希函數(shù)也稱為散列函數(shù)。7.5哈希表7.5.2哈希函數(shù)的構(gòu)造方法1.直接定址法直接定址法就是直接取關(guān)鍵字的線性函數(shù)值作為哈希函數(shù)的地址。直接定址法可以表示如下：h(key)=x*key+y其中x和y是常數(shù)。直接定址法的計(jì)算比較簡(jiǎn)單且不會(huì)發(fā)生沖突。由于這種方法會(huì)使產(chǎn)生的哈希函數(shù)地址比較分散，造成內(nèi)存的大量浪費(fèi)。7.5哈希表7.5.2哈希函數(shù)的構(gòu)造方法2.平方取中法平方取中法就是將關(guān)鍵字的平方得到的值的其中幾位作為哈希函數(shù)的地址。3.折疊法折疊法是將關(guān)鍵字平均分割為若干等分，最后一個(gè)部分如果不夠可以空缺，然后將這幾個(gè)等分疊加求和作為哈希地址。4.除留余數(shù)法除留余數(shù)法主要是通過對(duì)關(guān)鍵字取余，將得到的余數(shù)作為哈希地址。其主要方法為：設(shè)哈希表長(zhǎng)為m，p為小于等于m的數(shù)，則哈希函數(shù)為h(key)=key%p。除留余數(shù)法是一種常用的求哈希函數(shù)方法。7.5哈希表4.除留余數(shù)法例如，給定一組關(guān)鍵字{75,149,123,183,230,56,37,91}，設(shè)哈希表長(zhǎng)m為14，取p=13，則這組關(guān)鍵字的哈希地址存儲(chǔ)情況為：p如果沒有明確給出，一般取小于等于表長(zhǎng)的最大質(zhì)數(shù)。7.5哈希表7.5.3處理沖突的方法處理沖突的方法比較常用的主要有：開放定址法、再哈希法和鏈地址法。1.開放定址法開放定址法就是利用哈希表中的空地址存儲(chǔ)產(chǎn)生沖突的關(guān)鍵字。當(dāng)沖突發(fā)生時(shí)，按照下列公式處理沖突：hi=(h(key)+di)%m,其中i=1,2,…,m-1其中，h(key)為哈希函數(shù)，m為哈希表長(zhǎng)，di為地址增量。（1）線性探測(cè)再散列：在沖突發(fā)生時(shí)，地址增量di依次取1,2,…,m-1自然數(shù)列，即di=1,2,…,m-1。（2）二次探測(cè)再散列：di=12,-12,22,-22,…,k2,-k2。（3）偽隨機(jī)數(shù)再散列。7.5哈希表1.開放定址法（1）線性探測(cè)再散列：在沖突發(fā)生時(shí)，地址增量di依次取1,2,…,m-1自然數(shù)列，即di=1,2,…,m-1。（2）二次探測(cè)再散列：在沖突發(fā)生時(shí)，地址增量di依次取自然數(shù)的平方，即di=12,-12,22,-22,…,k2,-k2。（3）偽隨機(jī)數(shù)再散列：在沖突發(fā)生時(shí)，地址增量di依次取隨機(jī)數(shù)序列。7.5哈希表1.開放定址法例如，在長(zhǎng)度為14的哈希表中，在將關(guān)鍵字183、123、230、91存放在哈希表中的情況如圖7.31所示。插入關(guān)鍵字149時(shí)，h(149)=149%13=6，產(chǎn)生沖突，利用線性探測(cè)再散列法解決沖突，即h1=(6+1)%14=7，將149存儲(chǔ)在單元7中。7.5哈希表2.再哈希法再哈希法就是在沖突發(fā)生時(shí)，利用另外一個(gè)哈希函數(shù)再次求哈希函數(shù)的地址，直到?jīng)_突不再發(fā)生為止，即：hi=rehash(key)，i=1,2,…,n其中，rehash表示不同的哈希函數(shù)。7.5哈希表3.鏈地址法鏈地址法就是將具有相同散列地址的關(guān)鍵字用一個(gè)線性鏈表存儲(chǔ)起來。例如，一組關(guān)鍵字序列{23,35,12,56,123,39,342,90,78,110}，按照哈希函數(shù)h(key)=key%13和鏈地址法處理沖突，其哈希表如圖7.35所示。7.5哈希表【例7.2】設(shè)哈希表的長(zhǎng)度為15，哈希函數(shù)為H(k)=k%13，散列地址空間為0~14，對(duì)關(guān)鍵字序列（19,5,21,24,45,20,68,27,70,11,10），按線性探測(cè)再散列解決沖突的方法構(gòu)造哈希表，畫出構(gòu)造后的哈希表，并求出等概率下查找成功和查找不成功時(shí)的平均查找長(zhǎng)度。對(duì)于關(guān)鍵字19，H(19)=19%13=6對(duì)于關(guān)鍵字5，H(5)=5%13=5對(duì)于關(guān)鍵字21，H(21)=21%13=8對(duì)于關(guān)鍵字24，H(24)=24%13=11對(duì)于關(guān)鍵字45，H(45)=45%13=6，沖突；利用線性探測(cè)再散列法處理沖突，d1=1，H1=(H(19)+1)%15=7。7.5哈希表【例7.2】設(shè)哈希表的長(zhǎng)度為15，哈希函數(shù)為H(k)=k%13，散列地址空間為0~14，對(duì)關(guān)鍵字序列（19,5,21,24,45,20,68,27,70,11,10），按線性探測(cè)再散列解決沖突的方法構(gòu)造哈希表，畫出構(gòu)造后的哈希表，并求出等概率下查找成功和查找不成功時(shí)的平均查找長(zhǎng)度。查找成功時(shí)的平均查找長(zhǎng)度ASL成功=ASL失敗=哈希表地址：01234567891011121314關(guān)鍵字key:-127-168-151945212070241110-1比較次數(shù)：010101121361240關(guān)鍵字68在哈希表中的位置為：3查找成功時(shí)的平均查找長(zhǎng)度ASL_succ=2.090909查找不成功時(shí)的平均查找長(zhǎng)度ASL_unsucc=4.53846177.5哈希表【例7.2】設(shè)哈希表的長(zhǎng)度為15，哈希函數(shù)為H(k)=k%13，散列地址空間為0~14，對(duì)關(guān)鍵字序列（19,5,21,24,45,20,68,27,70,11,10），按線性探測(cè)再散列解決沖突的方法構(gòu)造哈希表，畫出構(gòu)造后的哈希表，并求出等概率下查找成功和查找不成功時(shí)的平均查找長(zhǎng)度。哈希表地址：01234567891011121314關(guān)鍵字key:-127-168-151945212070241110-1比較次數(shù)：010101121361240關(guān)鍵字68在哈希表中的位置為：3查找成功時(shí)的平均查找長(zhǎng)度ASL_succ=2.090909查找不成功時(shí)的平均查找長(zhǎng)度ASL_unsucc=4.53846177.6小結(jié)查找分為兩種：靜態(tài)查找與動(dòng)態(tài)查找。動(dòng)態(tài)查找是利用二叉樹和樹的特點(diǎn)對(duì)數(shù)據(jù)元素集合進(jìn)行排序，通過將元素插入到二叉樹或樹中建立二叉樹或樹，然后通過對(duì)二叉樹或樹的遍歷按照從小到大輸出元素的序列。其中，B-樹和B+樹又利用了索引技術(shù)，這樣可以提高查找的效率。

靜態(tài)查找中順序表的平均查找長(zhǎng)度為O(n)，折半查找的平均查找長(zhǎng)度為O(log2n)。動(dòng)態(tài)查找中的二叉排序樹的查找類似于折半查找，其平均查找長(zhǎng)度為O(log2n)。哈希表是利用哈希函數(shù)的映射關(guān)系直接確定要查找元素的位置，大大減少了與元素的關(guān)鍵字的比較次數(shù)。感謝聆聽主講：結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)第8章排序結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS8.1

排序的基本概念8.2插入排序8.3選擇排序8.6基數(shù)排序8.4交換排序8.5歸并排序8.7小結(jié)8.1排序的基本概念排序：把一個(gè)無序的元素序列按照元素的關(guān)鍵字遞增或遞減排列為有序的序列。穩(wěn)定排序和不穩(wěn)定排序：在排列過程中，如果存在兩個(gè)關(guān)鍵字相等即ki=kj(1≤i≤n,1≤j≤n,i≠j)，在排序之前，對(duì)應(yīng)的元素Ei在Ej之前。內(nèi)排序是指需要排序的元素?cái)?shù)量不是特別大，在排序的過程中完全在內(nèi)存中進(jìn)行的方法。外排序是指需要排序的數(shù)據(jù)量非常大，在內(nèi)存中不能一次完成排序，需要不斷地在內(nèi)存和外存中交替才能完成的排序。8.1排序的基本概念待排序的元素的存儲(chǔ)結(jié)構(gòu)有兩種方式：（1）順序存儲(chǔ)。將待排序的元素存儲(chǔ)在一組連續(xù)的存儲(chǔ)單元中，這類似于線性表的順序存儲(chǔ)，元素Ei和Ej邏輯上相鄰，其物理位置也相鄰。在排序過程中，需要移動(dòng)元素。（2）鏈?zhǔn)酱鎯?chǔ)。將待排序元素存儲(chǔ)在一組不連續(xù)的存儲(chǔ)單元中，這類似于線性表的鏈?zhǔn)酱鎯?chǔ)，元素Ei和Ej邏輯上相鄰，其物理位置不一定相鄰。在進(jìn)行排序時(shí)，不需要移動(dòng)元素，只需要修改相應(yīng)的指針即可。classSqList//順序表類型定義{intdata[];intlength;finalintMAXSIZE=30;SqList(){this.data=newint[MAXSIZE];this.length=0;}}8.2插入排序?qū)W習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力直接插入排序的基本思想：假設(shè)前i-1個(gè)元素已經(jīng)有序，將第i個(gè)元素的關(guān)鍵字與前i-1個(gè)元素的關(guān)鍵字進(jìn)行比較，找到合適的位置，將第i個(gè)元素插入。按照類似的方法，將剩下的元素依次插入到已經(jīng)有序的序列中，完成插入排序。01直接插入排序8.2插入排序?qū)W習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力例如，給定一個(gè)含有8個(gè)元素的關(guān)鍵字序列(45,23,56,12,97,76,29,68)，將這些元素按照關(guān)鍵字從小到大進(jìn)行直接插入排序的過程如圖8.1所示。publicvoidDirectInsertSort()//直接插入排序

{

inti=0,t=-1,j=0;

for(i=0;i<length-1;i++)//前i個(gè)元素已經(jīng)有序，從第i+1個(gè)元素開始與前i個(gè)有序的關(guān)鍵字比較

{

t=data[i+1];//取出第i+1個(gè)元素，

j=i;

while(j>-1&&t<data[j])//尋找當(dāng)前元素的合適位置

{

data[j+1]=data[j];

j-=1;

}

data[j+1]=t;//將當(dāng)前元素插入合適的位置

}

}8.2插入排序?qū)W習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力8.2插入排序8.2.2折半插入排序在插入排序中，將待排序元素插入到已經(jīng)有序的元素序列的正確位置，因此，在查找正確插入位置時(shí)，可以采用折半查找的思想尋找插入位置。這種插入排序算法稱為折半插入排序。8.2插入排序i=48.2插入排序lowmidhighi=5highmidlow8.2插入排序i=6lowmidhigh8.2插入排序8.2.2折半插入排序publicvoidBinInsertSort()//折半插入排序

{

intt,low,high,mid;

for(inti=0;i<length-1;i++)

{

t=data[i+1];//取出第i+1個(gè)元素，即待排序的元素

low=0;

high=i;

while(low<=high)//利用折半查找思想尋找當(dāng)前元素的合適位置

{

mid=(low+high)/2;

if(data[mid]>t)

high=mid-1;

else

low=mid+1;}

for(intj=i;j>low-1;j--)//移動(dòng)元素，空出要插入的位置

data[j+1]=data[j];

data[low]=t;//將當(dāng)前元素插入合適的位置

}

}8.2插入排序8.2.3希爾排序希爾排序也稱為縮小增量排序，它的基本思想是：通過將待排序的元素分為若干個(gè)子序列，利用直接插入排序思想對(duì)子序列進(jìn)行排序。然后將該子序列縮小，接著對(duì)子序列進(jìn)行直接插入排序。按照這種思想，直到所有的元素都按照關(guān)鍵字有序排列。希爾排序算法思想的出發(fā)點(diǎn)：直接插入排序在基本有序時(shí)，效率較高在待排序的記錄個(gè)數(shù)較少時(shí)，效率較高基本思想：先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。8.2插入排序8.2插入排序例如，利用希爾排序的算法思想，對(duì)元素的關(guān)鍵字序列(56,22,67,32,59,12,89,26,48,37)進(jìn)行排序，其排序過程如圖8.2所示。8.2插入排序publicvoidShellInsert(intc)//對(duì)順序表L進(jìn)行一次希爾排序，c是增量

{

intt,j;

for(inti=c;i<length;i++)//將距離為c的元素作為一個(gè)子序列進(jìn)行排序

{

if(data[i]<data[i-c])//如果后者小于前者，則需要移動(dòng)元素

{

t=data[i];

j=i-c;

while(j>-1&&t<data[j]){

data[j+c]=data[j];

j-=c;

}

data[j+c]=t;//依次將元素插入到正確的位置

}

}

}

publicvoidShellInsertSort(intdelta[],intm)//希爾排序，每次調(diào)用算法ShellInsert,delta是存放增量的列表

{

for(inti=0;i<m;i++)//進(jìn)行m次希爾插入排序

ShellInsert(delta[i]);

}8.2插入排序8.2.3希爾排序算法效率分析希爾排序的分析是一個(gè)非常復(fù)雜的事情，問題主要在于希爾排序選擇的增量，但是經(jīng)過大量的研究，當(dāng)增量的序列為2m-k+1-1時(shí)，其中m為排序的次數(shù)，1≤k≤t，其時(shí)間復(fù)雜度為O(n3/2)。希爾排序的空間復(fù)雜度為O(1)。希爾排序是一種不穩(wěn)定的排序。8.2插入排序【例8.1】利用直接插入排序、折半插入排序和希爾排序?qū)﹃P(guān)鍵字為(56,22,67,32,59,12,89,26,48,37)的元素序列進(jìn)行排序。程序運(yùn)行結(jié)果如下所示。排序前：56226732591289264837直接插入排序結(jié)果：12222632374856596789排序前：56226732591289264837折半插入排序結(jié)果：12222632374856596789排序前：56226732591289264837希爾排序結(jié)果：122226323748565967898.3選擇排序8.3.1簡(jiǎn)單選擇排序基本思想：假設(shè)待排序的元素序列有n個(gè)，第一趟排序經(jīng)過n-1次比較，從n個(gè)元素序列中選擇關(guān)鍵字最小的元素，并將其放在元素序列的最前面即第一個(gè)位置。第二趟排序從剩余的n-1個(gè)元素中，經(jīng)過n-2次比較選擇關(guān)鍵字最小的元素，將其放在第二個(gè)位置。依次類推，直到?jīng)]有待比較的元素，簡(jiǎn)單選擇排序算法結(jié)束。8.3選擇排序給定一組元素序列，其元素的關(guān)鍵字為(56,22,67,32,59,12,89,26)，簡(jiǎn)單選擇排序的過程如圖8.4所示。8.3選擇排序publicvoidSimpleSelectSort()

//簡(jiǎn)單選擇排序

{

//將第i個(gè)元素與后面[i+1...n]個(gè)元素比較，將值最小的元素放在第i個(gè)位置

for(inti=0;i<length-1;i++){

intj=i;

for(intk=i+1;k<length;k++)//值最小的元素的序號(hào)為j

{

if(data[k]<data[j])

j=k;

}

if(j!=i)//如果序號(hào)i不等于j，則需要將序號(hào)i和序號(hào)j的元素交換

{

intt=data[i];

data[i]=data[j];

data[j]=t;

}

}

}8.3選擇排序簡(jiǎn)單選擇排序的空間復(fù)雜度為O(1)。簡(jiǎn)單選擇排序在最好的情況下，其元素序列已經(jīng)是非遞減有序序列，則不需要移動(dòng)元素。在最壞的情況下，其元素序列是按照遞減排列，則在每一趟排序的過程中都需要移動(dòng)元素，因此，需要移動(dòng)元素的次數(shù)為3(n-1)。簡(jiǎn)單選擇排序的比較次數(shù)與元素的關(guān)鍵字排列無關(guān)，在任何情況下，都需要進(jìn)行n(n-1)/2次。綜合以上考慮，簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度為O(n2)。8.3選擇排序1.堆的定義堆排序是利用了二叉樹的樹形結(jié)構(gòu)進(jìn)行排序。堆中的每一個(gè)結(jié)點(diǎn)都大于（或小于）其孩子結(jié)點(diǎn)。堆的數(shù)學(xué)形式定義為：假設(shè)存在n個(gè)元素，其關(guān)鍵字序列為(k1,k2,…,ki,…,kn)，如果有：8.3.2堆排序8.3選擇排序在堆中，堆的根結(jié)點(diǎn)元素值一定是所有結(jié)點(diǎn)元素值的最大值或最小值。例如，序列(87,64,53,51,23,21,48,32)和(12,35,27,46,41,39,48,55,89,76)都是堆，相應(yīng)的完全二叉樹表示如圖8.5所示。8.3選擇排序2.建堆堆排序的過程就是建立堆和不斷調(diào)整使剩余結(jié)點(diǎn)構(gòu)成新堆的過程。假設(shè)將待排序的元素的關(guān)鍵字存放在數(shù)組a中，第1個(gè)元素的關(guān)鍵字a[1]表示二叉樹的根結(jié)點(diǎn)，剩下的元素的關(guān)鍵字a[2…n]分別與二叉樹中的結(jié)點(diǎn)按照層次從左到右一一對(duì)應(yīng)。例如，根結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存放在a[2]中，右孩子結(jié)點(diǎn)存放在a[3]中，a[i]的左孩子結(jié)點(diǎn)存放在a[2*i]中，右孩子結(jié)點(diǎn)存放在a[2*i+1]中。8.3選擇排序例如，給定一組元素，其關(guān)鍵字序列為(21,47,39,51,39,57,48,56)，建立大頂堆的過程如圖8.6所示。結(jié)點(diǎn)的旁邊為對(duì)應(yīng)的序號(hào)。8.3選擇排序publicvoidCreateHeap(intn)

//建立大頂堆

{

for(inti=n/2-1;i>=0;i--)//從序號(hào)n/2開始建立大頂堆

AdjustHeap(i,n-1);

}

publicvoidAdjustHeap(ints,intm)

//調(diào)整H.data[s...m]的關(guān)鍵字，使其成為一個(gè)大頂堆

{

intt=data[s];//將根結(jié)點(diǎn)暫時(shí)保存在t中

intj=2*s+1;

while(j<=m){

if(j<m&&data[j]<data[j+1])//沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下篩選

j++;//j為關(guān)鍵字較大的結(jié)點(diǎn)的下標(biāo)

if(t>data[j])//如果孩子結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值，則不進(jìn)行交換

break;

data[s]=data[j];

s=j;

j*=2+1;

}

data[s]=t;//將根結(jié)點(diǎn)插入到正確位置

}8.3選擇排序3.調(diào)整堆建立好一個(gè)大頂堆后，當(dāng)輸出堆頂元素后，如何調(diào)整剩下的元素，使其構(gòu)成一個(gè)新的大頂堆呢？其實(shí)，這也是一個(gè)建堆的過程，由于除了堆頂元素外，剩下的元素本身就具有a[i].key≥a[2*i].key且a[i].key≥a[2*i+1].key(i=1,2,…,)。例如，一個(gè)大頂堆的關(guān)鍵字序列為(87,64,53,51,23,21,48,32)，當(dāng)輸出87后，調(diào)整剩余的關(guān)鍵字序列為一個(gè)新的大頂堆的過程如圖8.7所示。8.3選擇排序publicvoidHeapSort()

//對(duì)順序表H進(jìn)行堆排序

{

CreateHeap(length);//創(chuàng)建堆

for(inti=length-1;i>0;i--)//將堆頂元素與最后一個(gè)元素交換，重新調(diào)整堆

{

intt=data[0];

data[0]=data[i];

data[i]=t;

AdjustHeap(0,i-1);//將data[1..i-1];//調(diào)整為大頂堆

}

}8.3選擇排序堆排序8.3選擇排序堆排序是一種不穩(wěn)定的排序。堆排序的時(shí)間耗費(fèi)主要是在建立堆和不斷調(diào)整堆的過程。一個(gè)深度為h，元素個(gè)數(shù)為n的堆，其調(diào)整算法的比較次數(shù)最多為2(h-1)次，而建立一個(gè)堆，其比較次數(shù)最多為4n。一個(gè)完整的堆排序過程總共的比較次數(shù)為堆排序在最壞的情況下時(shí)間復(fù)雜度為O(nlog2n)。堆排序適合應(yīng)用于待排序的數(shù)據(jù)量較大的情況。8.4交換排序基本思想：從第1個(gè)元素開始，依次比較兩個(gè)相鄰的元素，如果兩個(gè)元素逆序，則進(jìn)行交換，即如果L.data[i].key>L.data[i+1].key，則交換L.data[i]與L.data[i+1]。例如，一組元素序列的關(guān)鍵字為(56,22,67,32,59,12,89,26,48,37)，對(duì)該關(guān)鍵字序列進(jìn)行冒泡排序，第1趟排序過程如圖所示。8.4.1冒泡排序8.4交換排序8.4.1冒泡排序8.4交換排序publicvoidBubbleSort(intn)//冒泡排序

{

booleanflag=true;

for(inti=0;i<n-1;i++){//需要進(jìn)行n-1趟排序

if(flag)

{

flag=false;

for(intj=0;j<length-i-1;j++)//每一趟排序需要比較n-i次

{

if(data[j]>data[j+1]){

intt=data[j];

data[j]=data[j+1];

data[j+1]=t;

flag=true;}}

}

}

}冒泡排序的改進(jìn)若元素個(gè)數(shù)為n比較次數(shù)和移動(dòng)次數(shù)與初始排列相關(guān)只需1趟排序，比較次數(shù)為

n-1，不移動(dòng)42567956*2812最好情況下：8.4交換排序時(shí)間復(fù)雜度為o(n2)需n-1趟排序，第i趟比較n-i次，移動(dòng)3(n-i)次最壞情況下：空間復(fù)雜度為o(1)是一種穩(wěn)定的排序方法8.4交換排序8.4交換排序8.4.2快速排序基本算法思想：設(shè)待排序的元素序列的個(gè)數(shù)為n，分別存放在數(shù)組a[1…n]中，令第一元素作為樞軸元素，即將a[1]作為參考元素，令pivot=a[1]。初始時(shí)，令i=1、j=n，執(zhí)行以下操作：（1）從序列的j位置往前，依次將元素的關(guān)鍵字與樞軸元素比較。如果當(dāng)前元素的關(guān)鍵字大于等于樞軸元素的關(guān)鍵字，則將前一個(gè)元素的關(guān)鍵字與樞軸元素的關(guān)鍵字比較，否則，將當(dāng)前元素移動(dòng)到位置i，即比較a[j].key與pivot.key，如果a[j].key≥pivot.key，則連續(xù)執(zhí)行j―=1操作，直到找到一個(gè)元素使a[j].key<pivot.key，則將a[j]移動(dòng)到a[i]中，并執(zhí)行一次i+=1操作。8.4交換排序（2）從序列的i位置開始，依次將該元素的關(guān)鍵字與樞軸元素比較。如果當(dāng)前元素的關(guān)鍵字小于樞軸元素的關(guān)鍵字，則將后一個(gè)元素的關(guān)鍵字與樞軸元素的關(guān)鍵字比較，否則，將當(dāng)前元素移動(dòng)到位置j，即比較a[i].key與pivot.key，如果a[i].key<pivot.key，則連續(xù)執(zhí)行i+=1，直到遇到一個(gè)元素使a[i].key≥pivot.key，則將a[i]移動(dòng)到a[j]中，并執(zhí)行一次j-=1操作。（3）循環(huán)執(zhí)行步驟（1）和（2），直到出現(xiàn)i≥j，則將元素pivot移動(dòng)到a[i]中。此時(shí)整個(gè)元素序列在位置i被劃分成兩個(gè)部分，前一部分的元素關(guān)鍵字都小于a[1].key，后一部分元素的關(guān)鍵字都大于等于a[1].key，即完成了一趟快速排序。8.4交換排序例如，一組元素序列的關(guān)鍵字為(37,19,43,22,22,89,26,92)，根據(jù)快速排序算法思想，第一次劃分的過程如圖8.11所示。8.4交換排序快速排序8.4交換排序publicintPartition(intlow,inthigh)

//對(duì)順序表L.r[low..high]的元素進(jìn)行一趟排序

{

intpivotkey=data[low];//將表的第一個(gè)元素作為樞軸元素

intt=data[low];

while(low<high)//從表的兩端交替地向中間掃描

{

while(low<high&&data[high]>=pivotkey)high--;

if(low<high)//將當(dāng)前high指向的元素保存在low位置

{

data[low]=data[high];

low++;}

while(low<high&&data[low]<=pivotkey)

low++;

if(low<high)//將當(dāng)前l(fā)ow指向的元素保存在high位置

{

data[high]=data[low];

high--;}

data[low]=t;//將樞軸元素保存在low=high的位置

}

returnlow;//返回樞軸所在位置

}8.4交換排序快速排序是一種不穩(wěn)定的排序算法，其空間復(fù)雜度為O(log2n)。在最好的情況下，每趟排序均將元素序列正好劃分為相等的兩個(gè)子序列，這樣快速排序的劃分的過程就將元素序列構(gòu)成一個(gè)完全二叉樹的結(jié)構(gòu)，分解的次數(shù)等于樹的深度即log2n，因此快速排序總的比較次數(shù)為T(n)≤n+2T(n/2)≤n+2*(n/2+2*T(n/4))=2n+4T(n/4)≤3n+8T(n/8)≤…≤nlog2n+nT(1)。在最好的情況下，時(shí)間復(fù)雜度為O(nlog2n)。8.4交換排序【例8.2】對(duì)于n個(gè)元素組成的線性表進(jìn)行快速排序時(shí)，對(duì)關(guān)鍵字的比較次數(shù)是與這n個(gè)元素的初始排列有關(guān)的。若n=7時(shí)，請(qǐng)回答以下問題：（1）在最好的情況下，需要對(duì)關(guān)鍵字進(jìn)行多少次比較？請(qǐng)說明理由。（2）給出一個(gè)最好情況的初始排序的實(shí)例。（3）在最壞情況下需要對(duì)關(guān)鍵字進(jìn)行多少次比較？請(qǐng)說明理由。（4）請(qǐng)給出一個(gè)最壞情況下的初始排序?qū)嵗?。在最好的情況下，快速排序初始序列為4、1、3、2、6、5、7。在最壞的情況下，初始序列為7、6、5、4、3、2、1。8.4交換排序【例8.3】一組元素的關(guān)鍵字序列為(37,19,43,22,22,89,26,92)，使用冒泡排序和快速排序?qū)υ撛剡M(jìn)行排序，并輸出冒泡排序和快速排序的每趟排序結(jié)果。冒泡排序前：3719432222892692第1趟排序結(jié)果:1937222243268992第2趟排序結(jié)果:1922223726438992第3趟排序結(jié)果:1922222637438992第4趟排序結(jié)果:1922222637438992冒泡排序結(jié)果：1922222637438992快速排序前：3719432222892692第1趟排序結(jié)果:[26192222]37[894392]第2趟排序結(jié)果:[221922]26[37894392]第3趟排序結(jié)果:[19]22[222637894392]第4趟排序結(jié)果:[192222263743]89[92]快速排序結(jié)果：19222226374389928.5歸并排序2路歸并排序的主要思想：假設(shè)元素的個(gè)數(shù)是n，將每個(gè)元素作為一個(gè)有序的子序列，然后將相鄰的兩個(gè)子序列兩兩合并，得到個(gè)長(zhǎng)度為2的有序子序列。繼續(xù)將相鄰的兩個(gè)有序子序列兩兩合并，得到個(gè)長(zhǎng)度為4的有序子序列。依次類推，重復(fù)執(zhí)行以上操作，直到有序序列合并為1個(gè)為止。這樣就得到了一個(gè)有序序列。8.5歸并排序一組元素序列的關(guān)鍵字序列為(37,19,43,22,57,89,26,92)，2路歸并排序的過程如圖8.14所示。8.5歸并排序publicvoidMerge(ints[],intt[],intlow,intmid,inthigh)

//將有序的s[low...mid]和s[mid+1..high]歸并為有序的t[low..high]

{

inti=low;intj=mid+1;intk=low;

while(i<=mid&&j<=high)//將s中元素由小到大地合并到t

{

if(s[i]<=s[j])

{

t[k]=s[i];

i++;

}

else{

t[k]=s[j];

j++;}

k++;

}

while(i<=mid)//將剩余的s[i..mid]復(fù)制到t

{

t[k]=s[i];

k++;

i++;}

while(j<=high)//將剩余的s[j..high]復(fù)制到t

{

t[k]=s[j];

k++;

j++;}

}以撲克牌排序?yàn)槔?。每張撲克牌有兩個(gè)“排序碼”：有兩個(gè)關(guān)鍵字：花色和面值。其有序關(guān)系為：

花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A

可以把所有撲克牌排成以下次序：

2,…,

A,

2,…,

A,

2,…,

A,

2,…,

A花色相同的情況下，比較面值。8.6基數(shù)排序前面的排序方法主要通過關(guān)鍵字值之間的比較和移動(dòng)而基數(shù)排序不需要關(guān)鍵字之間的比較。對(duì)52張撲克牌按以下次序排序：

2<

3<……<

A<

2<

3<……<

A<

2<

3<……<

A<

2<

3<……<

A兩個(gè)關(guān)鍵字：花色（

<

<

<

）面值（2<3<……<A）并且“花色”重要性高于“面值”8.6基數(shù)排序多關(guān)鍵字排序最高位優(yōu)先最低位優(yōu)先鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序鏈?zhǔn)交鶖?shù)排序8.6基數(shù)排序十進(jìn)制數(shù)比較可以看作是一個(gè)多關(guān)鍵字排序先對(duì)最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2（如面值）排序，又分成若干更小的子