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

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