第11章查找與排序

1、第十一章第十一章 查找和排序查找和排序本章內(nèi)容本章內(nèi)容查找查找 順序查找順序查找 二分查找二分查找 二叉排序樹(shù)查找二叉排序樹(shù)查找 哈希查找哈希查找 平均查找長(zhǎng)度的計(jì)算平均查找長(zhǎng)度的計(jì)算n 排序排序l 直接插入排序直接插入排序l 直接選擇排序直接選擇排序l 冒泡排序冒泡排序查找的基本概念查找的基本概念查找：在數(shù)據(jù)元素集合(查找表)中查找關(guān)鍵字與給定值相等的數(shù)據(jù)元素。關(guān)鍵字：數(shù)據(jù)元素中的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)值，它可以惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。平均查找長(zhǎng)度(ASL)：iniiCPASL1式中，n為查找表的長(zhǎng)度；pi為查找第i個(gè)元素的概率，在等概率情況下pi等于1/n； Ci為找到第i個(gè)元素時(shí)的比較次數(shù)順序查

2、找順序查找 要求： 查找表必須采用線性表?；舅枷耄河媒o定值依次與線性表中每個(gè)元素的關(guān)鍵字進(jìn)行比較。如果某個(gè)元素的關(guān)鍵字與給定值相同，則查找成功；如果找遍全表也沒(méi)有發(fā)現(xiàn)滿足條件的元素，則查找失敗。算法實(shí)現(xiàn)： 順序表類和單鏈表類中的search函數(shù)。 實(shí)現(xiàn)一：順序表類中實(shí)現(xiàn)順序查找的成員函數(shù)實(shí)現(xiàn)一：順序表類中實(shí)現(xiàn)順序查找的成員函數(shù)/查找元素查找元素x并返回其下標(biāo)，若元素不存在，則返回并返回其下標(biāo)，若元素不存在，則返回-1/被查找的數(shù)存放在一個(gè)數(shù)組中被查找的數(shù)存放在一個(gè)數(shù)組中，從數(shù)組的第一個(gè)元素從數(shù)組的第一個(gè)元素開(kāi)始，依次往下比較，直到找到要找的元素為止。開(kāi)始，依次往下比較，直到找到要找的元素為止

3、。int Seqlist:Search ( char x ) int i = 0; for( i = 0; i next; while( p != NULL ) if( p - data = x ) break; p = p - next; return p;順序查找的平均查找長(zhǎng)度評(píng)價(jià)：在用順序查找方法完成查找時(shí)，每進(jìn)行一次成功查找需要的平均比較次數(shù)約為表長(zhǎng)度的一半，因此，它的效率較低。適用于在查找表較小的情況下進(jìn)行查找。)(21111nOninCPASLniinii二分查找（折半查找）二分查找（折半查找）要求： 必須以順序方式存儲(chǔ)線性表 線性表中所有數(shù)據(jù)元素必須按照關(guān)鍵字有序排列基本思想：將

4、給定值與處于順序表“中間位置”上的元素的關(guān)鍵字進(jìn)行比較，若相等則查找成功；若給定值大于關(guān)鍵字則在表的后半部分繼續(xù)進(jìn)行二分查找，否則在表的前半部分繼續(xù)進(jìn)行二分查找。如此進(jìn)行下去直至找到滿足條件的元素，或當(dāng)前查找區(qū)為空，此時(shí)查找失敗。1.設(shè)表長(zhǎng)為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn)，k為給定值。2.初始時(shí)，令 low = 0，high = n - 1，mid= (low+high)/2讓 k 與 mid 指向的記錄比較 若 k = rmid ，查找成功 若 k rmid ，則low = mid + 13.重復(fù)上述操作，直至low high時(shí)，查找失敗。二分查找算法

5、實(shí)現(xiàn)二分查找算法實(shí)現(xiàn)0Atlanta1Boston2Chicago3Denver4Detroit5Houston6Los Angeles7Miami8New York9Philadelphia10 San Francisco11 Seattle Seattle 11San Francisco10Philadelphia9New York8Miami7Los Angeles6Houston5Detroit4Denver3Chicago2Boston1Atlanta0Seattle 11San Francisco10Philadelphia9New York8Miami7Los Angeles6H

6、ouston5Detroit4Denver3Chicago2Boston1Atlanta0lowhighmid0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92找找21例如例如 key = 21 的查找過(guò)程的查找過(guò)程low 指示查找區(qū)間的下界high 指示查找區(qū)間的上界mid = (low+high)/2lowhighmid5 13 19 21 37 56 64 75 80 88 920 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92lowhighmid0 1 2 3 4 5 6 7

7、 8 9 10例例key = 70 的查找過(guò)程的查找過(guò)程lowhighmid找找70 5 13 19 21 37 56 64 75 80 88 92lowhighmid 5 13 19 21 37 56 64 75 80 88 92low highmid 5 13 19 21 37 56 64 75 80 88 92lowhighmid0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 925 13 19 21 3

