第11章 查找與排序

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

2、 Ci為找到第i個元素時的比較次數 順序查找順序查找 要求： 查找表必須采用線性表。 基本思想：用給定值依次與線性表中每 個元素的關鍵字進行比較。如果某個元 素的關鍵字與給定值相同，則查找成功； 如果找遍全表也沒有發(fā)現滿足條件的元 素，則查找失敗。 算法實現： 順序表類和單鏈表類中的 search函數。 實現一：順序表類中實現順序查找的成員函數實現一：順序表類中實現順序查找的成員函數 /查找元素查找元素x并返回其下標，若元素不存在，則返回并返回其下標，若元素不存在，則返回-1 /被查找的數存放在一個數組中，從數組的第一個元素被查找的數存放在一個數組中，從數組的第一個元素 開始，依次往下比較，直

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; 順序查找的平均查找長度 評價：在用順序查找方法完成查找時， 每進行一次成功查找需要的平均比較次 數約為表長度的一半，因此，它的效率 較低。適用于在查找表較小的情況下進 行查找。 )( 2 11 11 nO n i n CPASL n i i n i i 二分查找（折半查找

4、）二分查找（折半查找） 要求： 必須以順序方式存儲線性表 線性表中所有數據元素必須按照關鍵字有序排列 基本思想：將給定值與處于順序表“中間位置” 上的元素的關鍵字進行比較，若相等則查找成 功；若給定值大于關鍵字則在表的后半部分繼 續(xù)進行二分查找，否則在表的前半部分繼續(xù)進 行二分查找。如此進行下去直至找到滿足條件 的元素，或當前查找區(qū)為空，此時查找失敗。 1.設表長為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.重復上述操作，直至low high時，查找失敗。 二分查找算法實現二分查找算法實現 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 當下界當下界low大于上界大于上界high時，則說明表中時，則說明表中 沒有關鍵字等于沒有關鍵字等于key的元素，查找不成功。的元素，查找不成功。 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3

9、 4 5 6 7 8 9 10 例：例：二分查找函數模板及其測試程序二分查找函數模板及其測試程序 #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; /查找成功，返回元素的下標查找成功，返回元素的下標 if( key Amid ) high=mid-1; /到表的前半部分查找到表的前半部分查找 else low =

10、mid + 1; /到表的后半部分查找到表的后半部分查找 return -1;/查找失敗，返回失敗標志查找失敗，返回失敗標志-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 ) 例：例：用遞歸方法實現二分查找函數模板用遞歸方法實現二分查找函數模板 #include using namespace std; template int BinSearch( T A , int low , int high , T key ) int mi

