【正文】 ，每個子序列中的記錄個數(shù)較少，從而排序速度較快；當(dāng)增量較小時，雖然每個子序列中記錄個數(shù)較多，但整個序列已基本有序，排序速度也較快。 交換排序 反序則 交換 ri rj 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 起泡排序 基本思想： 兩兩比較 相鄰 記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。 交換排序 關(guān)鍵問題⑴：如何記載一趟排序過程中交換的多個記錄？ 05 98 12 69 38 53 81 05 98 69 81 12 交換 38 交換 53 交換 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 交換排序 關(guān)鍵問題⑴：如何記載一趟排序過程中交換的多個記錄？ 算法描述： if （ r[j]r[j+1]） { r[j]←→r[j+1] ； exchange=j； } 解決方法： 設(shè)變量 exchange記載記錄交換的位置，則一趟排序后，exchange記載的一定是這一趟排序中記錄的最后一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。 在一趟排序后，從 exchange位置之后的記錄一定是有序的，所以 bound=exchange。 在一趟排序后，從 exchange位置之后的記錄一定是有序的，所以 bound=exchange。 for (j=1。 j++) if （ r[j]r[j+1]） { r[j]==r[j+1]； exchange=j； } 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 05 98 12 69 38 53 81 解決方法： 在每一趟起泡排序之前，令 exchange的初值為 0， 在以后的排序過程中，只要有記錄交換， exchange的值就會大于 0。 交換排序 關(guān)鍵問題⑶： 如何判別起泡排序的結(jié)束？ 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 解決方法： 在每一趟起泡排序之前，令 exchange的初值為 0， 在以后的排序過程中，只要有記錄交換， exchange的值就會大于 0。 交換排序 關(guān)鍵問題⑶： 如何判別起泡排序的結(jié)束？ 算法描述： while (exchange) { 執(zhí)行一趟起泡排序； } 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) void BubbleSort(int r[ ], int n) { exchange=n。 exchange=0； for (j=1。 j++) if (r[j]r[j+1]) { r[j]←→r[j+ 1]； exchange=j； } } } 起泡排序算法 交換排序 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 起泡排序的時間性能分析 最好情況 （ 正序 ） ： 交換排序 比較次數(shù)： n1 移動次數(shù)： 0 1 2 3 4 5 時間復(fù)雜度為 O(n)。 4 3 2 1 5 3 2 1 4 5 2 1 3 4 5 1 2 3 4 5 比較次數(shù)： 移動次數(shù)： 2 ) 1 ( 1 = ? = n n (ni) n1 i 2 ) 1 ( 1 = ? = n 3n 3(ni) n1 i 平均情況： 時間復(fù)雜度為 O(n2)。 交換排序 ⑴如何選擇軸值？ ⑵如何實現(xiàn)分割（稱一次劃分）？ ⑶如何處理分割得到的兩個待排序子序列？ ⑷如何判別快速排序的結(jié)束？ 需解決的關(guān)鍵問題 ? 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 選擇軸值的方法： ； ； 、最后一個記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個記錄的位置； 。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 13 65 27 50 38 49 55 j i 13 38 65 27 50 49 55 13 65 27 50 49 38 55 交換排序 關(guān)鍵問題⑵： 如何實現(xiàn)一次劃分？ j j i i i j i j j j 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 解決方法： 對分割得到的兩個子序列遞歸地執(zhí)行快速排序。 快速排序的時間性能分析 交換排序 T(n)≤2T(n/2)＋ n ≤2(2T(n/4)＋ n/2)＋ n＝ 4T(n/4)＋ 2n ≤4(2T(n/8)＋ n/4)＋ 2n＝ 8T(n/8)＋ 3n … … … ≤nT(1)＋ nlog2n＝ O(nlog2n) 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 最壞情況： 每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空），為 O(n2)。 快速排序的時間性能分析 交換排序 平均情況： 為 O(nlog2n)。 選擇排序 有序序列 r1 r2 ri1 ri rn rk …… … … 無序序列 rn ri+1 r1 r2 ri1 …… ri ri … … 交換 最小記錄 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 簡單選擇排序 基本思想： 第 i 趟在 ni+1（ i=1,2,… ,n1） 個記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第 i個記錄。 選擇排序 關(guān)鍵問題⑴： 如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？ 21 28 25 16 49 08 index index index 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 算法描述： index=i。 j=n。 解決方法： 設(shè)置一個整型變量 index， 用于記錄在一趟比較的過程中關(guān)鍵碼 最小的記錄位置。 選擇排序 關(guān)鍵問題⑵：如何確定 最小記錄的最終位置？ 算法描述： if (index!=i) r[i]←→r[index] 。 in。 for (j=i+1。 j++) if (r[j]r[index]) index=j。 } } 簡單選擇排序算法 選擇排序 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 簡單選擇排序算法的性能分析 移動次數(shù)： 最好情況 （ 正序 ） ： 0次 選擇排序 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 最壞情況： 3(n1)次 簡單選擇排序算法的性能分析 移動次數(shù)： 最好情況 （ 正序 ） ： 0次 選擇排序 空間性能： 需一個輔助空間。 4 5 2 3 1 5 2 3 4 1 5 3 4 1 2 5 4 1 2 3 5 1 2 3 4 比較次數(shù)： ) ( ) 1 ( 2 1 2 1 1 n O n n i n n i = = ? = ） （ 簡單選擇排序的時間復(fù)雜度為 O(n2)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個排序過程的效率。 選擇排序 18 20 32 36 45 25 38 50 40 28 1. 小根堆的根結(jié)點是所有結(jié)點的最小者。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 堆的定義 堆是具有下列性質(zhì)的 完全二叉樹 ：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值（稱為 小根堆 ），或每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（稱為 大根堆 ）。 2. 較大結(jié)點靠近根結(jié)點，但不絕對。 50 38 45 40 28 36 32 20 18 28 50