[理學(xué)]大學(xué)教程零起點數(shù)據(jù)結(jié)構(gòu)--排序-閱讀頁
2024-12-23 00:50本頁面
【正文】 40 98 49 34 ?????? 122iiiirrrr46 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 12 36 27 65 81 73 55 40 98 49 14 47 堆排序的基本思想是： 首先將待排序的記錄序列 構(gòu)造一個堆 ，此時，選出了堆中所有記錄的 最小者或最大者 ，然后將它 從堆中移走 ，并將剩余的記錄 再調(diào)整成堆 ，這樣又找出了次?。ɑ虼未螅┑挠涗?，以此類推，直到堆中只有一個記錄為止，每個記錄出堆的順序就是一個有序序列。 交換后，子樹堆被破壞，繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點，堆被建成。交換后，子樹堆被破壞，繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點，堆被建成。此時可能會反復(fù)調(diào)整某些結(jié)點，直到 i=1為止，初建堆完成。 畫出對應(yīng)于序列 {10， 20， 7， 75， 41， 67， 3， 9， 30， 45} 的初始堆（堆頂元素取最小值）。 什么是堆 ? 寫出對應(yīng)于序列 (10， 20， 7， 75， 41， 67， 3， 9， 30， 45) 的初始堆 (堆頂元素取最小值 )。 83 40 63 13 84 35 96 57 39 79 61 15 40 83 13 63 35 84 57 96 39 79 15 61 13 40 63 83 35 57 84 96 15 39 61 79 13 35 40 57 63 83 84 96 15 39 61 79 13 15 35 39 40 57 61 63 79 83 84 96 58 兩個有序序列 A， B如何合并成一個有序序列？ 13 35 40 57 63 83 84 15 39 61 79 i j 合并至 A序列 合并形成新序列 C k 59 兩個有序序列如何合并成一個有序序列？ 設(shè) i， j是兩個有序序列中的記錄下標(biāo)， m， n是兩個序列長度， R[]是新的合并后的序列，下表從 k開始 1， im且 jn時，比較 a[i]和 b[j]的鍵值大小 取較小存入 R[k]中，同時對應(yīng) i， j加 1， k加 1 2，當(dāng) im或 jn時，將對應(yīng)序列中的剩余部分存入 R中 13 35 40 57 63 83 84 96 15 39 61 79 i j k 13 15 35 39 40 57 61 63 79 83 84 96 60 有序序列的合并算法 Void merge（ list a， list b， list c） { i=1； j=1。 while（ ian amp。 jbn） { if( a[i].key b[j].key ) { c[k]=a[i]。 k++。 j++。 } } //循環(huán)結(jié)束后是否所有記錄已存入 c中？ ………… } 61 有序序列的合并算法 Void merge（ list a， list b， list c） { ………… //循環(huán)結(jié)束后是否所有記錄已存入 c中？ while( ian ) { c[k]=a[i]。 k++。 j++。 } } 62 寫出鍵值 83， 40， 63， 13， 84， 35， 96， 57， 39， 79， 61， 15 應(yīng)用二路歸并排序算法從小到大排序后各趟的結(jié)果。 63 分配排序 箱（桶）排序 箱排序也稱桶排序 算法思想： 設(shè)置若干個箱子 ， 依次掃描待排序記錄 ， 把關(guān)鍵字等于 K的記錄全部裝入第 k個箱子 （ 分配過程 ） ， 然后依次將各個非空的箱子首尾連接起來 （ 收集過程 ） 。 多關(guān)鍵字的排序 鏈?zhǔn)交鶖?shù)排序 最低位優(yōu)先 LSD法 最高位優(yōu)先 MSD法 分配排序 基數(shù)排序 66 無序序列 對 K2排序 對 K1排序 對 K0排序 3,2,30 1,2,15 3,1,20 2,3,18 2,1,20 1,2,15 2,3,18 3,1,20 2,1,20 3,2,30 3,1,20 2,1,20 1,2,15 3,2,30 2,3,18 1,2,15 2,1,20 2,3,18 3,1,20 3,2,30 LSD的排序過程如下 : 67 在計算機(jī)上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： １．待排序記錄以指針相鏈，構(gòu)成一個鏈表； ２． “ 分配 ” 時，按當(dāng)前 “ 關(guān)鍵字位 ” 所取值，將記錄分配到不同的 “ 鏈隊列 ” 中，每個隊列中記錄的 “ 關(guān)鍵字位 ” 相同； ３． “ 收集 ” 時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表 。 68 對關(guān)鍵字序 (278,109,063,930,589,184,505,269,008,083) 進(jìn)行基數(shù)排序 930 083 063 184 505 008 278 269 589 109 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 69 930 083 063 184 505 008 278 269 589 109 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 收集 930 063 083 184 505 278 008 109 589 269 70 收集 930 063 083 184 505 278 008 109 589 269 505 930 184 083 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 063 278 008 109 589 269 收集 505 008 109 930 063 269 278 083 184 589 71 收集 505 008 109 930 063 269 178 083 184 589 008 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 505 083 589 109 178 930 063 269 184 收集 008 063 083 109 178 184 269 505 589 930 72 各種內(nèi)部排序算法的比較
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1