8、7 56 64 75 80 88 92lowhigh5 13 19 21 37 56 64 75 80 88 92當(dāng)下界當(dāng)下界low大于上界大于上界high時(shí)，則說(shuō)明表中時(shí)，則說(shuō)明表中沒(méi)有關(guān)鍵字等于沒(méi)有關(guān)鍵字等于key的元素，查找不成功。的元素，查找不成功。0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10例：例：二分查找函數(shù)模板及其測(cè)試程序二分查找函數(shù)模板及其測(cè)試程序#include using namespace std;template int BinSearch( T A , int low , int high , T key )int mid;

9、while(low = high)mid=(low + high) / 2;if( key = Amid ) return mid; /查找成功，返回元素的下標(biāo)查找成功，返回元素的下標(biāo)if( key Amid ) high=mid-1; /到表的前半部分查找到表的前半部分查找else low = mid + 1; /到表的后半部分查找到表的后半部分查找return -1;/查找失敗，返回失敗標(biāo)志查找失敗，返回失敗標(biāo)志-1int main()int a = 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , k = 7 , i;i = BinSearch(a , 0 , 7 , k)

10、;if( i = -1 )例：例：用遞歸方法實(shí)現(xiàn)二分查找函數(shù)模板用遞歸方法實(shí)現(xiàn)二分查找函數(shù)模板#include using namespace std;template int BinSearch( T A , int low , int high , T key )int mid;if(low high) return -1; /查找失敗，返回失敗標(biāo)志查找失敗，返回失敗標(biāo)志-1 elsemid=(low + high) / 2;if( key = Amid ) return mid; /查找成功，返回元素的下標(biāo)查找成功，返回元素的下標(biāo)if( key Amid ) BinSearch( A ,

11、 low , mid - 1 , key ); /到表的前半部分查找到表的前半部分查找else BinSearch( A , mid + 1 , high , key ); /到表的后半部分查找到表的后半部分查找 int main()int a = 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , k = 7 , i;i = BinSearch(a , 0 , 7 , k);二分查找二分查找在二分查找中，比較的次數(shù)取決于所要查找的元素在數(shù)組中的位置。對(duì)于n個(gè)元素的數(shù)組，在最壞的情況下所要查找的元素必須查到查找區(qū)間只剩下一個(gè)元素時(shí)才能找到或者能確定該元素根本不在數(shù)組中。二分查找優(yōu)缺

12、點(diǎn)二分查找優(yōu)缺點(diǎn)優(yōu)點(diǎn)： 查找效率高 平均查找長(zhǎng)度缺點(diǎn)： 查找前要將表中元素按關(guān)鍵字有序排列 只適用于線性表的順序存儲(chǔ)。適用于那種一經(jīng)建立就很少改動(dòng)而又經(jīng)常需要查找的線性表。)(log1) 1(log12122111nOnnnjnCPASLjkjinii搜索算法的效率搜索算法的效率順序搜索的平均時(shí)間性能 （1 + 2 + 3 + + n ) / n = ( n + 1 ) / 2二分查找的最壞情況的時(shí)間性能 n / 2 / 2 / 2 / 2 = 1 n=2k使用二分查找算法最多只需要k=log2n次比較即可K次次)(nO)(log2nO平均查找長(zhǎng)度：平均查找長(zhǎng)度：N和和log2N的值的值Nlo

13、g2N10310071000101,000,000201,000,000,00030二叉排序樹(shù)查找二叉排序樹(shù)查找n將數(shù)據(jù)集合中的數(shù)據(jù)元素存儲(chǔ)為一顆二將數(shù)據(jù)集合中的數(shù)據(jù)元素存儲(chǔ)為一顆二叉排序樹(shù)，叉排序樹(shù)， 然后按給定方法進(jìn)行查找。然后按給定方法進(jìn)行查找。二叉排序樹(shù)的定義：二叉排序樹(shù)的定義： 二叉排序樹(shù)或者是一棵空二叉樹(shù)，或者二叉排序樹(shù)或者是一棵空二叉樹(shù)，或者 是具有以下性質(zhì)的二叉樹(shù)：是具有以下性質(zhì)的二叉樹(shù)： 若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；值均小于根結(jié)點(diǎn)的值； 若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)

14、點(diǎn)的值均不小于根結(jié)點(diǎn)的值；值均不小于根結(jié)點(diǎn)的值； 左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。二叉排序樹(shù)二叉排序樹(shù)二叉排序樹(shù)：二叉排序樹(shù)：一種特殊的二叉樹(shù)，其特點(diǎn)是：左子樹(shù)上一種特殊的二叉樹(shù)，其特點(diǎn)是：左子樹(shù)上所有結(jié)點(diǎn)的值均小于其雙親結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的所有結(jié)點(diǎn)的值均小于其雙親結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于其雙親結(jié)點(diǎn)的值。值均大于或等于其雙親結(jié)點(diǎn)的值。 56894723152650308020901085403525238866不是二叉排序樹(shù)。不是二叉排序樹(shù)。 插入操作：插入操作：若二叉排序樹(shù)為空，則新結(jié)點(diǎn)為二叉排序樹(shù)的根結(jié)點(diǎn)；否若二叉排序樹(shù)為空

