[工學(xué)]第12章_縮小規(guī)模算法-資料下載頁
2025-10-10 00:16本頁面
【正文】 //輸出本趟排序的結(jié)果 printf(%5d,r[k].key)。 printf(\n)。 i++。 } } 電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 32 選擇排序的基本思想是：每一趟 (例如第 i 趟， i = 1, …, n1) 在后面的 ni+1 個(gè)待排序?qū)ο笾羞x出關(guān)鍵字最小的對(duì)象 , 作為有序?qū)ο笮蛄械牡? i 個(gè)對(duì)象。待到第 n1 趟作完，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。 選擇排序 (Selection Sort)（不講） ?基本步驟為： i從 1開始，直到 n1，進(jìn)行 n1趟排序，第 i 趟的排序過程為： 在一組對(duì)象r[i]～ r[n] (i=1,2,…,n 1)中選擇具有最小關(guān)鍵字的對(duì)象；并和第 i 個(gè)對(duì)象進(jìn)行交換； 電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 33 簡單選擇排序的算法 void SelectSort(SqList *L) { for (int i=1。 iLlength。++i) { int k=i。 for (int j=i+1。j=Llength。++j) if (Lr[k].key Lr[j].key) k=j。 if (i!=k){ temp=Lr[i]。 Lr[i]=Lr[k]。 Lr[k]=temp。 } } } 電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 34 21 25 49 25* 16 08 1 2 3 4 5 6 21 25* i = 1 49 25 16 25 16 08 49 08 25* 49 21 i = 2 i = 3 08 16 25* 25 21 初始 最小者 08 交換 21,08 最小者 16 交換 25,16 最小者 21 交換 49,21 電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 35 49 25* 1 2 3 4 5 6 25* i = 5 25 16 08 49 25* 49 21 結(jié)果 i = 4 08 16 25 21 最小者 25* 無交換 最小者 25 無交換 25 21 16 08 各趟排序后的結(jié)果 電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 36 1 2 3 4 5 6 49 16 08 25* 49 21 08 25* 25 21 i =2時(shí)選擇排序的過程 i k j 49 25 08 25* 16 21 i k j 49 ? 25 25* ? 25 16 25 i k j 16 25 , k=5 電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 37 49 25 08 25* 16 21 0 1 2 3 4 5 i k j 21 ? 16 k 指示當(dāng)前序列中最小者 算法分析 ?直接選擇排序的關(guān)鍵字比較次數(shù) KCN與對(duì)象的初始排列無關(guān)。第 i 趟選擇具有最小關(guān)鍵字對(duì)象所需的比較次數(shù)總是 ni1 次，此處假定整個(gè)待排序?qū)ο笮蛄杏? n 個(gè)對(duì)象。因此，總的關(guān)鍵字比較次數(shù)為 電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 38 ?對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時(shí)候，對(duì)象的移動(dòng)次數(shù) RMN = 0，達(dá)到最少。 ?最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為 RMN = 3(n1)。 ???????? 20 211ninninK C N )()(電子工程學(xué)院 ?上一頁 ?下一頁 ?回主目錄 2021/11/10 39 習(xí)題 ? 設(shè)順序表為 { 1 1 1 23 4 52} ，畫出折半查找判定樹，計(jì)算查找 1 1 12所需的比較次數(shù)分別是多少？ ? 對(duì)關(guān)鍵字序列 19， 11， 27， 18， 33進(jìn)行快速排序，寫出每一趟的排序結(jié)果。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1