第11章查找與排序

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

2、找順序查找 要求： 查找表必須采用線性表。基本思想：用給定值依次與線性表中每個元素的關(guān)鍵字進(jìn)行比較。如果某個元素的關(guān)鍵字與給定值相同，則查找成功；如果找遍全表也沒有發(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ù)存放在一個數(shù)組中，從數(shù)組的第一個元素被查找的數(shù)存放在一個數(shù)組中，從數(shù)組的第一個元素開始，依次往下比較，直到找到要找的元素為止。開始，依次往下比較，直到找到要找的元素為

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;順序查找的平均查找長度評價：在用順序查找方法完成查找時，每進(jìn)行一次成功查找需要的平均比較次數(shù)約為表長度的一半，因此，它的效率較低。適用于在查找表較小的情況下進(jìn)行查找。)(21111nOninCPASLniinii二分查找（折半查找）二分查找（折半查找）要求： 必須以順序方式存儲線性表 線性表中所有數(shù)據(jù)元素必須按照關(guān)鍵字有序排列基本思想：

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

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

6、Houston5Detroit4Denver3Chicago2Boston1Atlanta0lowhighmid0 1 2 3 4 5 6 7 8 9 105 13 19 21 37 56 64 75 80 88 92找找21例如例如 key = 21 的查找過程的查找過程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 的查找過程的查找過程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

8、37 56 64 75 80 88 92lowhigh5 13 19 21 37 56 64 75 80 88 92當(dāng)下界當(dāng)下界low大于上界大于上界high時，則說明表中時，則說明表中沒有關(guān)鍵字等于沒有關(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ù)模板及其測試程序二分查找函數(shù)模板及其測試程序#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ù)組中的位置。對于n個元素的數(shù)組，在最壞的情況下所要查找的元素必須查到查找區(qū)間只剩下一個元素時才能找到或者能確定該元素根本不在數(shù)組中。二分查找優(yōu)

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

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

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

15、空，則新結(jié)點(diǎn)為二叉排序樹的根結(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)插入到左子樹中去，否則，小于根結(jié)點(diǎn)的值，則將新結(jié)點(diǎn)插入到左子樹中去，否則，插入到右子樹中去。此插入過程是遞歸進(jìn)行的。插入到右子樹中去。此插入過程是遞歸進(jìn)行的。 設(shè)有整數(shù)序列設(shè)有整數(shù)序列47,23,56,15,26,89,將其中的值依次插入將其中的值依次插入二叉排序樹二叉排序樹568947231526152326475689中序遍歷結(jié)果：中序遍歷結(jié)果：對二叉排序樹進(jìn)行中序遍歷可以得到一個數(shù)據(jù)元素由小到大對二叉排序樹進(jìn)行中序遍歷可以得到一

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

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

18、。方法二：用被刪除結(jié)點(diǎn)在中序遍歷序列中的直接前驅(qū)結(jié)方法二：用被刪除結(jié)點(diǎn)在中序遍歷序列中的直接前驅(qū)結(jié)點(diǎn)（該結(jié)點(diǎn)的右子樹也一定為空）代替被刪除的結(jié)點(diǎn)，點(diǎn)（該結(jié)點(diǎn)的右子樹也一定為空）代替被刪除的結(jié)點(diǎn)，然后刪除這個前驅(qū)結(jié)點(diǎn)。然后刪除這個前驅(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用中序遍歷該二叉樹得到的直接后繼用中序遍歷

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

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

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

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

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

24、開放地址法和鏈地址法解決沖突的方法：開放地址法和鏈地址法u 開放地址法：處理用數(shù)組存儲哈希表時出現(xiàn)的沖突開放地址法：處理用數(shù)組存儲哈希表時出現(xiàn)的沖突發(fā)生沖突時按某種規(guī)則形成一個地址探查序列發(fā)生沖突時按某種規(guī)則形成一個地址探查序列按序列順序逐個檢查各地址單元，直至找到一個未被占按序列順序逐個檢查各地址單元，直至找到一個未被占用的單元為止用的單元為止將發(fā)生沖突的數(shù)據(jù)元素存入該地址單元中。將發(fā)生沖突的數(shù)據(jù)元素存入該地址單元中。 線性探查序列線性探查序列 平方探查序列平方探查序列設(shè)哈希表的長度是設(shè)哈希表的長度是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è)哈希表的長度設(shè)哈希表的長度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等概率時查找成功的平均查找長度：等概率時查找成功的平均查找長度：ASL=（1+1+1+1+1+2+6）/ 7=13/7設(shè)哈希表的長度設(shè)哈希表的長度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, 平方探查地址序列：平方探查地址序列：將所有哈希地址相同的記錄都鏈接在同一單將所有哈希地址相同的記錄都鏈接在同一單鏈表中。鏈表中。哈希表中的每個存儲單元中不再存放數(shù)據(jù)元哈希表中的每個存儲單元中不再存放數(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哈希查找哈希表的查找過程和建表的過程相似，按哈希存儲哈希表的查找過程和建表的過程相似，按哈希存儲的方法進(jìn)行查找。的方法進(jìn)行查找。假設(shè)給定的關(guān)鍵字為假設(shè)給定的關(guān)鍵字為k:根據(jù)建表時構(gòu)造的哈希函數(shù)根據(jù)建表時構(gòu)造的哈希函數(shù)h，計算出哈希地址，計算出哈希地址h(k)，如果哈希表中該地址單元為空，則查找，如果哈希表中該地址單元為空，則查找

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

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

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

32、序直接插入排序 把把n n個元素的序列劃分為兩個子序列：一個為有序；另一個為無序個元素的序列劃分為兩個子序列：一個為有序；另一個為無序?qū)o序子序列中的元素依次取出插入到有序子序列中，直到無序子將無序子序列中的元素依次取出插入到有序子序列中，直到無序子序列為空，整個排序結(jié)束。序列為空，整個排序結(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)/對對A0An-1排序排序int i , j;T temp;for( i = 1 ; i 0 & temp Aj-1 ; j- )Aj = Aj-1;Aj = temp;算法分析算法

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

35、oid InsertionSort( T A , int n ) /對對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;選擇排序選擇排序 基本思想：每次從待排序的元素序列中選擇一個最小的元素將其附加到已排好序的元素序列的后面，直至全部元素排好序?yàn)橹埂Ｔ诔跏紩r，已排好序的元

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

