[理學(xué)]大學(xué)教程零起點(diǎn)數(shù)據(jù)結(jié)構(gòu)--排序-資料下載頁
2024-12-08 00:50本頁面
【正文】 果。 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。 k=1。 while（ ian amp。amp。 jbn） { if( a[i].key b[j].key ) { c[k]=a[i]。 i++。 k++。 } else { c[k]=a[j]。 j++。 k++。 } } //循環(huán)結(jié)束后是否所有記錄已存入 c中？ ………… } 61 有序序列的合并算法 Void merge（ list a， list b， list c） { ………… //循環(huán)結(jié)束后是否所有記錄已存入 c中？ while( ian ) { c[k]=a[i]。 i++。 k++。 } while( jbn ) { c[k]=b[j]。 j++。 k++。 } } 62 寫出鍵值 83， 40， 63， 13， 84， 35， 96， 57， 39， 79， 61， 15 應(yīng)用二路歸并排序算法從小到大排序后各趟的結(jié)果。 已知一組鍵值序列 （ 13， 12， 16， 17， 15， 14， 11）， 試采用二路歸并排序法對該組序列作升序排序 并給出每一趟的排序結(jié)果 已知一組鍵值序列 (26， 21， 32， 56， 78， 89， 90)， 試采用二路歸并排序法對該組序列 作升序排序， 并給出每一趟的排序結(jié)果。 63 分配排序 箱（桶）排序 箱排序也稱桶排序 算法思想： 設(shè)置若干個箱子 ， 依次掃描待排序記錄 ， 把關(guān)鍵字等于 K的記錄全部裝入第 k個箱子 （ 分配過程 ） ， 然后依次將各個非空的箱子首尾連接起來 （ 收集過程 ） 。 64 分配排序 箱（桶）排序 { 78, 17, 39, 26, 72, 94, 21, 12， 23, 68 } B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7] B[8] B[9] 26 39 94 78 21 72 17 桶 010 2030 4050 6070 8090 12 23 68 每個桶首尾相連，收集即可得到有序序列 65 基數(shù)排序是一種借助 “多關(guān)鍵字排序”的思想來實(shí)現(xiàn) “單關(guān)鍵字排序”的內(nèi)部排序算法。 多關(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ī)上實(shí)現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用鏈表作存儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為： １．待排序記錄以指針相鏈，構(gòu)成一個鏈表； ２． “ 分配 ” 時，按當(dāng)前 “ 關(guān)鍵字位 ” 所取值，將記錄分配到不同的 “ 鏈隊列 ” 中，每個隊列中記錄的 “ 關(guān)鍵字位 ” 相同； ３． “ 收集 ” 時，按當(dāng)前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表 。 ４．對每個關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。 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