15、，則新結(jié)點(diǎn)為二叉排序樹(shù)的根結(jié)點(diǎn)；否則將新結(jié)點(diǎn)的關(guān)鍵字值和根結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行比較，若則將新結(jié)點(diǎn)的關(guān)鍵字值和根結(jié)點(diǎn)的關(guān)鍵字值進(jìn)行比較，若小于根結(jié)點(diǎn)的值，則將新結(jié)點(diǎn)插入到左子樹(shù)中去，否則，小于根結(jié)點(diǎn)的值，則將新結(jié)點(diǎn)插入到左子樹(shù)中去，否則，插入到右子樹(shù)中去。此插入過(guò)程是遞歸進(jìn)行的。插入到右子樹(shù)中去。此插入過(guò)程是遞歸進(jìn)行的。 設(shè)有整數(shù)序列設(shè)有整數(shù)序列47,23,56,15,26,89,將其中的值依次插入將其中的值依次插入二叉排序樹(shù)二叉排序樹(shù)568947231526152326475689中序遍歷結(jié)果：中序遍歷結(jié)果：對(duì)二叉排序樹(shù)進(jìn)行中序遍歷可以得到一個(gè)數(shù)據(jù)元素由小到大對(duì)二叉排序樹(shù)進(jìn)行中序遍歷可以得到一個(gè)

16、數(shù)據(jù)元素由小到大的有序序列。構(gòu)造二叉排序樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排的有序序列。構(gòu)造二叉排序樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。序的過(guò)程。 刪除操作：刪除操作：一個(gè)結(jié)點(diǎn)被刪除后，必須保證余下的結(jié)點(diǎn)仍然構(gòu)成一棵二一個(gè)結(jié)點(diǎn)被刪除后，必須保證余下的結(jié)點(diǎn)仍然構(gòu)成一棵二叉排序樹(shù)。下面分三種情況討論：叉排序樹(shù)。下面分三種情況討論：u 情況二：被刪除的結(jié)點(diǎn)至少有一棵空子樹(shù)，則用那棵非空子情況二：被刪除的結(jié)點(diǎn)至少有一棵空子樹(shù)，則用那棵非空子 樹(shù)的根成為其雙親結(jié)點(diǎn)的相應(yīng)子女樹(shù)的根成為其雙親結(jié)點(diǎn)的相應(yīng)子女50302510153533375362605553625550301015353337u 情況一：若被刪除

17、的是葉結(jié)點(diǎn)，則將對(duì)應(yīng)雙親結(jié)點(diǎn)指針域置空情況一：若被刪除的是葉結(jié)點(diǎn)，則將對(duì)應(yīng)雙親結(jié)點(diǎn)指針域置空u 情況三：被刪除的結(jié)點(diǎn)有兩棵非空的子樹(shù)情況三：被刪除的結(jié)點(diǎn)有兩棵非空的子樹(shù)方法一：找到被刪除結(jié)點(diǎn)在中序遍歷序列中的直接后繼結(jié)方法一：找到被刪除結(jié)點(diǎn)在中序遍歷序列中的直接后繼結(jié)點(diǎn)（它一定在被刪除結(jié)點(diǎn)的右子樹(shù)中），用此后繼結(jié)點(diǎn)的點(diǎn)（它一定在被刪除結(jié)點(diǎn)的右子樹(shù)中），用此后繼結(jié)點(diǎn)的值取代被刪除結(jié)點(diǎn)的值，然后刪除此后繼結(jié)點(diǎn)，由于被刪值取代被刪除結(jié)點(diǎn)的值，然后刪除此后繼結(jié)點(diǎn)，由于被刪除的后繼結(jié)點(diǎn)的左子樹(shù)一定是空子樹(shù)，所以刪除后繼結(jié)點(diǎn)除的后繼結(jié)點(diǎn)的左子樹(shù)一定是空子樹(shù)，所以刪除后繼結(jié)點(diǎn)的過(guò)程同情況二。的過(guò)程同情況二。