37、2 2步：在步：在n-1n-1個數(shù)據(jù)元素中找出排序碼最小的數(shù)個數(shù)據(jù)元素中找出排序碼最小的數(shù) 據(jù)元素，與第據(jù)元素，與第2 2個元素交換個元素交換第第i i步：在步：在n-i+1n-i+1個數(shù)據(jù)元素中找出排序碼最小的個數(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)定算法，其平均時間復(fù)雜直接選擇排序算法是不穩(wěn)定算法，其平均時間復(fù)雜度為度為O(n2)，時間復(fù)雜度與元素的初態(tài)無關(guān)，時間復(fù)雜度與元素的初態(tài)無關(guān)template void SelectionSort(T A , int n)/對對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; 冒泡排序冒泡排序基本思想： 從待排序記錄集的一端（這里假定為低端）對相鄰的兩個元素（e0和e1，e1和e2，en-2和en-1）依次比較它們的排序碼，若不符合排序的順序要求，就將相應(yīng)的兩個元素互換，此過程稱為一趟冒泡排序，最多經(jīng)過n-1趟冒泡排序，排序工作即可完成。 每趟排序的結(jié)果是將待排序記錄集中排序碼最大的元素交換到待排序記錄集最后一個元素的位置。假設(shè)在一趟冒泡排序時，從ej+1以后沒有發(fā)生元素的互換，則說明ej+1以后的元素是已經(jīng)排好序的，下面只

40、需要在e0到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 1

41、0; i+)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)志置為真,有交換算法分析算法分析時間復(fù)雜度

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