【文章內(nèi)容簡介】 交換排序 關(guān)鍵問題⑵： 如何實(shí)現(xiàn)一次劃分？ j j i i i j i j j j 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 解決方法： 對分割得到的兩個子序列遞歸地執(zhí)行快速排序。 交換排序 關(guān)鍵問題⑶：如何處理分割得到的兩個待排序子序列？ 13 27 38 65 50 49 55 13 27 50 38 49 55 65 i j i j 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 快速排序的時間性能分析 交換排序 快速排序的時間性能 快速排序遞歸的深度 每次劃分軸值的選取 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 最好情況： 每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為 O(nlog2n)。 快速排序的時間性能分析 交換排序 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)。 最好情況： 每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為 O(nlog2n)。 快速排序的時間性能分析 交換排序 平均情況： 為 O(nlog2n)。 ) ( ) 1 ( 2 1 2 1 1 n O n n i n n i = = ? = ） （ 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 選擇排序的主要操作是 選擇 ，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼 最小的記錄，添加到有序序列中。 選擇排序 有序序列 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)鍵問題 ? ⑴如何在待排序序列中選出關(guān)鍵碼最小的記錄？ ⑵如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置？ 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 簡單選擇排序示例 08 21 i = 2 最小者 08 交換 21,08 最小者 16 交換 25,16 最小者 21 交換 49,21 21 28 i = 1 25 16 49 08 i = 3 21 08 28 49 選擇排序 28 49 16 25 16 25 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) i = 4 最小者 25 交換 25,28 i = 5 最小者 28 不交換 選擇排序 簡單選擇排序示例 49 21 08 28 16 25 49 21 08 16 28 25 49 21 08 16 28 25 無序區(qū)只有 一個記錄 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 解決方法： 設(shè)置一個整型變量 index， 用于記錄在一趟比較的過程中關(guān)鍵碼 最小的記錄位置。 選擇排序 關(guān)鍵問題⑴： 如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？ 21 28 25 16 49 08 index index index 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 算法描述： index=i。 for (j=i+1。 j=n。 j++) if (r[j]r[index]) index=j。 解決方法： 設(shè)置一個整型變量 index， 用于記錄在一趟比較的過程中關(guān)鍵碼 最小的記錄位置。 關(guān)鍵問題⑴： 如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？ 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 解決方法： 第 i趟簡單選擇排序的待排序區(qū)間是 r[i] ~ r[n]， 則 r[i]是無序 區(qū)第一個記錄，所以，將 index所記載的關(guān)鍵碼最小的記錄與 r[i]交換 。 選擇排序 關(guān)鍵問題⑵：如何確定 最小記錄的最終位置？ 算法描述： if (index!=i) r[i]←→r[index] 。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) void selectSort ( int r[ ], int n) { for ( i=1。 in。 i++) { index=i。 for (j=i+1。 j=n。 j++) if (r[j]r[index]) index=j。 if (index!=i) r[i]==r[index]。 } } 簡單選擇排序算法 選擇排序 第八章 排序技術(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次 選擇排序 空間性能： 需一個輔助空間。 穩(wěn)定性： 是一種穩(wěn)定的排序算法。 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)。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 堆排序 改進(jìn)的著眼點(diǎn)： 如何 減少 關(guān)鍵碼間的 比較 次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個排序過程的效率。 選擇排序 減少關(guān)鍵碼間的比較次數(shù) 查找最小值的同時，找出較小值 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 堆的定義 堆是具有下列性質(zhì)的 完全二叉樹 ：每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為 小根堆 ），或每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為 大根堆 ）。 選擇排序 18 20 32 36 45 25 38 50 40 28 1. 小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。 2. 較小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 堆的定義 堆是具有下列性質(zhì)的 完全二叉樹 ：每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為 小根堆 ），或每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為 大根堆 ）。 選擇排序 50 38 45 40 28 36 32 20 18 28 1. 大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。 2. 較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 堆和序列的關(guān)系 選擇排序 將堆用順序存儲結(jié)構(gòu)來存儲，則堆對應(yīng)一組序列。 50 38 45 40 28 36 32 20 18 28 50 38 45 32 36 40 28 20 18 28 1 2 3 4 5 6 7 8 9 10 采用順序存儲 第八章 排序技術(shù) 數(shù)據(jù)結(jié)構(gòu) 基本思想： 首先將待排序的記錄序列構(gòu)造成一個