18、方法二：用被刪除結(jié)點(diǎn)在中序遍歷序列中的直接前驅(qū)結(jié)方法二：用被刪除結(jié)點(diǎn)在中序遍歷序列中的直接前驅(qū)結(jié)點(diǎn)（該結(jié)點(diǎn)的右子樹(shù)也一定為空）代替被刪除的結(jié)點(diǎn)，點(diǎn)（該結(jié)點(diǎn)的右子樹(shù)也一定為空）代替被刪除的結(jié)點(diǎn)，然后刪除這個(gè)前驅(qū)結(jié)點(diǎn)。然后刪除這個(gè)前驅(qū)結(jié)點(diǎn)。 50301015353337536255533010153533376255373010153533536255后繼結(jié)點(diǎn)后繼結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn) 將結(jié)點(diǎn)將結(jié)點(diǎn)50刪除刪除中序遍歷結(jié)點(diǎn)序列：中序遍歷結(jié)點(diǎn)序列：10 15 30 33 35 10 15 30 33 35 3737 5050 5353 55 62 55 62用中序遍歷該二叉樹(shù)得到的直接后繼用中序遍歷該

19、二叉樹(shù)得到的直接后繼結(jié)點(diǎn)代替該結(jié)點(diǎn)，刪除直接后繼結(jié)點(diǎn)結(jié)點(diǎn)代替該結(jié)點(diǎn)，刪除直接后繼結(jié)點(diǎn)用中序遍歷該二叉樹(shù)得到的直接前驅(qū)用中序遍歷該二叉樹(shù)得到的直接前驅(qū)結(jié)點(diǎn)代替該結(jié)點(diǎn)，刪除直接前驅(qū)結(jié)點(diǎn)結(jié)點(diǎn)代替該結(jié)點(diǎn)，刪除直接前驅(qū)結(jié)點(diǎn) 查找操作：查找操作：u 查找查找思路：思路：當(dāng)二叉排序樹(shù)不為空時(shí)，將給定值與根結(jié)點(diǎn)的值進(jìn)行比當(dāng)二叉排序樹(shù)不為空時(shí)，將給定值與根結(jié)點(diǎn)的值進(jìn)行比較，若相等則查找成功。如果給定值小于根結(jié)點(diǎn)的值，較，若相等則查找成功。如果給定值小于根結(jié)點(diǎn)的值，則在根結(jié)點(diǎn)的左子樹(shù)中繼續(xù)查找，否則在根結(jié)點(diǎn)的右子則在根結(jié)點(diǎn)的左子樹(shù)中繼續(xù)查找，否則在根結(jié)點(diǎn)的右子樹(shù)中繼續(xù)查找。當(dāng)待查找的二叉排序樹(shù)為空時(shí)，查找失樹(shù)中繼

