算法22內(nèi)部排序基數(shù)排序.ppt

第9章內(nèi)部排序 基數(shù)排序 2 10 6基數(shù)排序 RadixSort 問題 1 什么是 多關(guān)鍵字 排序 實現(xiàn)方法 2 單邏輯關(guān)鍵字怎樣 按位值 排序 基本思想 借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序 即 用關(guān)鍵字不同的位值進(jìn)行排序 多關(guān)鍵字排序 例1 對一副撲克牌該如何排序 若規(guī)定花色和面值的順序關(guān)系為 花色 面值 2 3 4 5 6 7 8 9 10 J Q K A則可以先按花色排序 花色相同者再按面值排序也可以先按面值排序 面值相同者再按花色排序 10 6基數(shù)排序 例2 職工分房該如何排序 規(guī)定 先以總分排序 職稱分 工齡分 總分相同者 再按配偶總分排序 其次按配偶職稱 工齡 人口 等等排序 例3 學(xué)生評獎學(xué)金如何排序 多關(guān)鍵字排序的實現(xiàn)方法通常有兩種 最高位優(yōu)先法MSD MostSignificantDigitfirst 最低位優(yōu)先法LSD LeastSignificantDigitfirst 10 6基數(shù)排序 對一副撲克牌的排序若規(guī)定花色為第一關(guān)鍵字 高位 面值為第二關(guān)鍵字 低位 則使用MSD和LSD方法都可以達(dá)到排序目的 MSD方法的思路 先設(shè)立4個花色 箱 將全部牌按花色分別歸入4個箱內(nèi) 每個箱中有13張牌 然后對每個箱中的牌按面值進(jìn)行插入排序 或其它穩(wěn)定算法 LSD方法的思路 先按面值分成13堆 每堆4張牌 然后對每堆中的牌按花色進(jìn)行排序 用插入排序等穩(wěn)定的算法 用哪種方法更快些 單邏輯關(guān)鍵字 按位值 排序 設(shè)n個記錄的序列為 V0 V1 Vn 1 可以把每個記錄Vi的單關(guān)鍵碼Ki看成是一個d元組 Ki1 Ki2 Kid 則其中的每一個分量Kij 1 j d 也可看成是一個關(guān)鍵字 注1 Ki1 最高位 Kid 最低位 Ki共有d位 可看成d元組 注2 每個分量Kij 1 j d 有radix種取值 則稱radix為基數(shù) 思路 討論 是借用MSD方式來排序呢 還是借用LSD方式 例 初始關(guān)鍵字序列T 32 19 27 32 13 30 請分別用MSD和LSD進(jìn)行排序 并討論其優(yōu)缺點 法1 MSD 原始序列 32 19 27 32 13 30先按高位Ki1排序 19 13 27 32 32 30 再按低位Ki2排序 13 19 27 30 32 32 法2 LSD 原始序列 32 19 27 32 13 30先按低位Ki2排序 30 32 32 13 27 19再按高位Ki1排序 13 19 27 30 32 32 MSD存在遞歸效率受影響 LSD只需進(jìn)行線性掃描 用鏈隊列來實現(xiàn)基數(shù)排序 鏈?zhǔn)交鶖?shù)排序 實現(xiàn)思路 針對d元組中的每一位分量 把原始鏈表中的所有記錄 按Kij的取值 讓j d d 1 1 先 分配 到radix個鏈隊列中去 然后再按各鏈隊列的順序 依次把記錄從鏈隊列中 收集 起來 分別用這種 分配 收集 的運算逐趟進(jìn)行排序 在最后一趟 分配 收集 完成后 所有記錄就按其關(guān)鍵碼的值從小到大排好序了 實現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序 T 278 109 063 930 589 184 505 269 008 083 例 第一趟分配 e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 184 083 589 505 063 269 278 930 008 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 是隊首指針 e 為隊尾指針 第一趟收集 r 0 109 2020 4 21 e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 063 278 269 083 184 505 109 930 589 008 f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 第二趟分配 按次低位i 2 第一趟收集的結(jié)果 第二趟收集 r 0 r 0 2020 4 21 e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 083 008 930 589 184 109 269 505 063 278 f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 第三趟分配 按最高位i 1 r 0 排序結(jié)束 r 0 第二趟收集的結(jié)果 第三趟收集 基數(shù)排序算法分析 假設(shè)有n個記錄 每個記錄的關(guān)鍵字有d位 每個關(guān)鍵字的取值有radix個 則需要radix個隊列 進(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ù)排序較好 特點 不用比較和移動 改用分配和收集 時間效率高 2020 4 21 鏈表基數(shù)排序的算法 voidRadixSort 選下一關(guān)鍵字 直到本趟分配完 2020 4 21 j 0 開始從0號隊列 總共radix個隊 開始收集while f j 0 j 若是空隊列則跳過r 0 next p f j 建立本趟收集鏈表的頭指針intlast e j 建立本趟收集鏈表的尾指針for k j 1 k radix k 逐個隊列鏈接 收集 if f k 若隊列非空r last next f k last e k 隊尾指針鏈接 r last next 0 本趟收集鏈表之尾部應(yīng)為0 RadixSort在此算法中 數(shù)組r n 被反復(fù)使用 用來存放原始序列和每趟收集的結(jié)果 記錄從未移動 僅指針改變 2020 4 21 特點 不用比較和移動 改用分配和收集 時間效率高 假設(shè)有n個記錄 每個記錄的關(guān)鍵字有d位 每個關(guān)鍵字的取值有radix個 則需要radix個隊列 進(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ù)排序較好 1 平方階 O n2 排序一般稱為簡單排序 例如直接插入 直接選擇和冒泡排序 2 線性對數(shù)階 O nlgn 排序如快速 堆和歸并排序 3 O n1 階排序 是介于0和1之間的常數(shù) 即0 1 如希爾排序 按平均時間將排序類 9 7內(nèi)部排序方法的比較 17 1 各種方法的時 空優(yōu)劣 判定樹模型 如下圖所示 說明對a b c進(jìn)行分類的一棵判定樹 當(dāng)判斷條件成立時 轉(zhuǎn)向左 否則轉(zhuǎn)向右 2 比較法分類的下界 O nlogn a b a b c a c b c a c b c a c b c a b c b a b a c b c a no yes yes yes yes yes no no no no 注意 樹高代表比較的代價 因此只要知道了樹高和結(jié)點數(shù)n的關(guān)系 就可以求出用比較法進(jìn)行排序時的時間代價 另外 n個結(jié)點的分類序列 其葉子結(jié)點共有n 片 9 7內(nèi)部排序方法的比較 18 n n2 0 n2 1 n n2 0 n2 1 nlog2n n2 0 n2 log2n n n2 0 n 1 nlog2n nlog2n 1 nlog2n nlog2n n dn n 9 7內(nèi)部排序方法的比較 因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求 所以選擇合適的排序方法應(yīng)綜合考慮下列因素 待排序的記錄數(shù)目n 記錄的大小 規(guī)模 關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài) 對穩(wěn)定性的要求 語言工具的條件 存儲結(jié)構(gòu) 時間和輔助空間復(fù)雜度等 影響排序效果的因素 9 7內(nèi)部排序方法的比較 1 若n較小 如n 50 可采用直接插入或直接選擇排序 當(dāng)記錄規(guī)模較小時 直接插入排序較好 否則因為直接選擇移動的記錄數(shù)少于直接插人 應(yīng)選直接選擇排序為宜 2 若文件初始狀態(tài)基本有序 指正序 則應(yīng)選用直接插人 冒泡或隨機的快速排序為宜 3 若n較大 則應(yīng)采用時間復(fù)雜度為O nlgn 的排序方法 快速排序 堆排序或歸并排序 快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法 當(dāng)待排序的關(guān)鍵字是隨機分布時 快速排序的平均時間最短 堆排序所需的輔助空間少于快速排序 并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況 這兩種排序都是不穩(wěn)定的 不同條件下排序方法的選擇 2020 4 21 外部排序與文件 2020 4 21 1 外部排序 待排序的記錄數(shù)量巨大 無法一次調(diào)入內(nèi)存 只能駐留在外存上 磁帶 磁盤 CD ROM 上 不能使用內(nèi)部排序的方法進(jìn)行排序 否則將引起頻繁訪問外存 外部排序主要的時間開銷用在信息的內(nèi) 外存交換上 所以減少I O時間成為要解決的主要問題 2020 4 21 1 外部排序的方法 外部排序的基本過程由相對獨立的兩個步驟組成 按可用內(nèi)存大小 利用內(nèi)部排序方法 構(gòu)造若干個記錄的有序子序列寫入外存 通常稱這些記錄的有序子序列為 歸并段 通過 歸并 逐步擴大 記錄的 有序子序列的長度 直至外存中整個記錄序列按關(guān)鍵字有序為止 2020 4 21 例如 假設(shè)有一個含10 000個記錄的磁盤文件 而當(dāng)前所用的計算機一次只能對1 000個記錄進(jìn)行內(nèi)部排序 則首先利用內(nèi)部排序的方法得到10個初始?xì)w并段 然后進(jìn)行逐趟歸并 假設(shè)進(jìn)行2 路歸并 即兩兩歸并 則第一趟由10個歸并段得到5個歸并段 第二趟由5個歸并段得到3個歸并段 第三趟由3個歸并段得到2個歸并段 最后一趟歸并得到整個記錄的有序序列 2020 4 21 假設(shè) 數(shù)據(jù)塊 的大小為200 即每一次訪問外存可以讀 寫200個記錄 則對于10 000個記錄 處理一遍需訪問外存100次 讀和寫各50次 1 求得10個初始?xì)w并段需訪問外存100次 2 每進(jìn)行一趟歸并需訪問外存100次 3 總計訪問外存100 4 100 500次若對上述例子采用5 路歸并 則只需進(jìn)行2趟歸并 總的訪問外存的次數(shù)為100 2 100 300次 2020 4 21 一般情況下 假設(shè)待排記錄序列含m個初始?xì)w并段 外排時采用k 路歸并 則歸并趟數(shù)s logkm 顯然 隨著k的增大或m的減小 歸并的趟數(shù)將減少 因此對外排而言 通常采用多路歸并 k的大小可選 但需綜合考慮各種因素 2020 4 21 2 多路平衡歸并的實現(xiàn) 1 9 5 7 29 5 9 5 7 6 5 4 3 2 516495278 712258491 2938576671 922474859 5 輸入緩沖區(qū) 4路平衡歸并 勝者樹及其使用 2020 4 21 勝者樹及其使用 9 7 7 29 16 9 7 516495278 712258491 2938576671 922474859 7 6 5 4 3 2 1 輸入緩沖區(qū) 輸出緩沖區(qū) 7 7 9 16 7 29 9 7 6 5 4 3 2 1 57 2020 4 21 勝者樹及其使用 9 12 12 29 16 9 9 516495278 712258491 2938576671 922474859 7 6 5 4 3 2 1 輸入緩沖區(qū) 輸出緩沖區(qū) 9 12 9 16 12 29 9 7 6 5 4 3 2 1 579 2020 4 21 改進(jìn) 采用勝者樹 從K個元素中選取最小元素之后 從根結(jié)點到它的相應(yīng)的葉子結(jié)點路徑上的結(jié)點都需要進(jìn)行修改 為了加快程序運行的速度產(chǎn)生了敗者樹 2020 4 21 敗者樹及其使用 2 1 7 29 5 9 3 b 0 ls 1 輸入緩沖區(qū) 輸出緩沖區(qū) 9 7 29 5 7 29 9 7 6 5 4 3 2 1 注意 挑出冠軍需要進(jìn)行k 1次比較 此處需要比較3次 0 ls 0 0 5 ls 2 ls 3 b 1 b 2 b 3 516495278 712258491 2938576671 922474859 5 2020 4 21 2 0 7 29 16 9 3 516495278 712258491 2938576671 922474859 b 0 ls 1 輸入緩沖區(qū) 輸出緩沖區(qū) 57 注意 挑出冠軍需要進(jìn)行k 1次比較 此處需要比較3次 1 ls 2 ls 3 b 1 b 2 b 3 2020 4 21 多路平衡歸并的實現(xiàn) 敗者樹 2 0 12 29 16 9 1 516495278 712258491 2938576671 922474859 b 0 ls 1 輸入緩沖區(qū) 輸出緩沖區(qū) 579 注意 挑出冠軍需要進(jìn)行k 1次比較 此處需要比較3次 3 ls 0 ls 2 ls 3 b 1 b 2 b 3 2020 4 21 3 文件 1 文件 大量性質(zhì)相同的記錄的集合 和 查找表 的差別在于 文件 指的是存儲在外存儲器中的記錄的集合 記錄是文件中可以存取的數(shù)據(jù)的基本單位 2020 4 21 2 文件可按其中記錄的類型不同而分成兩類 操作系統(tǒng)的文件 文件中的記錄僅是一個字符組 由于操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列 為了用戶存取和加工的方便 將文件中的信息劃分為若干組 其中每一組信息稱作一個記錄 數(shù)據(jù)庫文件 文件中的記錄帶有結(jié)構(gòu) 是數(shù)據(jù)項的集合 記錄是文件中可以存取的數(shù)據(jù)基本單位 數(shù)據(jù)項是文件中可以使用的數(shù)據(jù)最小單位 還可分為定長記錄文件和不