第11章 查找與排序

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

2、 Ci為找到第i個元素時的比較次數(shù) 順序查找順序查找 要求： 查找表必須采用線性表。 基本思想：用給定值依次與線性表中每 個元素的關(guān)鍵字進行比較。如果某個元 素的關(guān)鍵字與給定值相同，則查找成功； 如果找遍全表也沒有發(fā)現(xiàn)滿足條件的元 素，則查找失敗。 算法實現(xiàn)： 順序表類和單鏈表類中的 search函數(shù)。 實現(xiàn)一：順序表類中實現(xiàn)順序查找的成員函數(shù)實現(xiàn)一：順序表類中實現(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; 順序查找的平均查找長度 評價：在用順序查找方法完成查找時， 每進行一次成功查找需要的平均比較次 數(shù)約為表長度的一半，因此，它的效率 較低。適用于在查找表較小的情況下進 行查找。 )( 2 11 11 nO n i n CPASL n i i n i i 二分查找（折半查找

4、）二分查找（折半查找） 要求： 必須以順序方式存儲線性表 線性表中所有數(shù)據(jù)元素必須按照關(guān)鍵字有序排列 基本思想：將給定值與處于順序表“中間位置” 上的元素的關(guān)鍵字進行比較，若相等則查找成 功；若給定值大于關(guān)鍵字則在表的后半部分繼 續(xù)進行二分查找，否則在表的前半部分繼續(xù)進 行二分查找。如此進行下去直至找到滿足條件 的元素，或當(dāng)前查找區(qū)為空，此時查找失敗。 1.設(shè)表長為n，low、high和mid分別指向待查元素 所在區(qū)間的上界、下界和中點，k為給定值。 2.初始時， 令 low = 0，high = n - 1，mid= (low+high)/2 讓 k 與 mid 指向的記錄比較 若 k =

5、rmid ，查找成功 若 k rmid ，則low = mid + 1 3.重復(fù)上述操作，直至low high時，查找失敗。 二分查找算法實現(xiàn)二分查找算法實現(xiàn) 0Atlanta 1Boston 2Chicago 3Denver 4Detroit 5Houston 6Los Angeles 7Miami 8New York 9Philadelphi a 10 San Francisco 11 Seattle Seattle 11 San Francisco10 Philadelphia9 New York8 Miami7 Los Angeles6 Houston5 Detroit4 Denver

6、3 Chicago2 Boston1 Atlanta0 Seattle 11 San Francisco10 Philadelphia9 New York8 Miami7 Los Angeles6 Houston5 Detroit4 Denver3 Chicago2 Boston1 Atlanta0 lowhigh mid 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92 找找21例如例如 key = 21 的查找過程的查找過程 low 指示查找區(qū)間的下界 high 指示查找區(qū)間的上界 mid = (low+high)/2 lowhi

7、ghmid 5 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92 lowhighmid 0 1 2 3 4 5 6 7 8 9 10 例例key = 70 的查找過程的查找過程 lowhigh mid 找找70 5 13 19 21 37 56 64 75 80 88 92 lowhighmid 5 13 19 21 37 56 64 75 80 88 92 low high mid 5 13 19 21 37 56 64 75 80 88 92 low high mid 0

8、 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92 low high 5 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 10 0 1 2 3

9、 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; while(low = high) mid=(low + high) / 2; if( key = Amid ) return mid; /查找成功，返回元素的下標(biāo)查找成功，返回元素的下標(biāo) if( key Amid ) high=mid-1; /到表的前半部分查找到表的前半部分查找 else low =

10、mid + 1; /到表的后半部分查找到表的后半部分查找 return -1;/查找失敗，返回失敗標(biāo)志查找失敗，返回失敗標(biāo)志-1 int main() int a = 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , k = 7 , i; i = BinSearch(a , 0 , 7 , k); if( i = -1 ) 例：例：用遞歸方法實現(xiàn)二分查找函數(shù)模板用遞歸方法實現(xiàn)二分查找函數(shù)模板 #include using namespace std; template int BinSearch( T A , int low , int high , T key ) int mi

11、d; if(low high) return -1; /查找失敗，返回失敗標(biāo)志查找失敗，返回失敗標(biāo)志-1 else mid=(low + high) / 2; if( key = Amid ) return mid; /查找成功，返回元素的下標(biāo)查找成功，返回元素的下標(biāo) if( key Amid ) BinSearch( A , low , mid - 1 , key ); /到表的前半部分查找到表的前半部分查找 else BinSearch( A , mid + 1 , high , key ); /到表的后半部分查找到表的后半部分查找 int main() int a = 1 , 2 , 3

12、 , 4 , 5 , 6 , 7 , 8 , k = 7 , i; i = BinSearch(a , 0 , 7 , k); 二分查找二分查找 在二分查找中，比較的次數(shù)取決于所要查找 的元素在數(shù)組中的位置。對于n個元素的數(shù) 組，在最壞的情況下所要查找的元素必須查 到查找區(qū)間只剩下一個元素時才能找到或者 能確定該元素根本不在數(shù)組中。 二分查找優(yōu)缺點二分查找優(yōu)缺點 優(yōu)點： 查找效率高 平均查找長度 缺點： 查找前要將表中元素按關(guān)鍵字有序排列 只適用于線性表的順序存儲。適用于那種一經(jīng) 建立就很少改動而又經(jīng)常需要查找的線性表。 )(log1) 1(log 1 2 1 22 1 11 nOn n n

13、j n CPASL j k j i n i i 搜索算法的效率搜索算法的效率 順序搜索的平均時間性能 （1 + 2 + 3 + + n ) / n = ( n + 1 ) / 2 二分查找的最壞情況的時間性能 n / 2 / 2 / 2 / 2 = 1 n=2k 使用二分查找算法最多只需要k=log2n次比較即可 K次次 )(nO )(log 2 nO 平均查找長度： 平均查找長度： N和和log2N的值的值 Nlog2N 103 1007 100010 1,000,00020 1,000,000,00030 二叉排序樹查找二叉排序樹查找 n將數(shù)據(jù)集合中的數(shù)據(jù)元素存儲為一顆二將數(shù)據(jù)集合中的數(shù)據(jù)

14、元素存儲為一顆二 叉排序樹，叉排序樹， 然后按給定方法進行查找。然后按給定方法進行查找。 二叉排序樹的定義：二叉排序樹的定義： 二叉排序樹或者是一棵空二叉樹，或者二叉排序樹或者是一棵空二叉樹，或者 是具有以下性質(zhì)的二叉樹：是具有以下性質(zhì)的二叉樹： 若它的左子樹非空，則左子樹上所有結(jié)點的若它的左子樹非空，則左子樹上所有結(jié)點的 值均小于根結(jié)點的值；值均小于根結(jié)點的值； 若它的右子樹非空，則右子樹上所有結(jié)點的若它的右子樹非空，則右子樹上所有結(jié)點的 值均不小于根結(jié)點的值；值均不小于根結(jié)點的值； 左、右子樹本身又各是一棵二叉排序樹。左、右子樹本身又各是一棵二叉排序樹。 二叉排序樹二叉排序樹 二叉排序樹：

15、二叉排序樹：一種特殊的二叉樹，其特點是：左子樹上一種特殊的二叉樹，其特點是：左子樹上 所有結(jié)點的值均小于其雙親結(jié)點的值，右子樹上所有結(jié)點的所有結(jié)點的值均小于其雙親結(jié)點的值，右子樹上所有結(jié)點的 值均大于或等于其雙親結(jié)點的值。值均大于或等于其雙親結(jié)點的值。 56 89 47 23 1526 50 3080 2090 1085 40 3525 2388 66 不是二叉排序樹。不是二叉排序樹。 插入操作：插入操作： 若二叉排序樹為空，則新結(jié)點為二叉排序樹的根結(jié)點；否若二叉排序樹為空，則新結(jié)點為二叉排序樹的根結(jié)點；否 則將新結(jié)點的關(guān)鍵字值和根結(jié)點的關(guān)鍵字值進行比較，若則將新結(jié)點的關(guān)鍵字值和根結(jié)點的關(guān)鍵字

16、值進行比較，若 小于根結(jié)點的值，則將新結(jié)點插入到左子樹中去，否則，小于根結(jié)點的值，則將新結(jié)點插入到左子樹中去，否則， 插入到右子樹中去。此插入過程是遞歸進行的。插入到右子樹中去。此插入過程是遞歸進行的。 設(shè)有整數(shù)序列設(shè)有整數(shù)序列47,23,56,15,26,89,將其中的值依次插入將其中的值依次插入 二叉排序樹二叉排序樹 56 89 47 23 1526 152326475689 中序遍歷結(jié)果：中序遍歷結(jié)果： 對二叉排序樹進行中序遍歷可以得到一個數(shù)據(jù)元素由小到大對二叉排序樹進行中序遍歷可以得到一個數(shù)據(jù)元素由小到大 的有序序列。構(gòu)造二叉排序樹的過程即為對無序序列進行排的有序序列。構(gòu)造二叉排序樹的

17、過程即為對無序序列進行排 序的過程。序的過程。 刪除操作：刪除操作： 一個結(jié)點被刪除后，必須保證余下的結(jié)點仍然構(gòu)成一棵二一個結(jié)點被刪除后，必須保證余下的結(jié)點仍然構(gòu)成一棵二 叉排序樹。下面分三種情況討論：叉排序樹。下面分三種情況討論： u 情況二：被刪除的結(jié)點至少有一棵空子樹，則用那棵非空子情況二：被刪除的結(jié)點至少有一棵空子樹，則用那棵非空子 樹的根成為其雙親結(jié)點的相應(yīng)子女樹的根成為其雙親結(jié)點的相應(yīng)子女 50 30 25 10 15 35 3337 53 62 60 55 53 62 55 50 30 10 15 35 3337 u 情況一：若被刪除的是葉結(jié)點，則將對應(yīng)雙親結(jié)點指針域置空情況一：

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

19、列中的直接前驅(qū)結(jié)方法二：用被刪除結(jié)點在中序遍歷序列中的直接前驅(qū)結(jié) 點（該結(jié)點的右子樹也一定為空）代替被刪除的結(jié)點，點（該結(jié)點的右子樹也一定為空）代替被刪除的結(jié)點， 然后刪除這個前驅(qū)結(jié)點。然后刪除這個前驅(qū)結(jié)點。 50 30 10 15 35 3337 53 62 55 53 30 10 15 35 3337 62 55 37 30 10 15 35 33 53 62 55 后繼結(jié)點后繼結(jié)點 前驅(qū)結(jié)點前驅(qū)結(jié)點 將結(jié)點將結(jié)點50刪除刪除 中序遍歷結(jié)點序列：中序遍歷結(jié)點序列：10 15 30 33 35 10 15 30 33 35 3737 5050 5353 55 62 55 62 用中序遍歷該二

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

21、查找。當(dāng)待查找的二叉排序樹為空時，查找失樹中繼續(xù)查找。當(dāng)待查找的二叉排序樹為空時，查找失 敗。敗。 u 平均查找長度：平均查找長度： )(log2nOASL 在二叉排序樹中查找成功時走過的是一條從根結(jié)點到 所尋找結(jié)點的一條路徑，因此，二叉排序樹查找的平 均查找長度取決于二叉排序樹的深度。 在二叉排序樹中查找關(guān)鍵字值等于在二叉排序樹中查找關(guān)鍵字值等于50,35,90,95 50 3080 2090 85 40 35 8832 505050 30 40 35 5050 80 90 )(log2nOASL 平均查找長度：平均查找長度： 二叉排序樹的蛻變：二叉排序樹的蛻變： 例如，由整數(shù)序列例如，由整

22、數(shù)序列15,23,26,47,56,89 生成的二叉排序樹生成的二叉排序樹 47 56 89 15 23 26 平均查找長度與順序查找相同平均查找長度與順序查找相同 當(dāng)把一組有序值依次插入到一棵二叉排序樹時， 生成的二叉排序樹將蛻變成一棵單支樹。 哈希查找哈希查找 U K T 0 1 2 . . . m- 1 哈希方法：使用函數(shù)將哈希方法：使用函數(shù)將U映射到表映射到表T0m- 1 的下標(biāo)上的下標(biāo)上 哈希函數(shù)哈希函數(shù): h(關(guān)鍵值關(guān)鍵值) 元素存儲地元素存儲地 址址 所有可能出現(xiàn)的關(guān)鍵字集合U 實際存儲關(guān)鍵字集合K 哈希表哈希表 如果哈希函數(shù)是一一映射的，那么增、 刪、改、查的復(fù)雜度都是O(1)

23、的。 如果關(guān)鍵字的可能值太多，而數(shù)組長度 是有限的，那么哈希函數(shù)就只能是多對 一的，就會產(chǎn)生碰撞。 哈希存儲哈希存儲(哈希表哈希表) 哈希存儲(哈希表)： 以數(shù)據(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, 7

24、0, 90, 38， 哈希函數(shù)哈希函數(shù) h(k) = k mod 12。則對應(yīng)的哈希地址為：。則對應(yīng)的哈希地址為： 1, 0, 1, 10, 3, 10, 6, 2 沖突： 若有兩個不同的關(guān)鍵字若有兩個不同的關(guān)鍵字ki和和kj，即，即ki kj（i j）。）。 但但h(ki) = h(kj)，這種情況稱為沖突。，這種情況稱為沖突。 ki與與kj 稱為同義詞。稱為同義詞。 采用哈希技術(shù)要解決的兩個主要問題：采用哈希技術(shù)要解決的兩個主要問題： u 構(gòu)造一個好的哈希函數(shù)，使出現(xiàn)沖突的機會構(gòu)造一個好的哈希函數(shù)，使出現(xiàn)沖突的機會 盡可能少些；盡可能少些； u設(shè)計一個有效的解決沖突的辦法設(shè)計一個有效的解決

25、沖突的辦法 哈希表哈希表 碰撞的解決方法： 開放地址法：如果一個元素該在的位置已經(jīng)有 其他元素，就另安排一個空閑位置。 鏈地址法：映射到同一位置的元素被串成鏈表。 解決沖突的方法：開放地址法和鏈地址法解決沖突的方法：開放地址法和鏈地址法 u 開放地址法：處理用數(shù)組存儲哈希表時出現(xiàn)的沖突開放地址法：處理用數(shù)組存儲哈希表時出現(xiàn)的沖突 發(fā)生沖突時按某種規(guī)則形成一個地址探查序列發(fā)生沖突時按某種規(guī)則形成一個地址探查序列 按序列順序逐個檢查各地址單元，直至找到一個未被占按序列順序逐個檢查各地址單元，直至找到一個未被占 用的單元為止用的單元為止 將發(fā)生沖突的數(shù)據(jù)元素存入該地址單元中。將發(fā)生沖突的數(shù)據(jù)元素存入

26、該地址單元中。 線性探查序列線性探查序列 平方探查序列平方探查序列 設(shè)哈希表的長度是設(shè)哈希表的長度是m，發(fā)生沖突的地址是，發(fā)生沖突的地址是d d+1, d+2, , m-1, 0, 1, , d-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存入哈希表。按存入哈希表。按線性探查法線性探查法處理沖突處理沖突 例例1 01234678910 54 7794 89

27、54 % 11 = 10 77 % 11 = 0 94 % 11 = 6 89 % 11 = 1 14 % 11 = 3 45 % 11 = 1 (沖突沖突) 76 % 11 = 10 (沖突沖突) 14 4576 線性探查法建立哈希表線性探查法建立哈希表 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

28、,89,14,45,76存入哈希表。按平方探查法處理沖突存入哈希表。按平方探查法處理沖突 例例2 012345678910 5477 94 89 54 % 11 = 10 77 % 11 = 0 94 % 11 = 6 89 % 11 = 1 14 % 11 = 3 45 % 11 = 1 (沖突沖突) 76 % 11 = 10 (沖突沖突) 14 4576 平方探查法建立哈希表平方探查法建立哈希表 (d+12)%m, (d-12)%m, (d+22)%m, (d-22)%m, 平方探查地址序列：平方探查地址序列： 將所有哈希地址相同的記錄都鏈接在同一單將所有哈希地址相同的記錄都鏈接在同一單

29、鏈表中。鏈表中。 哈希表中的每個存儲單元中不再存放數(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) = key % 7 鏈地址法鏈地址法 例例:給定關(guān)鍵字給定關(guān)鍵字 19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函數(shù)為哈希函數(shù)為 H(key) = key % 7 鏈地址法鏈地址法 14 11 198268 55 36 1 23 0 1 2 5 4 3 6 哈希查找 哈希表的查找過程和建

30、表的過程相似，按哈希存儲哈希表的查找過程和建表的過程相似，按哈希存儲 的方法進行查找。的方法進行查找。 假設(shè)給定的關(guān)鍵字為假設(shè)給定的關(guān)鍵字為k: 根據(jù)建表時構(gòu)造的哈希函數(shù)根據(jù)建表時構(gòu)造的哈希函數(shù)h，計算出哈希地址，計算出哈希地址 h(k)，如果哈希表中該地址單元為空，則查找，如果哈希表中該地址單元為空，則查找 失敗。失敗。 否則，將該地址中記錄的關(guān)鍵字與給定值比較，否則，將該地址中記錄的關(guān)鍵字與給定值比較， 如果相等，則查找成功；如果不等，則按建表如果相等，則查找成功；如果不等，則按建表 時設(shè)定的處理沖突方法查找下一個地址。如此時設(shè)定的處理沖突方法查找下一個地址。如此 反復(fù)下去，直到某個地址單

31、元為空（查找失?。┓磸?fù)下去，直到某個地址單元為空（查找失?。?或者關(guān)鍵字比較相等（查找成功）為止?；蛘哧P(guān)鍵字比較相等（查找成功）為止。 排序的基本概念排序的基本概念 排序排序：將文件中的記錄按排序碼非遞減：將文件中的記錄按排序碼非遞減(或非遞增或非遞增) 的順序重新排列。的順序重新排列。 排序碼排序碼：數(shù)據(jù)元素中的一個或多個數(shù)據(jù)項。排序碼：數(shù)據(jù)元素中的一個或多個數(shù)據(jù)項。排序碼 可以是關(guān)鍵字，也可以是其他若干數(shù)據(jù)項的組合?？梢允顷P(guān)鍵字，也可以是其他若干數(shù)據(jù)項的組合。 排序算法的穩(wěn)定性排序算法的穩(wěn)定性：如果在待排序的元素序列中，：如果在待排序的元素序列中， 存在著多個排序碼相同的元素，按照某種排序

32、算法存在著多個排序碼相同的元素，按照某種排序算法 排序后，這些元素的相對位置仍保持不變，則稱該排序后，這些元素的相對位置仍保持不變，則稱該 排序算法是穩(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)定 排序后數(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個元素仍為有序。 直

33、接插入排序直接插入排序 以順序查找的辦法找到要插入的元素在已排好 序的元素序列中應(yīng)處的位置。 所有元素分成兩個集合：已排序記錄集和待排 序記錄集。初始時，已排序記錄集只有一個元 素，即e0，待排序記錄集是所有剩余元素。然 后每次從待排序記錄集中選取一個元素，使用 順序查找的方法，找到其在已排序記錄集中的 位置，將其插入到該位置，直到待排序記錄集 為空。 直接插入排序直接插入排序 把把n n個元素的序列劃分為兩個子序列：一個為有序；另一個為無序個元素的序列劃分為兩個子序列：一個為有序；另一個為無序 將無序子序列中的元素依次取出插入到有序子序列中，直到無序子將無序子序列中的元素依次取出插入到有序子

34、序列中，直到無序子 序列為空，整個排序結(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 10 18 18 30 16 12 12 10 第第1趟趟 第第2趟趟 第第3 3趟趟 第第4 4趟趟 第第5趟趟 初始狀態(tài)初始狀態(tài) 未排序未排序 已排序已排序 直接插入排序直接插入排序 例：例：待排序記錄為待排序記錄為50,20,75

35、,34,40 3440752050 直接插入排序直接插入排序 直接插入排序的函數(shù)模板示例：直接插入排序的函數(shù)模板示例： template void InsertionSort(T A, int n)/對對A0An-1排序排序 int i , j; T temp; for( i = 1 ; i 0 j- ) Aj = Aj-1; Aj = temp; 算法分析算法分析 時間復(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) 直接插入

36、排序是穩(wěn)定的排序算法 適用于一個長度較短、接近有序的序列 3440752050 5040207534 二分插入排序二分插入排序 在插入ei時，e0, e1, , ei-1是一個有序序 列，所以可以用二分查找法尋找ei的插入 位置，從而減少比較次數(shù)。 二分插入排序是穩(wěn)定的排序算法，其平均 時間復(fù)雜度仍是O(n2) 二分插入排序的函數(shù)模板示例：二分插入排序的函數(shù)模板示例： template void InsertionSort( T A , int n ) /對對0An-1排序排序 int i , j , low , high , mid; T temp; for(i = 1 ; i n ; i+

37、 ) temp = ai; low = 0; high = i - 1; while(low = high) mid = (low + high) / 2; if( temp = low ; j-) Aj+1 = Aj; Alow = temp; 選擇排序選擇排序 基本思想：每次從待排序的元素序列中 選擇一個最小的元素將其附加到已排好 序的元素序列的后面，直至全部元素排 好序為止。 在初始時，已排好序的元素序列為空， 待排序的元素序列中包括了需要排序的 所有元素。 直接選擇排序直接選擇排序 基本思想：用逐個比較的辦法從待排序 的元素序列中選出最小的元素。依次對 i=0, 1, 2, ,n-2分

38、別執(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個元素交換個元素交換 第第2 2步：在步：在n-1n-1個數(shù)據(jù)元素中找出排序碼最小的數(shù)個數(shù)據(jù)元素中找出排序碼最小的數(shù) 據(jù)元素，與第據(jù)元素，與第2 2個元素交換個元素交換 第第i i步：在步：

39、在n-i+1n-i+1個數(shù)據(jù)元素中找出排序碼最小的個數(shù)據(jù)元素中找出排序碼最小的 數(shù)據(jù)元素，與第數(shù)據(jù)元素，與第i i元素交換元素交換 未排序未排序 已排序已排序 1630181012 16301812 3016121210 163018 1630 18 1210 121210 18121210 12 183016121210 第第1趟趟(i=0) 第第2趟趟(i=1) 第第3趟趟(i=2) 第第4 4趟趟(i=3) 第第5趟趟(i=4) 初始狀態(tài)初始狀態(tài) 直接選擇排序直接選擇排序 直接選擇排序函數(shù)模板：直接選擇排序函數(shù)模板： 直接選擇排序算法是不穩(wěn)定算法，其平均時間復(fù)雜直接選擇排序算法是不穩(wěn)定算

40、法，其平均時間復(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)前最小元素的下標(biāo) if(k != i) /Ai不是最小，與不是最小，與Ak交換交換 temp = Ai; Ai = Ak;

41、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)排好序的，下面只需要在 e0到ej范圍內(nèi)進行新一趟的冒泡排序，即待排序記錄集 是從e0到ej，下一趟只需從e0到ej范圍內(nèi)

42、進行。 冒泡排序（交換排序）冒泡排序（交換排序） 冒冒 泡泡 排排 序序 76654913582797 第一趟第一趟 第三趟第三趟 第四趟第四趟 第二趟第二趟 97766549135827 97766558491327 97766558492713 97766558492713 97766558492713 97766558492713 第五趟第五趟 第六趟第六趟 初始狀態(tài)初始狀態(tài) #include void main() int a10; for(int i= 0 ; i ai; int temp; for(i = 0 ; i 10; i+) for(int j = 0 ; j aj+1)

43、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 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ù)雜度與元素的初始狀態(tài)有關(guān)。 最好情況下的時間復(fù)雜度為O(n)。若待排序 元

44、素序列已經(jīng)有序，則排序工作經(jīng)一趟處理 就可結(jié)束。此時，對元素排序碼的比較次數(shù) 為最小值n-1，且沒有元素的互換。 最壞情況下的時間復(fù)雜度為O(n2)。若待排序 元素序列為逆序，則需要進行n-1趟冒泡。 每趟要進行n-i-1次排序碼的比較和n-i-1次元 素的互換。 平均時間復(fù)雜度為O(n2)。 冒泡排序算法是穩(wěn)定的。 97 27 58 13 49 65 76 待 排 序 記 錄 LastExchangeIndex 27 97 58 13 49 65 76 27 58 97 13 49 65 76 27 58 13 97 49 65 76 27 58 13 49 97 65 76 27 58 13 49 65 97 76 27 58 13 49 65 76 97 待 排 序 記 錄 第一趟排序結(jié)束第一趟排序結(jié)束 27 58 13 49 65 76 97 待 排 序 記 錄 已排序記錄 27 58 13 49 65 76 97 待 排 序 記 錄 27 58 13 49 65 76 97 27 13 58 49 65 76 97 27 13 49 58 65 76 97 27 13 49 58 65 76 97 27 13 49 58 65 76 97 第二趟排序結(jié)束