20、續(xù)查找。當(dāng)待查找的二叉排序樹(shù)為空時(shí)，查找失敗。敗。u 平均查找長(zhǎng)度：平均查找長(zhǎng)度：)(log2nOASL 在二叉排序樹(shù)中查找成功時(shí)走過(guò)的是一條從根結(jié)點(diǎn)到所尋找結(jié)點(diǎn)的一條路徑，因此，二叉排序樹(shù)查找的平均查找長(zhǎng)度取決于二叉排序樹(shù)的深度。在二叉排序樹(shù)中查找關(guān)鍵字值等于在二叉排序樹(shù)中查找關(guān)鍵字值等于50,35,90,955030802090854035883250505030403550508090)(log2nOASL 平均查找長(zhǎng)度：平均查找長(zhǎng)度： 二叉排序樹(shù)的蛻變：二叉排序樹(shù)的蛻變：例如，由整數(shù)序列例如，由整數(shù)序列15,23,26,47,56,89 生成的二叉排序樹(shù)生成的二叉排序樹(shù)47568915

21、2326平均查找長(zhǎng)度與順序查找相同平均查找長(zhǎng)度與順序查找相同當(dāng)把一組有序值依次插入到一棵二叉排序樹(shù)時(shí)，生成的二叉排序樹(shù)將蛻變成一棵單支樹(shù)。哈希查找哈希查找UKT012.m-1哈希方法：使用函數(shù)將哈希方法：使用函數(shù)將U映射到表映射到表T0m-1 的下標(biāo)上的下標(biāo)上哈希函數(shù)哈希函數(shù): h(關(guān)鍵值關(guān)鍵值) 元素存儲(chǔ)地元素存儲(chǔ)地址址所有可能出現(xiàn)的關(guān)鍵字集合U實(shí)際存儲(chǔ)關(guān)鍵字集合K哈希表哈希表如果哈希函數(shù)是一一映射的，那么增、刪、改、查的復(fù)雜度都是O(1)的。如果關(guān)鍵字的可能值太多，而數(shù)組長(zhǎng)度是有限的，那么哈希函數(shù)就只能是多對(duì)一的，就會(huì)產(chǎn)生碰撞。哈希存儲(chǔ)哈希存儲(chǔ)(哈希表哈希表) 哈希存儲(chǔ)(哈希表)： 以數(shù)據(jù)

22、元素的關(guān)鍵字以數(shù)據(jù)元素的關(guān)鍵字k為自變量，通過(guò)一定的函數(shù)關(guān)系計(jì)算為自變量，通過(guò)一定的函數(shù)關(guān)系計(jì)算出對(duì)應(yīng)的函數(shù)值出對(duì)應(yīng)的函數(shù)值h(k)，把這個(gè)值解釋為數(shù)據(jù)元素的存儲(chǔ)地址，把這個(gè)值解釋為數(shù)據(jù)元素的存儲(chǔ)地址并把數(shù)據(jù)元素存儲(chǔ)到相應(yīng)的存儲(chǔ)單元內(nèi)（這個(gè)過(guò)程稱為哈并把數(shù)據(jù)元素存儲(chǔ)到相應(yīng)的存儲(chǔ)單元內(nèi)（這個(gè)過(guò)程稱為哈希）。希）。h(k)稱為哈希地址。稱為哈希地址。 例：設(shè)有一組關(guān)鍵字值例：設(shè)有一組關(guān)鍵字值85, 72, 49, 58, 15, 70, 90, 38， 哈希函數(shù)哈希函數(shù) h(k) = k mod 12。則對(duì)應(yīng)的哈希地址為：。則對(duì)應(yīng)的哈希地址為： 1, 0, 1, 10, 3, 10, 6, 2沖突

23、： 若有兩個(gè)不同的關(guān)鍵字若有兩個(gè)不同的關(guān)鍵字ki和和kj，即，即ki kj（i j）。）。 但但h(ki) = h(kj)，這種情況稱為沖突。，這種情況稱為沖突。 ki與與kj 稱為同義詞。稱為同義詞。 采用哈希技術(shù)要解決的兩個(gè)主要問(wèn)題：采用哈希技術(shù)要解決的兩個(gè)主要問(wèn)題：u 構(gòu)造一個(gè)好的哈希函數(shù)，使出現(xiàn)沖突的機(jī)會(huì)構(gòu)造一個(gè)好的哈希函數(shù)，使出現(xiàn)沖突的機(jī)會(huì)盡可能少些；盡可能少些；u設(shè)計(jì)一個(gè)有效的解決沖突的辦法設(shè)計(jì)一個(gè)有效的解決沖突的辦法哈希表哈希表碰撞的解決方法： 開(kāi)放地址法：如果一個(gè)元素該在的位置已經(jīng)有其他元素，就另安排一個(gè)空閑位置。 鏈地址法：映射到同一位置的元素被串成鏈表。 解決沖突的方法：開(kāi)

24、放地址法和鏈地址法解決沖突的方法：開(kāi)放地址法和鏈地址法u 開(kāi)放地址法：處理用數(shù)組存儲(chǔ)哈希表時(shí)出現(xiàn)的沖突開(kāi)放地址法：處理用數(shù)組存儲(chǔ)哈希表時(shí)出現(xiàn)的沖突發(fā)生沖突時(shí)按某種規(guī)則形成一個(gè)地址探查序列發(fā)生沖突時(shí)按某種規(guī)則形成一個(gè)地址探查序列按序列順序逐個(gè)檢查各地址單元，直至找到一個(gè)未被占按序列順序逐個(gè)檢查各地址單元，直至找到一個(gè)未被占用的單元為止用的單元為止將發(fā)生沖突的數(shù)據(jù)元素存入該地址單元中。將發(fā)生沖突的數(shù)據(jù)元素存入該地址單元中。 線性探查序列線性探查序列 平方探查序列平方探查序列設(shè)哈希表的長(zhǎng)度是設(shè)哈希表的長(zhǎng)度是m，發(fā)生沖突的地址是，發(fā)生沖突的地址是dd+1, d+2, , m-1, 0, 1, , d-

25、1(d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, l兩種常用的地址探查方法：兩種常用的地址探查方法：設(shè)哈希表的長(zhǎng)度設(shè)哈希表的長(zhǎng)度11，哈希函數(shù)是，哈希函數(shù)是h(k) = k % 11，將整數(shù)序列，將整數(shù)序列54,77,94,89,14,45,76存入哈希表。按存入哈希表。按線性探查法線性探查法處理沖突處理沖突 例例1012346789105477948954 % 11 = 1077 % 11 = 094 % 11 = 689 % 11 = 114 % 11 = 345 % 11 = 1 (沖突沖突)76 % 11 = 10 (沖突沖突)144576線性探查法建立

26、哈希表線性探查法建立哈希表5 線性探查地址序列線性探查地址序列d+1, d+2, , m-1, 0, 1, , d-1等概率時(shí)查找成功的平均查找長(zhǎng)度：等概率時(shí)查找成功的平均查找長(zhǎng)度：ASL=（1+1+1+1+1+2+6）/ 7=13/7設(shè)哈希表的長(zhǎng)度設(shè)哈希表的長(zhǎng)度11，哈希函數(shù)是，哈希函數(shù)是h(k) = k % 11，將整數(shù)序列，將整數(shù)序列54,77,94,89,14,45,76存入哈希表。按平方探查法處理沖突存入哈希表。按平方探查法處理沖突 例例20123456789105477948954 % 11 = 1077 % 11 = 094 % 11 = 689 % 11 = 114 % 11

27、= 345 % 11 = 1 (沖突沖突)76 % 11 = 10 (沖突沖突)144576平方探查法建立哈希表平方探查法建立哈希表(d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, 平方探查地址序列：平方探查地址序列：將所有哈希地址相同的記錄都鏈接在同一單將所有哈希地址相同的記錄都鏈接在同一單鏈表中。鏈表中。哈希表中的每個(gè)存儲(chǔ)單元中不再存放數(shù)據(jù)元哈希表中的每個(gè)存儲(chǔ)單元中不再存放數(shù)據(jù)元素而是存放相應(yīng)單鏈表的頭指針?biāo)囟谴娣畔鄳?yīng)單鏈表的頭指針.例例:給定關(guān)鍵字給定關(guān)鍵字19, 1, 23, 14, 55, 68, 11, 82, 36哈希函數(shù)為哈希函數(shù)為 H(key)

28、 = key % 7 鏈地址法鏈地址法例例:給定關(guān)鍵字給定關(guān)鍵字 19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函數(shù)為哈希函數(shù)為 H(key) = key % 7 鏈地址法鏈地址法 14 11 198268 5536 1 23 0125436哈希查找哈希表的查找過(guò)程和建表的過(guò)程相似，按哈希存儲(chǔ)哈希表的查找過(guò)程和建表的過(guò)程相似，按哈希存儲(chǔ)的方法進(jìn)行查找。的方法進(jìn)行查找。假設(shè)給定的關(guān)鍵字為假設(shè)給定的關(guān)鍵字為k:根據(jù)建表時(shí)構(gòu)造的哈希函數(shù)根據(jù)建表時(shí)構(gòu)造的哈希函數(shù)h，計(jì)算出哈希地址，計(jì)算出哈希地址h(k)，如果哈希表中該地址單元為空，則查找，如果哈希表中該地址單元為空，則查找失

29、敗。失敗。否則，將該地址中記錄的關(guān)鍵字與給定值比較，否則，將該地址中記錄的關(guān)鍵字與給定值比較，如果相等，則查找成功；如果不等，則按建表如果相等，則查找成功；如果不等，則按建表時(shí)設(shè)定的處理沖突方法查找下一個(gè)地址。如此時(shí)設(shè)定的處理沖突方法查找下一個(gè)地址。如此反復(fù)下去，直到某個(gè)地址單元為空（查找失?。┓磸?fù)下去，直到某個(gè)地址單元為空（查找失?。┗蛘哧P(guān)鍵字比較相等（查找成功）為止?；蛘哧P(guān)鍵字比較相等（查找成功）為止。 排序的基本概念排序的基本概念排序排序：將文件中的記錄按排序碼非遞減：將文件中的記錄按排序碼非遞減(或非遞增或非遞增)的順序重新排列。的順序重新排列。排序碼排序碼：數(shù)據(jù)元素中的一個(gè)或多個(gè)數(shù)據(jù)

