數(shù)據(jù)結(jié)構(gòu)課件第十章-資料下載頁
2025-05-13 00:10本頁面
【正文】 *, 33 無需分組，易編程實(shí)現(xiàn)！ 52 例 ： T=（ 02， 77， 70， 54， 64， 21， 55， 11），用 LSD排序。 分析： ①各關(guān)鍵字可視為 2元組；②每位的取值范圍是： 09；即 基數(shù)radix ＝ 10 。 因此，特設(shè)置 10個隊(duì)列，并編號為 09。 11 55 21 64 54 70 77 02 原始序列 1 2 3 4 5 6 7 8 先對低位掃描 出隊(duì) 0 1 2 3 4 5 6 7 8 9 10個隊(duì)列 計(jì)算機(jī)怎樣實(shí)現(xiàn) LSD算法？ 分配過程 收集過程 下一步 77 55 64 54 02 11 21 70 1 2 3 4 5 6 7 8 出隊(duì)后序列 77 55 54， 64 21， 11 70 02 又稱散列過程！ 53 0 1 2 3 4 5 6 7 8 9 再次入隊(duì) 再次出隊(duì) 再對高位掃描 小結(jié)： 排序時經(jīng)過了反復(fù)的“分配”和“收集”過程。當(dāng)對關(guān)鍵字所有的位進(jìn)行掃描排序后，整個序列便從無序變?yōu)橛行蛄恕? 77 55 64 54 02 11 21 70 1 2 3 4 5 6 7 8 出隊(duì)后序列 70， 77 64 54， 55 21 11 02 再次分配 再次收集 77 70 64 55 54 21 11 02 再次出隊(duì)后序列 這種 LSD排序方法稱為： 基數(shù)排序 54 請實(shí)現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序： T=（ 614， 738， 921， 485， 637， 101， 215， 530， 790， 306） 例 :614 921 485 637 738 101 215 530 790 306 第一趟分配 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 614 738 921 485 637 101 215 530 790 306 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 原始序列鏈表： r[0]→ （從最低位 i = 3開始排序， f[ ] 是隊(duì)首指針， e[ ] 為隊(duì)尾指針） 第一趟收集 （讓隊(duì)尾指針 e[i] 鏈接到下一非空隊(duì)首指針 f[i+1 ] 即可） 530 790 921 101 614 485 215 306 637 738 r[0]→ 55 第一趟收集的結(jié)果： e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 614 738 921 485 637 101 215 530 790 306 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 第二趟分配 （按次低位 i = 2 ） 530 790 921 101 614 485 215 306 637 738 第二趟收集 （讓隊(duì)尾指針 e[i] 鏈接到下一非空隊(duì)首指針 f[i+1 ] ） 530 790 921 101 614 485 215 306 637 738 r[0]→ r[0]→ 56 第二趟收集的結(jié)果： 530 790 921 101 614 485 215 306 637 738 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 614 738 921 485 637 101 215 530 790 306 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 第三趟分配 （按最高位 i = 1 ） 第三趟收集 （讓隊(duì)尾指針 e[i] 鏈接到下一非空隊(duì)首指針 f[i+1 ] ） 530 790 921 101 614 485 215 306 637 738 r[0]→ r[0]→ 排序結(jié)束！ 57 基數(shù)排序算法分析 ? 假設(shè)有 n 個記錄 , 每個記錄的關(guān)鍵字有 d 位 ， 每個關(guān)鍵字的取值有 radix個 , 則需要 radix個隊(duì)列 , 進(jìn)行 d 趟 “ 分配 ”與 “ 收集 ” 。 因此時間復(fù)雜度： O ( d ( n+radix ) )。 ? 基數(shù)排序需要增加 n+2radix個附加鏈接指針 ， 空間效率低 空間復(fù)雜度： O（ radix） . ? 穩(wěn)定性：穩(wěn)定 。 (一直前后有序 )。 用途： 若基數(shù) radix相同 ， 對于記錄個數(shù)較多而關(guān)鍵碼位數(shù)較少的情況 ， 使用鏈?zhǔn)交鶖?shù)排序較好 。 特點(diǎn)： 不用比較和移動，改用分配和收集，時間效率高！ 58 各種內(nèi)部排序方法的比較 (教材 P289） 排序方法 最好情況 平均時間 最壞情況 輔助存儲 穩(wěn)定性 簡單排序 O(n) O(n2) O(n2) O(1） 穩(wěn)定 快速排序 O(nlgn ) O(nlgn) O(n2) O(lgn) 不穩(wěn)定 堆排序 O(nlgn ) O(nlgn ) O(nlgn) O(1） 不穩(wěn)定 歸并排序 O(nlgn ) O(nlgn ) O(nlgn) O(n） 穩(wěn)定 基數(shù)排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(rd) 穩(wěn)定 簡單選擇 O(n2) O(n2) O(n2) O(1） 不穩(wěn)定 直接插入 O(n) O(n2) O(n2) O(1） 穩(wěn)定 折半插入 O(nlgn ) O(nlgn ) O(nlgn ) O(1） 穩(wěn)定 冒泡 O(n) O(n2) O(n2) O(1） 穩(wěn)定 59 討論： 若初始記錄基本無序，則選用哪些排序方法比較適合？若初始記錄基本無序，則最好選用哪些排序方法？ 答： 對基本有序的情況，可選用堆排序、冒泡排序、歸并排序等方法； 在基本無序的情況下，最好選用快速排序、希爾排序。 想一想： 能選用折半排序么？
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1