11、d; if(low high) return -1; /查找失敗，返回失敗標志查找失敗，返回失敗標志-1 else mid=(low + high) / 2; if( key = Amid ) return mid; /查找成功，返回元素的下標查找成功，返回元素的下標 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); 二分查找二分查找 在二分查找中，比較的次數取決于所要查找 的元素在數組中的位置。對于n個元素的數 組，在最壞的情況下所要查找的元素必須查 到查找區(qū)間只剩下一個元素時才能找到或者 能確定該元素根本不在數組中。 二分查找優(yōu)缺點二分查找優(yōu)缺點 優(yōu)點： 查找效率高 平均查找長度 缺點： 查找前要將表中元素按關鍵字有序排列 只適用于線性表的順序存儲。適用于那種一經 建立就很少改動而又經常需要查找的線性表。 )(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將數據集合中的數據元素存儲為一顆二將數據集合中的數據

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

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

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

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

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

19、列中的直接前驅結方法二：用被刪除結點在中序遍歷序列中的直接前驅結 點（該結點的右子樹也一定為空）代替被刪除的結點，點（該結點的右子樹也一定為空）代替被刪除的結點， 然后刪除這個前驅結點。然后刪除這個前驅結點。 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 后繼結點后繼結點 前驅結點前驅結點 將結點將結點50刪除刪除 中序遍歷結點序列：中序遍歷結點序列：10 15 30 33 35 10 15 30 33 35 3737 5050 5353 55 62 55 62 用中序遍歷該二

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

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

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

23、的。 如果關鍵字的可能值太多，而數組長度 是有限的，那么哈希函數就只能是多對 一的，就會產生碰撞。 哈希存儲哈希存儲(哈希表哈希表) 哈希存儲(哈希表)： 以數據元素的關鍵字以數據元素的關鍵字k為自變量，通過一定的函數關系計算為自變量，通過一定的函數關系計算 出對應的函數值出對應的函數值h(k)，把這個值解釋為數據元素的存儲地址，把這個值解釋為數據元素的存儲地址 并把數據元素存儲到相應的存儲單元內（這個過程稱為哈并把數據元素存儲到相應的存儲單元內（這個過程稱為哈 希）。希）。h(k)稱為哈希地址。稱為哈希地址。 例：設有一組關鍵字值例：設有一組關鍵字值85, 72, 49, 58, 15, 7

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

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

26、該地址單元中。 線性探查序列線性探查序列 平方探查序列平方探查序列 設哈希表的長度是設哈希表的長度是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兩種常用的地址探查方法：兩種常用的地址探查方法： 設哈希表的長度設哈希表的長度11，哈希函數是，哈希函數是h(k) = k % 11，將整數序列，將整數序列 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 設哈希表的長度設哈希表的長度11，哈希函數是，哈希函數是h(k) = k % 11，將整數序列，將整數序列 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、鏈表中。鏈表中。 哈希表中的每個存儲單元中不再存放數據元哈希表中的每個存儲單元中不再存放數據元 素而是存放相應單鏈表的頭指針素而是存放相應單鏈表的頭指針. 例例:給定關鍵字給定關鍵字19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函數為哈希函數為 H(key) = key % 7 鏈地址法鏈地址法 例例:給定關鍵字給定關鍵字 19, 1, 23, 14, 55, 68, 11, 82, 36 哈希函數為哈希函數為 H(key) = key % 7 鏈地址法鏈地址法 14 11 198268 55 36 1 23 0 1 2 5 4 3 6 哈希查找 哈希表的查找過程和建

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

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

32、算法存在著多個排序碼相同的元素，按照某種排序算法 排序后，這些元素的相對位置仍保持不變，則稱該排序后，這些元素的相對位置仍保持不變，則稱該 排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。 待排序數據：待排序數據：18 12 10 12 30 16 排序后數據：排序后數據：10 12 12 16 18 30 穩(wěn)定穩(wěn)定 排序后數據：排序后數據：10 12 12 16 18 30 不穩(wěn)定不穩(wěn)定 插入排序插入排序 基本思想：把元素ei(0in) 依次插入到 由S中前i個元素組成的已經排好序的序列 e0, e1, ,ei-1的適當位置上，插入后S的 前i+1個元素仍為有序。 直

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

34、序列中，直到無序子 序列為空，整個排序結束。序列為空，整個排序結束。 若待排序數據元素的排序碼序列是（若待排序數據元素的排序碼序列是（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 直接插入排序直接插入排序 直接插入排序的函數模板示例：直接插入排序的函數模板示例： 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; 算法分析算法分析 時間復雜度與元素的初始狀態(tài)有關時間復雜度與元素的初始狀態(tài)有關 初態(tài)為正序時（最好情形）復雜度為初態(tài)為正序時（最好情形）復雜度為O(n) 初態(tài)為逆序時（最壞情形）復雜度是O(n2) 直接插入排序的平均時間復雜度是O(n2) 直接插入

36、排序是穩(wěn)定的排序算法 適用于一個長度較短、接近有序的序列 3440752050 5040207534 二分插入排序二分插入排序 在插入ei時，e0, e1, , ei-1是一個有序序 列，所以可以用二分查找法尋找ei的插入 位置，從而減少比較次數。 二分插入排序是穩(wěn)定的排序算法，其平均 時間復雜度仍是O(n2) 二分插入排序的函數模板示例：二分插入排序的函數模板示例： 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；當ki時，交換ei與ek 的值。經上述n-1次的選擇和交換后，排 序工作即已完成。 直接選擇排序直接選擇排序 用逐個比較的辦法從待排序的元素序列中 選出最小的元素。 直接選擇排序直接選擇排序 第第1 1步：在步：在n n個數據元素中找出排序碼最小的數據個數據元素中找出排序碼最小的數據 元素，與第元素，與第1 1個元素交換個元素交換 第第2 2步：在步：在n-1n-1個數據元素中找出排序碼最小的數個數據元素中找出排序碼最小的數 據元素，與第據元素，與第2 2個元素交換個元素交換 第第i i步：在步：

39、在n-i+1n-i+1個數據元素中找出排序碼最小的個數據元素中找出排序碼最小的 數據元素，與第數據元素，與第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) 直接選擇排序直接選擇排序 直接選擇排序函數模板：直接選擇排序函數模板： 直接選擇排序算法是不穩(wěn)定算法，其平均時間復雜直接選擇排序算法是不穩(wěn)定算

40、法，其平均時間復雜 度為度為O(n2)，時間復雜度與元素的初態(tài)無關，時間復雜度與元素的初態(tài)無關 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; /記當前最小元素的下標記當前最小元素的下標 if(k != i) /Ai不是最小，與不是最小，與Ak交換交換 temp = Ai; Ai = Ak;

41、Ak = temp; 冒泡排序冒泡排序 基本思想： 從待排序記錄集的一端（這里假定為低端）對相鄰 的兩個元素（e0和e1，e1和e2，en-2和en-1）依次比較 它們的排序碼，若不符合排序的順序要求，就將相應 的兩個元素互換，此過程稱為一趟冒泡排序，最多經 過n-1趟冒泡排序，排序工作即可完成。 每趟排序的結果是將待排序記錄集中排序碼最大的 元素交換到待排序記錄集最后一個元素的位置。假設 在一趟冒泡排序時，從ej+1以后沒有發(fā)生元素的互換， 則說明ej+1以后的元素是已經排好序的，下面只需要在 e0到ej范圍內進行新一趟的冒泡排序，即待排序記錄集 是從e0到ej，下一趟只需從e0到ej范圍內

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; /標志置為假，假設未交換 for(int j = 0 ; j aj+1) temp = aj; aj = aj+1; aj+1 = temp; change = true; /標志置為真,有 交換 算法分析算法分析 時間復雜度與元素的初始狀態(tài)有關。 最好情況下的時間復雜度為O(n)。若待排序 元

44、素序列已經有序，則排序工作經一趟處理 就可結束。此時，對元素排序碼的比較次數 為最小值n-1，且沒有元素的互換。 最壞情況下的時間復雜度為O(n2)。若待排序 元素序列為逆序，則需要進行n-1趟冒泡。 每趟要進行n-i-1次排序碼的比較和n-i-1次元 素的互換。 平均時間復雜度為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 待 排 序 記 錄 第一趟排序結束第一趟排序結束 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 第二趟排序結束