30、項(xiàng)。排序碼：數(shù)據(jù)元素中的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)。排序碼可以是關(guān)鍵字，也可以是其他若干數(shù)據(jù)項(xiàng)的組合。可以是關(guān)鍵字，也可以是其他若干數(shù)據(jù)項(xiàng)的組合。排序算法的穩(wěn)定性排序算法的穩(wěn)定性：如果在待排序的元素序列中，：如果在待排序的元素序列中，存在著多個(gè)排序碼相同的元素，按照某種排序算法存在著多個(gè)排序碼相同的元素，按照某種排序算法排序后，這些元素的相對(duì)位置仍保持不變，則稱該排序后，這些元素的相對(duì)位置仍保持不變，則稱該排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。 待排序數(shù)據(jù)：待排序數(shù)據(jù)：18 12 10 12 30 16 排序后數(shù)據(jù)：排序后數(shù)據(jù)：10 12 12 16 18 30 穩(wěn)定穩(wěn)

31、定 排序后數(shù)據(jù)：排序后數(shù)據(jù)：10 12 12 16 18 30 不穩(wěn)定不穩(wěn)定插入排序插入排序基本思想：把元素ei(0in) 依次插入到由S中前i個(gè)元素組成的已經(jīng)排好序的序列e0, e1, ,ei-1的適當(dāng)位置上，插入后S的前i+1個(gè)元素仍為有序。直接插入排序直接插入排序 以順序查找的辦法找到要插入的元素在已排好序的元素序列中應(yīng)處的位置。 所有元素分成兩個(gè)集合：已排序記錄集和待排序記錄集。初始時(shí)，已排序記錄集只有一個(gè)元素，即e0，待排序記錄集是所有剩余元素。然后每次從待排序記錄集中選取一個(gè)元素，使用順序查找的方法，找到其在已排序記錄集中的位置，將其插入到該位置，直到待排序記錄集為空。直接插入排序

