chap8-算法與數(shù)據(jù)結(jié)構(gòu)—c語(yǔ)言描述(第2版)張乃孝編課件-資料下載頁(yè)
2025-08-04 23:28本頁(yè)面
【正文】 低位關(guān)鍵字 kd起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字排序， …… 依次重復(fù)，直至對(duì)最高位關(guān)鍵字 k1排序后，便成為一個(gè)有序序列 ? MSD與 LSD不同特點(diǎn) ?按 MSD排序，必須將序列逐層分割成若干子序列，然后對(duì)各子序列分別排序 ?按 LSD排序，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過(guò)關(guān)鍵字比較，而通過(guò)若干次分配與收集實(shí)現(xiàn)排序 ? 鏈?zhǔn)交鶖?shù)排序 ?基數(shù)排序：借助 “ 分配 ” 和 “ 收集 ” 對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種方法 ?鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲(chǔ)結(jié)構(gòu)的基數(shù)排序 ?鏈?zhǔn)交鶖?shù)排序步驟 ?設(shè)置 10個(gè)隊(duì)列， f[i]和 e[i]分別為第 i個(gè)隊(duì)列的頭指針和尾指針 ?第一趟分配對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至 10個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同 ?第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將 10個(gè)隊(duì)列鏈成一個(gè)鏈表 ?重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對(duì)十位、百位進(jìn)行，最后得到一個(gè)有序序列 例 初始狀態(tài)： 278 109 063 930 589 184 505 269 008 083 109 589 269 278 063 930 083 184 505 008 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 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 一趟收集： 505 008 109 930 063 269 278 083 184 589 二趟收集： 083 184 589 063 505 269 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 008 109 278 930 063 083 184 505 278 008 109 589 269 一趟收集： 008 063 083 109 184 269 278 505 589 930 三趟收集： 109 008 184 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 063 083 269 278 505 589 505 008 109 930 063 269 278 083 184 589 二趟收集： ?算法描述 ?算法評(píng)價(jià) ?時(shí)間復(fù)雜度： ?分配： T(n)=O(n) ?收集： T(n)=O(rd) T(n)=O(d(n+r)) 其中： n—— 記錄數(shù) d—— 關(guān)鍵字位數(shù) r—— 關(guān)鍵字每位的取值范圍 ?空間復(fù)雜度： S(n)= O( n+r) r個(gè)隊(duì)列指針 +n個(gè)指針域空間 ? 歸并排序 ?歸并 —— 將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表，叫歸并 ? 2路歸并排序 ?排序過(guò)程 ?設(shè)初始序列含有 n個(gè)記錄，則可看成 n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為 1 ?兩兩合并，得到 ?n/2?個(gè)長(zhǎng)度為 2或 1的有序子序列 ?再兩兩合并， …… 如此重復(fù)，直至得到一個(gè)長(zhǎng)度為 n的有序序列為止 例 初始關(guān)鍵字： [49] [38] [65] [97] [76] [13] [27] 一趟歸并后： [38 49] [65 97] [13 76] [27] 二趟歸并后： [38 49 65 97] [13 27 76] 三趟歸并后： [13 27 38 49 65 76 97] ?算法描述 ?算法評(píng)價(jià) ?時(shí)間復(fù)雜度： T(n)=O(nlogn) ?空間復(fù)雜度： S(n)=O(n)
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1