【正文】 5 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)整勝者樹后樹的狀態(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)整勝者樹后樹的狀態(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í)樹的狀態(tài) a[6] 關(guān)鍵碼比較次數(shù) : 2 57 勝者樹數(shù)據(jù)結(jié)點(diǎn)類的定義 template class Type class DataNode { public: Type data。 每個(gè)結(jié)點(diǎn)除了存放對(duì)象的關(guān)鍵碼 data 外 ， 還存放了此對(duì)象是否要參選的標(biāo)志 Active 和此對(duì)象在滿二叉樹中的序號(hào) index。 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 勝者樹的概念 ? 每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn) ， 稱這種比賽樹為勝者樹 。 葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)關(guān)鍵碼兩兩比較的結(jié)果 。 ? 在圖例中，最下面是對(duì)象排列的初始狀態(tài)，相當(dāng)于一棵滿二叉樹的葉結(jié)點(diǎn)，它存放的是所有參加排序的對(duì)象的關(guān)鍵碼。首先取得 n 個(gè)對(duì)象的關(guān)鍵碼，進(jìn)行兩兩比較，得到 ?n/2? 個(gè)比較的優(yōu)勝者 (關(guān)鍵碼小者 )，作為第一步比較的結(jié)果保留下來。設(shè)整個(gè)待排序?qū)ο笮蛄杏? n 個(gè)對(duì)象 , 則第 i 趟選擇具有最小排序碼對(duì)象所需的比較次數(shù) 總是 ni1 次 。 //當(dāng)前具最小排序碼的對(duì)象 if ( k != i ) //對(duì)換到第 i 個(gè)位置 Swap ( V[i], V[k] )。 j n。 i++ ) { int k = i。 void SelectSort ( SortData V[ ], int n ) { for ( int i = 0。 在剩下的對(duì)象 V[i+1]～ V[n1]中重復(fù)執(zhí)行第 ① 、 ② 步 , 直到剩余對(duì)象只有一個(gè)為止 。 選擇排序 42 ② 若它不是這組對(duì)象中的第一個(gè)對(duì)象 , 則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào) 。 41 基本思想是 : 每一趟 (例如第 i 趟 , i = 0, 1, …, n2) 在后面 ni 個(gè)待排序?qū)ο笾羞x出排序碼最小的對(duì)象 , 作為有序?qū)ο笮蛄械牡? i 個(gè)對(duì)象。 ——基本上是！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！ 而且，每趟需要比較和移動(dòng)的元素也呈指數(shù)下降，加上編程時(shí)使用了交替逼近技巧，更進(jìn)一步減少了移動(dòng)次數(shù)，所以速度特別快。 39 ?在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下， 其遞歸樹成為單支樹 ，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。 ?如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序，這是最理想的情況。 ?最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 ?log2(n+1)? 。 ?可以證明，函數(shù) quicksort的平均計(jì)算時(shí)間也是 O(nlog2n)。 原始序列： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438 第 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)。L) { QSort (L, 1, )。 QSort ( L, pivot+1, high )。L, int low, int high ) { if ( low high) { pivot = Partition ( L, low, high )。 return ok。 r[j] = r[i]。amp。 r[i] = r[j]。amp。 pivot=r[low].key。 j=high。 }//Partition 34 Low=high=3， 本趟停止，將支點(diǎn)定位并返回位置信息 例 2： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16， 08），請(qǐng)寫出快速排序算法的一趟實(shí)現(xiàn)過程。 //支點(diǎn)記錄到位； return low。 r[high]=r[low]。amp。 r[low]=r[high]。amp。 //以子表的首記錄作為支點(diǎn)記錄，放入 r[0]單元 （續(xù)下頁） 一趟快速排序算法 （針對(duì)一個(gè)子表的操作） 33 pivotkey=r[low].key。返回時(shí)，在支點(diǎn)之前的記錄均不大于它，支點(diǎn)之后的記錄均不小于它。 見教材 P275 int Partition(SqList amp。 基本思想： 優(yōu)點(diǎn)： 因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別快！ 前提： 順序存儲(chǔ)結(jié)構(gòu) 31 ( )， 設(shè)以首元素為樞軸中心 例 1： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16， 08），請(qǐng)寫出快速排序的算法步驟。此時(shí)的比較總次數(shù) KCN和記錄移動(dòng)次數(shù) RMN為： ??????????????11111233121nininninR M NnninKCN)()()()(30 2） 快速排序 從待排序列中任取一個(gè)元素 (例如取第一個(gè) ) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。 21， 25， 49， 25*， 16， 08 21， 25， 25*， 16， 08 ， 49 21， 25， 16， 08 ， 25*， 49 21， 16， 08 ， 25， 25*， 49 16， 08 ， 21， 25， 25*， 49 08， 16， 21， 25， 25*， 49 初態(tài)： 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 29 冒泡排序的算法分析 時(shí)間效率： O（ n2) —因?yàn)橐紤]最壞情況 空間效率： O（ 1） —只在交換時(shí)用到一個(gè)緩沖單元 穩(wěn) 定 性： 穩(wěn)定 —25和 25*在排序前后的次序未改變 詳細(xì)分析： ?最好情況： 初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做 n1 次關(guān)鍵碼比較，不移動(dòng)對(duì)象。 優(yōu)點(diǎn)： 每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。 兩種排序方法的中間狀態(tài)分別描述如后： 25 原始序列： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438 [256， 301]， 751， 129， 937， 863， 742， 694， 076， 438 [256， 301， 751]， 129， 937， 863， 742， 694， 076， 438 [129， 256， 301， 751]， 937， 863， 742， 694， 076， 438 [129， 256， 301， 751， 937]， 863， 742， 694， 076， 438 [129， 256， 301， 751， 863， 937]， 742， 694， 076， 438 [129， 256， 301， 742， 751， 863， 937]， 694， 076， 438 [129， 256， 301， 694， 742， 751， 863， 937]， 076， 438 [076， 129， 256， 301， 694， 742， 751， 863， 937]， 438 [076， 129， 256， 301， 438， 694， 742， 751， 863， 937] 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 第 6趟 第 7趟 第 8趟 第 9趟 26 原始序列： 256， 301， 751， 129， 937， 863， 742， 694， 076， 438 (取 dk=5,3,1) 256， 301， 751， 129， 937， 863， 742， 694， 076， 438 ， ， ， ， ， ， ， ， ， ， 694， ， ， ， ， 751， ， ， ， 076， ， ， ， ， 129， ， ， ， 4 8， ， ， ， ， 9 7第 1趟 dk=5 第 2趟 dk=3 第 3趟 dk=1 256， 301， 694， 076， 438， 863， 742， 751， 129， 937 ， ， ， ， ， ， ， ， ，076， ， ， 25 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 129， ， ， 694， ， ， 863，076， 301， 129， 256， 438， 694， 742， 751， 863， 937 ， ， ， ， ， ， ， ， ， 129， 256， 301， ， ， ， ， ，27 交換排序 兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹埂?r[0].keyr[j].key)。 j0 amp。 23 void ShellInsert(SqList amp。 Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出 ， 當(dāng) n很大時(shí) ， 關(guān)鍵碼平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在 到 的范圍內(nèi) 。L， int dlta[ ]， int t){ //按增量序列 dlta[0… t1]對(duì)順序表 L作 Shell排序 for(k=0； kt； ++k) ShellSort(L， dlta[k])； //增量為 dlta[k]的一趟插入排序 } // ShellSort 時(shí)間效率： 空間效率： O（ 1） ——因?yàn)閮H占用 1個(gè)緩沖單元 算法的穩(wěn)定性： 不穩(wěn)定 ——因?yàn)?49*排序后卻到了 49的前面 希爾排序算法 （主程序） 參見教材 P272 O(）～ O（ ） ——經(jīng)驗(yàn)公式 dk值依次裝在 dlta[t]中 22 附：希爾排序 算法分析 對(duì)特定的待排序?qū)ο笮蛄?， 可以準(zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù) 。 0 1 2 3 4 5 6 7 8 9 10 49 38 65 97 76 13 27 49* 55 04 初態(tài)： 第 1趟 (dk=5) 第 2趟 (dk=3) 第 3趟 (dk=1) 49 13 13 4938 27 65 49* 97 55 76 04 27 38 65 49* 975513 55 76045527 04 2704 49 49* 76 38 65 97 55 13 27 04 49 49* 38 76 65 97 13 27 04 49* 76 97 算法分析： 開始時(shí) dk 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展， dk 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，