32、直接插入排序 把把n n個(gè)元素的序列劃分為兩個(gè)子序列：一個(gè)為有序；另一個(gè)為無(wú)序個(gè)元素的序列劃分為兩個(gè)子序列：一個(gè)為有序；另一個(gè)為無(wú)序?qū)o(wú)序子序列中的元素依次取出插入到有序子序列中，直到無(wú)序子將無(wú)序子序列中的元素依次取出插入到有序子序列中，直到無(wú)序子序列為空，整個(gè)排序結(jié)束。序列為空，整個(gè)排序結(jié)束。若待排序數(shù)據(jù)元素的排序碼序列是（若待排序數(shù)據(jù)元素的排序碼序列是（1818，1212，1010，1212，3030，1616） 16 30 12 10 12 16 30 12 10 30 18 12 12 10 16 30 12 16 30 16 18 12 18 12 10 18 12 12 1018

33、18 30 16 12 12 10 第第1趟趟 第第2趟趟 第第3 3趟趟 第第4 4趟趟 第第5趟趟 初始狀態(tài)初始狀態(tài)未排序未排序已排序已排序直接插入排序直接插入排序例：例：待排序記錄為待排序記錄為50,20,75,34,403440752050直接插入排序直接插入排序 直接插入排序的函數(shù)模板示例：直接插入排序的函數(shù)模板示例：template void InsertionSort(T A, int n)/對(duì)對(duì)A0An-1排序排序int i , j;T temp;for( i = 1 ; i 0 & temp Aj-1 ; j- )Aj = Aj-1;Aj = temp;算法分析算法分析時(shí)間復(fù)

34、雜度與元素的初始狀態(tài)有關(guān)時(shí)間復(fù)雜度與元素的初始狀態(tài)有關(guān)初態(tài)為正序時(shí)（最好情形）復(fù)雜度為初態(tài)為正序時(shí)（最好情形）復(fù)雜度為O(n)初態(tài)為逆序時(shí)（最壞情形）復(fù)雜度是O(n2) 直接插入排序的平均時(shí)間復(fù)雜度是O(n2)直接插入排序是穩(wěn)定的排序算法適用于一個(gè)長(zhǎng)度較短、接近有序的序列34407520505040207534二分插入排序二分插入排序在插入ei時(shí)，e0, e1, , ei-1是一個(gè)有序序列，所以可以用二分查找法尋找ei的插入位置，從而減少比較次數(shù)。二分插入排序是穩(wěn)定的排序算法，其平均時(shí)間復(fù)雜度仍是O(n2) 二分插入排序的函數(shù)模板示例：二分插入排序的函數(shù)模板示例：template void I

35、nsertionSort( T A , int n ) /對(duì)對(duì)0An-1排序排序int i , j , low , high , mid; T temp; for(i = 1 ; i n ; i+ ) temp = ai; low = 0; high = i - 1; while(low = high) mid = (low + high) / 2; if( temp = low ; j-)Aj+1 = Aj;Alow = temp;選擇排序選擇排序 基本思想：每次從待排序的元素序列中選擇一個(gè)最小的元素將其附加到已排好序的元素序列的后面，直至全部元素排好序?yàn)橹?。在初始時(shí)，已排好序的元素序列為空

36、，待排序的元素序列中包括了需要排序的所有元素。直接選擇排序直接選擇排序基本思想：用逐個(gè)比較的辦法從待排序的元素序列中選出最小的元素。依次對(duì)i=0, 1, 2, ,n-2分別執(zhí)行如下的選擇和交換步驟：在元素序列ei, ei+1, , en-1中選擇出最小的元素ek；當(dāng)ki時(shí)，交換ei與ek的值。經(jīng)上述n-1次的選擇和交換后，排序工作即已完成。直接選擇排序直接選擇排序 用逐個(gè)比較的辦法從待排序的元素序列中選出最小的元素。直接選擇排序直接選擇排序 第第1 1步：在步：在n n個(gè)數(shù)據(jù)元素中找出排序碼最小的數(shù)據(jù)個(gè)數(shù)據(jù)元素中找出排序碼最小的數(shù)據(jù) 元素，與第元素，與第1 1個(gè)元素交換個(gè)元素交換第第2 2步：

