【文章內(nèi)容簡(jiǎn)介】 第 1趟 第 2趟 第 3趟 第 4趟 256， 301， 751， 129， 937， 863， 742， 694， 076， 438 076， 129， 256， 751， 937， 863， 742， 694， 301， 438 要求模擬算法實(shí)現(xiàn)步驟 256 076 301 129 751 256 ， ， ， 438， 301， 694， ， ， 863， 9 7751 076， 129， 256， 438， 301， 694， 742， 751， 863， 937 ， ， ， 301， ， ， ， ， ，438 076， 129， 256， 301， 438， 694， 742， 751， 863， 937 時(shí)間效率： O(nlog2n) —因?yàn)槊刻舜_定的元素呈指數(shù)增加 空間效率： O（ log2n） —因?yàn)樗惴ǖ倪f歸性，要用到?？臻g 穩(wěn) 定 性： 不穩(wěn)定 —因?yàn)榭蛇x任一元素為支點(diǎn)。 38 快速排序算法詳細(xì)分析： ?快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù) （新的 low和 high） 。 ?可以證明，函數(shù) quicksort的平均計(jì)算時(shí)間也是 O(nlog2n)。 實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè) 。 ?最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致，理想情況為 ?log2(n+1)? 。因此，要求存儲(chǔ)開(kāi)銷(xiāo)為 o(log2n)。 ?如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序，這是最理想的情況。此時(shí)，快速排序的趟數(shù)最少。 39 ?在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下， 其遞歸樹(shù)成為單支樹(shù) ，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。這樣，必須經(jīng)過(guò) n1 趟才能把所有對(duì)象定位，而且第 i 趟需要經(jīng)過(guò) ni 次關(guān)鍵碼比較才能找到第 i 個(gè)對(duì)象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到 n2/2 ? 快速排序是一個(gè) 不穩(wěn)定 的排序方法 40 討論 2. “快速排序 ” 是否真的比任何排序算法都快？ 設(shè)每個(gè)子表的支點(diǎn)都在中間（比較均衡），則： 第 1趟比較，可以確定 1個(gè)元素的位置； 第 2趟比較（ 2個(gè)子表），可以再確定 2個(gè)元素的位置； 第 3趟比較（ 4個(gè)子表），可以再確定 4個(gè)元素的位置； 第 4趟比較（ 8個(gè)子表），可以再確定 8個(gè)元素的位置； …… 只需 ?log2n? ＋ 1趟便可排好序。 ——基本上是！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！ 而且，每趟需要比較和移動(dòng)的元素也呈指數(shù)下降，加上編程時(shí)使用了交替逼近技巧，更進(jìn)一步減少了移動(dòng)次數(shù)，所以速度特別快。 教材 P276有證明：快速排序的平均排序效率為 O(nlog2n)； 但最壞情況 (例如已經(jīng)有序 )下仍為 O(n2),改進(jìn)措施見(jiàn) P277。 41 基本思想是 : 每一趟 (例如第 i 趟 , i = 0, 1, …, n2) 在后面 ni 個(gè)待排序?qū)ο笾羞x出排序碼最小的對(duì)象 , 作為有序?qū)ο笮蛄械牡? i 個(gè)對(duì)象。待到第 n2 趟作完 , 待排序?qū)ο笾皇Ｏ?1個(gè) , 就不用再選了。 選擇排序 42 ② 若它不是這組對(duì)象中的第一個(gè)對(duì)象 , 則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào) 。 ③ 在這組對(duì)象中剔除這個(gè)具有最小排序碼的對(duì)象 。 在剩下的對(duì)象 V[i+1]～ V[n1]中重復(fù)執(zhí)行第 ① 、 ② 步 , 直到剩余對(duì)象只有一個(gè)為止 。 ? 直接選擇排序是一種簡(jiǎn)單的排序方法 , 它的基本步驟是： ① 在一組對(duì)象 V[i]～ V[n1] 中選擇具有最小排序碼的對(duì)象； 直接選擇排序 (Select Sort) 43 21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 0 49 25 16 25 16 08 49 08 25* 49 21 i = 1 i = 2 08 16 25* 25 21 初始 最小者 08 交換 21,08 最小者 16 交換 25,16 最小者 21 交換 49,21 44 49 25* 0 1 2 3 4 5 25* i = 4 25 16 08 49 25* 49 21 結(jié)果 i = 3 08 16 25 21 最小者 25* 無(wú)交換 最小者 25 無(wú)交換 25 21 16 08 各趟排序后的結(jié)果 45 直接選擇排序的算法 typedef int SortData。 void SelectSort ( SortData V[ ], int n ) { for ( int i = 0。 i n1。 i++ ) { int k = i。 //選擇具有最小排序碼的對(duì)象 for ( int j = i+1。 j n。 j++) if ( V[j] V[k] ) k = j。 //當(dāng)前具最小排序碼的對(duì)象 if ( k != i ) //對(duì)換到第 i 個(gè)位置 Swap ( V[i], V[k] )。 } } 46 0 1 2 3 4 5 49 16 08 25* 49 21 08 25* 25 21 i =1時(shí)選擇排序的過(guò)程 i k j 49 25 08 25* 16 21 i k j 49 ? 25 25* ? 25 16 25 i k j 16 25 47 49 25 08 25* 16 21 0 1 2 3 4 5 i k j 21 ? 16 k 指示當(dāng)前序列中最小者 ? 直接選擇排序的 排序碼比較次數(shù) KCN 與對(duì)象的初始排列無(wú)關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏? n 個(gè)對(duì)象 , 則第 i 趟選擇具有最小排序碼對(duì)象所需的比較次數(shù) 總是 ni1 次 。總的排序碼比較次數(shù)為 ???????? 20 211ninninKCN )()(48 錦標(biāo)賽排序 (Tournament Tree Sort) ? 它的思想與體育比賽時(shí)的淘汰賽類似。首先取得 n 個(gè)對(duì)象的關(guān)鍵碼，進(jìn)行兩兩比較，得到 ?n/2? 個(gè)比較的優(yōu)勝者 (關(guān)鍵碼小者 )，作為第一步比較的結(jié)果保留下來(lái)。然后對(duì)這 ?n/2? 個(gè)對(duì)象再進(jìn)行關(guān)鍵碼的兩兩比較， … ，如此重復(fù)，直到選出一個(gè)關(guān)鍵碼最小的對(duì)象為止。 ? 在圖例中，最下面是對(duì)象排列的初始狀態(tài)，相當(dāng)于一棵滿二叉樹(shù)的葉結(jié)點(diǎn)，它存放的是所有參加排序的對(duì)象的關(guān)鍵碼。 49 ? 如果 n 不是 2的 k 次冪 ， 則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿足 2k1 n ? 2k 的 2k個(gè) 。 葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)關(guān)鍵碼兩兩比較的結(jié)果 。 最頂層是樹(shù)的根 。 08 Winner 21 08 08 63 25* 21 21 25 49 25* 16 08 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 50 勝者樹(shù)的概念 ? 每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn) ， 稱這種比賽樹(shù)為勝者樹(shù) 。 ? 位于最底層的葉結(jié)點(diǎn)叫做勝者樹(shù)的外結(jié)點(diǎn) ， 非葉結(jié)點(diǎn)稱為勝者樹(shù)的內(nèi)結(jié)點(diǎn) 。 每個(gè)結(jié)點(diǎn)除了存放對(duì)象的關(guān)鍵碼 data 外 ， 還存放了此對(duì)象是否要參選的標(biāo)志 Active 和此對(duì)象在滿二叉樹(shù)中的序號(hào) index。 ? 勝者樹(shù)最頂層是樹(shù)的根，表示最后選擇出來(lái)的具有最小關(guān)鍵碼的對(duì)象。 51 08 Winner (勝者 ) 21 08 08 63 25* 21 21 25 49 25* 16 08 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 形成初始勝者樹(shù)（最小關(guān)鍵碼上升到根） a[0] 關(guān)鍵碼比較次數(shù) : 6 52 16 Winner (勝者 ) 21 16 16 63 25* 21 21 25 49 25* 16 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 輸出冠軍并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) a[1] 關(guān)鍵碼比較次數(shù) : 2 53 21 Winner (勝者 ) 21 63 63 25* 21 21 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 輸出亞軍并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) a[2] 關(guān)鍵碼比較次數(shù) : 2 54 25 Winner (勝者 ) 25 63 63 25* 25 25 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 輸出第三名并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) a[3] 關(guān)鍵碼比較次數(shù) : 2 55 25* Winner (勝者 ) 25* 63 63 25* 49 25* 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 輸出第四名并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) a[4] 關(guān)鍵碼比較次數(shù) : 2 56 63 Winner (勝者 ) 63 63 63 tree[7] tree[8] tree[9] tree[10] tree[11] tree[12] tree[13] tree[14] 全部比賽結(jié)果輸出時(shí)樹(shù)的狀態(tài) a[6] 關(guān)鍵碼比較次數(shù) : 2 57 勝者樹(shù)數(shù)據(jù)結(jié)點(diǎn)類的定義 template class Type class DataNode { public: Type data。 //數(shù)據(jù)值 int index。 //結(jié)點(diǎn)在滿二叉樹(shù)中順序號(hào) int active。 //參選標(biāo)志： =1, 參選 , =0, 不參選 } 錦標(biāo)賽排序的算法 template class Type void TournamentSort ( Type a[ ], int n ) { DataNodeType *tree。 DataNodeType item。 58 int bottomRowSize = PowerOfTwo ( n )。 //乘冪值 int TreeSize = 2*bottomRowSize1。 //總結(jié)點(diǎn)個(gè)數(shù) int loadindex = bottomRowSize1。 //內(nèi)結(jié)點(diǎn)個(gè)數(shù) tree = new DataNodeType[TreeSize]。 int j = 0。 //從 a 向勝者樹(shù)外結(jié)點(diǎn)復(fù)制數(shù)據(jù) for ( int i = loadindex。 i TreeSize。 i++) { tree[i].index = i。 if ( j n ) { tree[i].active = 1。 tree[i].data = a[j++]。 } else tree[i].active = 0。 } i = loadindex。 //進(jìn)行初始比較選擇最小的項(xiàng) while ( i ) { 59 j = i。 while ( j 2*i ) { if ( !tree[j+1].active|| //勝者送入雙親