37、在步：在n-1n-1個(gè)數(shù)據(jù)元素中找出排序碼最小的數(shù)個(gè)數(shù)據(jù)元素中找出排序碼最小的數(shù) 據(jù)元素，與第據(jù)元素，與第2 2個(gè)元素交換個(gè)元素交換第第i i步：在步：在n-i+1n-i+1個(gè)數(shù)據(jù)元素中找出排序碼最小的個(gè)數(shù)據(jù)元素中找出排序碼最小的 數(shù)據(jù)元素，與第數(shù)據(jù)元素，與第i i元素交換元素交換 未排序未排序已排序已排序163018101216301812301612121016301816301812101212101812121012183016121210第第1趟趟(i=0)第第2趟趟(i=1)第第3趟趟(i=2)第第4 4趟趟(i=3)第第5趟趟(i=4) 初始狀態(tài)初始狀態(tài)直接選擇排序直接選擇排序

38、直接選擇排序函數(shù)模板：直接選擇排序函數(shù)模板： 直接選擇排序算法是不穩(wěn)定算法，其平均時(shí)間復(fù)雜直接選擇排序算法是不穩(wěn)定算法，其平均時(shí)間復(fù)雜度為度為O(n2)，時(shí)間復(fù)雜度與元素的初態(tài)無(wú)關(guān)，時(shí)間復(fù)雜度與元素的初態(tài)無(wú)關(guān)template void SelectionSort(T A , int n)/對(duì)對(duì)A0An-1排序排序 int i , j , k , temp; for(i = 0 ; i n-1 ; i+) /n-1趟選擇趟選擇 k = i; /假定假定Ai最小最小 for( j = i + 1 ; j n ; j+ ) if( Aj Ak ) k = j; /記當(dāng)前最小元素的下標(biāo)記當(dāng)前最小元素的

39、下標(biāo) if(k != i) /Ai不是最小，與不是最小，與Ak交換交換 temp = Ai; Ai = Ak; Ak = temp; 冒泡排序冒泡排序基本思想： 從待排序記錄集的一端（這里假定為低端）對(duì)相鄰的兩個(gè)元素（e0和e1，e1和e2，en-2和en-1）依次比較它們的排序碼，若不符合排序的順序要求，就將相應(yīng)的兩個(gè)元素互換，此過(guò)程稱為一趟冒泡排序，最多經(jīng)過(guò)n-1趟冒泡排序，排序工作即可完成。 每趟排序的結(jié)果是將待排序記錄集中排序碼最大的元素交換到待排序記錄集最后一個(gè)元素的位置。假設(shè)在一趟冒泡排序時(shí)，從ej+1以后沒(méi)有發(fā)生元素的互換，則說(shuō)明ej+1以后的元素是已經(jīng)排好序的，下面只需要在e0

40、到ej范圍內(nèi)進(jìn)行新一趟的冒泡排序，即待排序記錄集是從e0到ej，下一趟只需從e0到ej范圍內(nèi)進(jìn)行。冒泡排序（交換排序）冒泡排序（交換排序）冒冒泡泡排排序序76654913582797第一趟第一趟第三趟第三趟第四趟第四趟第二趟第二趟977665491358279776655849132797766558492713977665584927139776655849271397766558492713第五趟第五趟第六趟第六趟初始狀態(tài)初始狀態(tài)#include void main() int a10; for(int i= 0 ; i ai; int temp; for(i = 0 ; i 10; i+

41、)for(int j = 0 ; j aj+1) temp = aj;aj = aj+1;aj+1= temp; #include void main() int a10; for(int i = 0; i ai; bool change = true; int temp; for(i = 0 ; i 10 & change ; i+)change = false; /標(biāo)志置為假，假設(shè)未交換for(int j = 0 ; j aj+1) temp = aj;aj = aj+1;aj+1 = temp;change = true; /標(biāo)志置為真,有交換算法分析算法分析時(shí)間復(fù)雜度與元素的初始狀態(tài)有

42、關(guān)。最好情況下的時(shí)間復(fù)雜度為O(n)。若待排序元素序列已經(jīng)有序，則排序工作經(jīng)一趟處理就可結(jié)束。此時(shí)，對(duì)元素排序碼的比較次數(shù)為最小值n-1，且沒(méi)有元素的互換。最壞情況下的時(shí)間復(fù)雜度為O(n2)。若待排序元素序列為逆序，則需要進(jìn)行n-1趟冒泡。每趟要進(jìn)行n-i-1次排序碼的比較和n-i-1次元素的互換。平均時(shí)間復(fù)雜度為O(n2)。冒泡排序算法是穩(wěn)定的。97275813496576待排序記錄LastExchangeIndex279758134965762758971349657627581397496576275813499765762758134965977627581349657697待排序記錄第一趟排序結(jié)束第一趟排序結(jié)束27581349657697待排序記錄已排序記錄27581349657697待排序記錄2758134965769727135849657697271349586576972713495865769727134958657697第二趟排序結(jié)束第二趟排序結(jié)束待排序記錄27134958657697待排序記錄已排序記錄LastExchangeIndex第三趟排序結(jié)束第三趟排序結(jié)束27134958657697待排序記錄已排序記錄LastExchangeIndex977665584