數(shù)據(jù)庫(kù)——排序.ppt

1、2020年8月9日,1,10.1 基本概念 10.2 插入排序 10.3 交換排序 10.4 選擇排序 10.5 歸并排序 10.6 基數(shù)排序 10.7 內(nèi)部排序的比較 10.8 外部排序 10.9 小 結(jié),第十章 排序,2020年8月9日,2,本章主要內(nèi)容,本章主要內(nèi)容，本章詳細(xì)介紹了排序的基本概念和常見(jiàn)的排序方法，包括常用的內(nèi)部排序方法，外部排序方法等內(nèi)容。通過(guò)本章的學(xué)習(xí)，應(yīng)掌握如下內(nèi)容： l 插入排序 l 交換排序 l 選擇排序 l 歸并排序 l 基數(shù)排序 l 外部排序 l 各種排序的比較,2020年8月9日,3,關(guān)鍵字：在排序過(guò)程中，所依據(jù)的數(shù)據(jù)項(xiàng)稱為“關(guān)鍵字”，也稱為排序記錄的關(guān)鍵碼

2、。,排序：對(duì)任意排列的數(shù)據(jù)元素序列，通過(guò)某種算法使其滿足按關(guān)鍵字遞增（或遞減）關(guān)系的過(guò)程。,排序的穩(wěn)定性和不穩(wěn)定性：對(duì)需要排序的數(shù)據(jù)元素序列，將其按關(guān)鍵字進(jìn)行排序，若相同關(guān)鍵字元素之間的位置關(guān)系，排序前與排序后的相對(duì)位置不發(fā)生變化，稱此排序方法滿足穩(wěn)定性；否則稱這種排序方法滿足不穩(wěn)定性。,10.1 基本概念,2020年8月9日,4,排序算法中結(jié)點(diǎn)的數(shù)據(jù)類型描述方法： typedef int KeyType; typedef struct KeyType key; ElemType; typedef struct ElemType dataMAXSIZE+1；/*結(jié)點(diǎn)數(shù)組 */ int leng

3、th；/* 表長(zhǎng)度 */ SL；,內(nèi)部排序和外部排序：內(nèi)排序是指待排序列完全存放在內(nèi)存中所進(jìn)行的排序過(guò)程，適合記錄較少的序列。如果待排序列記錄數(shù)量非常多，排序過(guò)程不能一次在內(nèi)存中完成，必需對(duì)外存儲(chǔ)器進(jìn)行訪問(wèn)，這樣的排序稱為外部排序。,2020年8月9日,5,10.2.1 直接插入排序 直接插入排序：是指將一個(gè)記錄按關(guān)鍵字大小的順序插入到有序序列中的過(guò)程。,排序過(guò)程如下： 設(shè)有一組關(guān)鍵字 key1,key2,keyn ; 認(rèn)為key1就是一個(gè)有序序列; 令關(guān)鍵字為key2的數(shù)據(jù)元素插入到上述表長(zhǎng)為1的有序序列中,使之成為一個(gè)表長(zhǎng)為2的有序序列; 最后讓關(guān)鍵字為keyn的數(shù)據(jù)元素插入到上述表長(zhǎng)為n

4、-1的有序序列中,使之成為一個(gè)表長(zhǎng)為n的有序序列。,2020年8月9日,6,【算法10.1】直接插入排序 void InsertSort (SL *p) for(i=2；ilength；i+) if(p-datai.keydatai-1.key) p-data0=p-datai；/*設(shè)置監(jiān)視哨*/ for(j=i-1；p-data0.keydataj.key；j-) p-dataj+1 =p-dataj； /*記錄后移*/ p-dataj+1=p-data0；/*插入到正確位置*/ /* if */ ,a0 a1 a2 a3 a4 a5 i=1： 6 13 9 26 11 i=2： 6 13

5、9 26 11,2020年8月9日,7,【例10-1】 有一個(gè)待排序列6，13，9，26，11，將其按照直接插入方法實(shí)現(xiàn)排序。如圖所示：,初始關(guān)鍵字：a1 a2 a3 a4 a5 i=1： 6 13 9 26 11 i=2： 6 13 9 26 11 i=3： 6 9 13 26 11 i=4： 6 9 13 26 11 i=5： 6 9 11 13 26,2020年8月9日,8,算法分析： 空間復(fù)雜度：該算法只使用了一個(gè)輔助存儲(chǔ)單元p-data0，所以是O(1)； 時(shí)間復(fù)雜度：向有序表中逐個(gè)插入記錄的操作，進(jìn)行了n-1趟，每一趟比較和移動(dòng)記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列狀態(tài)。 最好

6、情況下，即初始序列已經(jīng)有序的情況下，比較n-1次，移動(dòng)2(n-1)次。 最壞情況下，即初始序列在呈逆序的情況下，比較n(n-1)/2次，移動(dòng)n(n-1)/2+2n次。 因此，時(shí)間復(fù)雜度為O(n2)，排序方法穩(wěn)定，適合于記錄個(gè)數(shù)比較少的情況，若原始數(shù)據(jù)序列在基本有序的情況下，算法效率比較高。,2020年8月9日,9,直接插入排序算法中，數(shù)據(jù)的移動(dòng)是一步步進(jìn)行的，當(dāng)數(shù)據(jù)量很大時(shí)，比較和移動(dòng)的次數(shù)都非常大。希爾排序是對(duì)該算法的改進(jìn)。,希爾排序基本思想是先將整個(gè)待排序列分割成若干個(gè)子序列，然后對(duì)各子序列分別進(jìn)行直接插入排序，當(dāng)達(dá)到有序狀態(tài)時(shí)，再進(jìn)行一次直接插入排序。,排序過(guò)程如下：每趟排序，根據(jù)對(duì)應(yīng)的

7、步長(zhǎng)，將待排序列分割成若干長(zhǎng)度為m的子序列，分別對(duì)各子序列進(jìn)行直接插入排序;縮小步長(zhǎng)再繼續(xù)劃分子序列排序，直到步長(zhǎng)為1為止。,10.2.2 希爾排序,2020年8月9日,10,【例10-2】待排序列為 34，81，72，42，10，28，52，77，33，13，109，4，42，89。 步長(zhǎng)因子di分別取5、3、1，則排序過(guò)程如下：,d0=5 34 81 72 42 10 28 52 77 33 13 109 4 42 89 ,子序列分別為34，28，109，81，52，4，72，77，42，42，33，89，10，13。,2020年8月9日,11,第一趟排序結(jié)果： 28 4 42 33 10

8、 34 52 72 42 13 109 81 77 89 ,第二趟排序結(jié)果： 13 4 34 28 13 42 33 72 42 52 89 81 77 109 此時(shí)，序列基本“有序”，對(duì)其進(jìn)行直接插入排序，得到最終結(jié)果： 4 10 13 28 33 34 42 42 52 72 77 81 89 109,2020年8月9日,12,【算法10.2】希爾排序 void ShellInsert(SL *p，int dk) /*一趟增量為dk的插入排序，dk為步長(zhǎng)因子*/ for(i=dk+1；ilength；i+) if (p-datai.key datai-dk.key) p-data0=p-d

9、atai； for(j=i-dk；j0 for(i=1;ii;j+) if(p-dataj.keydataj-1.key) p-data0=p-dataj; p-dataj= p-dataj-1; p-dataj-1=p-data0; flag=1; if(flag=0) printf(“排序結(jié)束”); break; /*bubble*/,2020年8月9日,16,算法分析: 算法中flag為標(biāo)志變量，當(dāng)某一趟排序中進(jìn)行過(guò)記錄交換時(shí)flag的值為1，否則為0。所以外循環(huán)結(jié)束條件是：flag=0，已有序，或i=n。 空間復(fù)雜度：僅用一個(gè)輔助單元,復(fù)雜度為O(1)。 時(shí)間復(fù)雜度：冒泡排序中元素之間

10、比較的次數(shù)為n(n-1)/2。若所給的序列是滿足排序要求，則元素移動(dòng)的次數(shù)為0(最好情況)；若所給的序列是正好成逆序狀態(tài)，元素移動(dòng)的次數(shù)為3n(n-1)/2(最壞情況)。其平均時(shí)間復(fù)雜度為O(n2)。,2020年8月9日,17,當(dāng)冒泡排序在數(shù)據(jù)元素的關(guān)鍵字呈逆序時(shí)進(jìn)行排序，需要進(jìn)行多次比較和移動(dòng)操作，數(shù)據(jù)元素移動(dòng)是一步一步進(jìn)行的，且有很多是重復(fù)的?？焖倥判蚴菍?duì)冒泡排序算法的改進(jìn)。,基本思想：快速排序又稱為分區(qū)交換法，是通過(guò)對(duì)某關(guān)鍵字(支點(diǎn))的比較，將各待排序列分成前后兩部分，后半部分所有記錄的關(guān)鍵字值大于等于支點(diǎn)的關(guān)鍵字值，前半部分所有記錄的關(guān)鍵字小于等于支點(diǎn)的關(guān)鍵字值。將待排序列按關(guān)鍵字以支

11、點(diǎn)分成兩部分的過(guò)程，稱為一次劃分。對(duì)各部分不斷的劃分，直到整個(gè)序列按關(guān)鍵字有序?yàn)橹埂?10.3.2 快速排序,2020年8月9日,18,【例10-3】一趟快速排序過(guò)程示例 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43 28 39 76 98 69 4 51 58 28 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43 43 28 39 76 98 69 4 51 58 28 low high 從high向前搜索小于r0.key的記錄，將其賦值給low指向的位置,r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43 28 2

12、8 39 76 98 69 4 51 58 28 low high 從low向后搜索大于r0.key的記錄，將其賦值給high指向的位置,2020年8月9日,19,43 28 28 39 76 98 69 4 51 58 76 low high 從high向前搜索小于r0.key的記錄，將其賦值給low指向的位置,43 28 28 39 4 98 69 4 51 58 76 low high 從low向后搜索大于r0.key的記錄，將其賦值給high指向的位置,2020年8月9日,20,43 28 28 39 4 98 69 98 51 58 76 low high,43 28 28 39 4

13、 98 69 98 51 58 76 low high low=high，劃分結(jié)束，將r0.key的值賦值給low(high)指向的位置,28 28 39 4 43 69 98 51 58 76,2020年8月9日,21,快速排序的遞歸過(guò)程可用生成一棵二叉樹(shù)的過(guò)程形象地表示，每棵子樹(shù)的根結(jié)點(diǎn)是各次劃分時(shí)的支點(diǎn)，,r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 43 28 39 76 98 69 4 51 58 28,28 28 39 4,69 98 51 58 76,初始序列,43,69 98 51 58 76,一次劃分后,2020年8月9日,22,算法分析：時(shí)間復(fù)雜度：在

14、n個(gè)記錄的待排序列中，一次劃分需要約n次關(guān)鍵碼比較。若每次劃分的前后兩部分?jǐn)?shù)據(jù)元素個(gè)數(shù)基本相等，則需要經(jīng)過(guò)log2n次劃分，所以算法時(shí)間復(fù)雜度為nlog2n，最壞情況下，時(shí)間復(fù)雜度為O(n2)?？臻g復(fù)雜度：快速排序是遞歸的，每層遞歸調(diào)用的指針和參數(shù)均要用棧來(lái)存放，遞歸調(diào)用次數(shù)與二叉樹(shù)的深度一致。存儲(chǔ)開(kāi)銷在理想情況下為O(log2n)，即樹(shù)的高度；在最壞情況下，二叉樹(shù)是一個(gè)單支，這時(shí)算法的空間復(fù)雜度為為O(n)。,2020年8月9日,23,是以降低數(shù)據(jù)元素的移動(dòng)次數(shù)為排序思路。,10.4.1 直接選擇排序 排序過(guò)程： 第一次，選取整個(gè)序列中關(guān)鍵字最小的記錄與第一個(gè)元素交換； 第二次，從剩余的n-

15、1個(gè)記錄中選出關(guān)鍵字最小的記錄與第二個(gè)記錄交換； 第i次，則從剩余的n-i+1個(gè)記錄選出關(guān)鍵字最小的記錄與第i個(gè)記錄交換； 直到整個(gè)序列按關(guān)鍵碼有序。,10.4 選擇排序,2020年8月9日,24,【例10-4】 待排序列 35 28 45 55 19 68 初始狀態(tài) 35 28 45 55 19 68 i=1 19 28 45 55 35 68 元素19和35交換 i=2 19 28 45 55 35 68 元素35和45交換 i=3 19 28 35 55 45 68 元素45和55交換 i=4 18 24 35 45 55 68 i=5 18 24 35 45 55 68 i=6 18

16、24 35 45 55 68,2020年8月9日,25,【算法10.5】直接選擇排序 void SelectSort(SL *p) for(i=1；ilength；i+) k=i; for(j=i+1，k=i；jlength；j+) if(p-datak.keyp-dataj.key) k=j；/* t中存放關(guān)鍵碼最小記錄的下標(biāo) */ if(i!=k) /* 關(guān)鍵碼最小的記錄與第i個(gè)記錄交換 */ p-data0=p-datai； p-datai=p-datak； p-datak=p-data0; ,2020年8月9日,26,算法分析： 空間復(fù)雜度：一個(gè)附加單元的存儲(chǔ)空間，所以是O(1)。 時(shí)

17、間復(fù)雜度：該算法使用了循環(huán)的嵌套形式，復(fù)雜度為n(n+1)/2，所以為O(n2)。 算法是穩(wěn)定的。 直接選擇排序中比較的次數(shù)比較多。,10.4.2 堆排序(Heap Sort) 堆排序就是直接選擇排序算法的改進(jìn)算法。 堆的定義：設(shè)有n個(gè)元素的序列R1,R2,Rn ,其關(guān)鍵字為k1，k2，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆.,2020年8月9日,27,下面討論小根堆,2020年8月9日,28,堆排序大體分兩步處理： 第一步建立堆結(jié)構(gòu)。先取i=n/2（i是第n個(gè)結(jié)點(diǎn)的雙親的編號(hào)），將以i結(jié)點(diǎn)為根的子樹(shù)調(diào)整為堆；然后令i=i-1；再將以i結(jié)點(diǎn)為根的子樹(shù)調(diào)整成為堆。直到i=1為止，初建堆完成。

18、,第二步堆排序。首先輸出堆頂元素，讓堆中最后一個(gè)元素上移到堆頂位置，然后恢復(fù)堆，重復(fù)執(zhí)行輸出堆頂元素、堆尾元素移到堆頂和恢復(fù)堆的操作，直到全部元素輸出完為止。,因此，實(shí)現(xiàn)堆排序需解決兩個(gè)問(wèn)題： 1. 如何將n個(gè)元素的序列按關(guān)鍵碼建成堆； 2. 輸出堆頂元素后，調(diào)整剩余元素成為一個(gè)新堆。,2020年8月9日,29,【例10-6】設(shè)有8 個(gè)記錄的關(guān)鍵字是53，36，30，91，47，12，24，85，試用堆排序的方法，將這組記錄由小到大排序。,第一步：建立堆結(jié)構(gòu)，其過(guò)程如圖所示。,2020年8月9日,30,2020年8月9日,31,第二步：堆排序。這是反復(fù)輸出堆頂元素，將堆尾元素上移至堆頂，再調(diào)整

19、恢復(fù)堆的過(guò)程，恢復(fù)堆的過(guò)程與初建堆中i=1時(shí)所進(jìn)行的調(diào)整操作相同。,2020年8月9日,32,2020年8月9日,33,2020年8月9日,34,歸并的含義是將兩個(gè)或兩個(gè)以上的有序序列歸并成一個(gè)新的有序表。歸并排序可分為多路歸并排序和兩路歸并排序。它既可以用于內(nèi)部排序，也可以用于外部排序。,一趟兩路歸并算法的思想（以升序?yàn)槔合扔脙蓚€(gè)指針?lè)謩e指向兩個(gè)序列的第一個(gè)數(shù)據(jù)元素，進(jìn)行比較，取出較小者，然后將其所在序列的指針后移，重復(fù)以上過(guò)程，直到指針達(dá)到序列的末尾，這時(shí)將另一個(gè)序列的剩余元素依次順序放到有序序列的后面即可。,10.5 歸并排序,2020年8月9日,35,將兩個(gè)有序序列L-datat.

20、m和L-datam+1.n歸并為有序序列L1-t.n的過(guò)程： i=t；j=m；k=t； 若im 或 jn，執(zhí)行； 比較L-datai和L-dataj關(guān)鍵字,將較小的存入L1中: 如果L-datai.keydataj.key； L1-datak=L-datai；i+； k+；執(zhí)行； 否則，L1-datak=L-dataj;j+;k+;執(zhí)行； 將尚未處理完的子表中元素存入L1； 如果idataim存入L1-datakn； 如果jjn存入L1-datakn； 合并結(jié)束。,2020年8月9日,36,【算法9.7】 一趟兩路歸并排序 void Merge(SL *L,SL *L1，int t，int m

21、，int n) for(i=t，j=m，k=t；idatai.keydataj.key) L1-datak=L-datai；i+； else L1-datak=L-dataj；j+； /* for */ if(idatakn=L1-dataim-1； if(jdatakn=L1-datajn； /*Merge*/,2020年8月9日,37,【例10-7】有一個(gè)序列12，9，44，10，99，61，65，43，76，其兩路歸并算法的過(guò)程：,初始關(guān)鍵字 12 9 44 10 99 61 65 43 76,一趟歸并后 9 12 10 44 61 99 43 65 76,二趟歸并后 9 10 12 4

22、4 43 61 65 99 76,三趟歸并后 9 10 12 43 44 61 65 99 76,四趟歸并后 9 10 12 43 44 61 65 76 99 ,2020年8月9日,38,兩路歸并排序思想：把序列所含的n個(gè)記錄看作n個(gè)有序的子序列，然后兩兩歸并，得n/2個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩歸并，以此類推直到得到的子序列長(zhǎng)度為n，排序完畢。,算法分析： 空間復(fù)雜度為O(n)。 時(shí)間復(fù)雜度：對(duì)包含n個(gè)數(shù)據(jù)元素的表，將這n個(gè)數(shù)據(jù)元素看作葉子結(jié)點(diǎn)，若將兩兩歸并生成的子表看作它們的父結(jié)點(diǎn)，則歸并過(guò)程對(duì)應(yīng)由葉子結(jié)點(diǎn)向根結(jié)點(diǎn)生成一棵二叉樹(shù)的過(guò)程。所以歸并趟數(shù)約等于二叉樹(shù)的高度-1，即log2

23、n，每趟歸并需移動(dòng)記錄n次，故為O(nlog2n)。,2020年8月9日,39,是一種借助于多關(guān)鍵碼排序的思想，將單關(guān)鍵碼按基數(shù)分成“多關(guān)鍵碼”進(jìn)行排序的方法。 多關(guān)鍵字排序的基本過(guò)程是首先根據(jù)多個(gè)關(guān)鍵字分別排序，最后再將其合并到一起。,【例10-8】撲克牌中52張牌，可按花色和面值分成兩個(gè)字段，其大小關(guān)系為： 花色：方塊 梅花 紅心 黑心 面值：2345678 9 10 J Q K A 若對(duì)撲克牌按花色、面值進(jìn)行升序排序，得到如下序列: 方塊2,3,.,A，梅花2,3,.,A，紅心2,3,.,A，黑心2,3,.,A,10.6 基數(shù)排序,2020年8月9日,40,本節(jié)假設(shè)記錄的關(guān)鍵字為整型。最

24、低位優(yōu)先法：即是首先根據(jù)關(guān)鍵字最低位(個(gè)位)有效數(shù)字進(jìn)行排序，然后根據(jù)次低位(十位)有效數(shù)字進(jìn)行排序，以此類推，直到根據(jù)最高位有效數(shù)字進(jìn)行排序，產(chǎn)生一個(gè)有序序列。,假設(shè)有n個(gè)記錄，其關(guān)鍵字在0999之間，每位上有效數(shù)字在09之間共有10種可能性，則基數(shù)為10，在進(jìn)行“分配”操作時(shí)涉及10個(gè)隊(duì)列，即隊(duì)列的個(gè)數(shù)與基數(shù)相同。此處關(guān)鍵字最多位數(shù)是3，那么需要進(jìn)行3趟“分配”和“收集”操作。,2020年8月9日,41,【例10-9】對(duì)序列248，159，43，970，549，134，585，279，18，53進(jìn)行基數(shù)排序。,2020年8月9日,42,2020年8月9日,43,(f) 第三趟按百位數(shù)分配，

25、修改結(jié)點(diǎn)指針域，將鏈表中的記錄分配到相應(yīng)鏈隊(duì)列中,2020年8月9日,44,算法思路如下：,第一趟“分配”，根據(jù)關(guān)鍵字個(gè)位有效數(shù)字，把所有記錄分配到相應(yīng)的10個(gè)隊(duì)列中去。f0，e0表示0號(hào)隊(duì)列的頭、尾指針；f9，e9表示9號(hào)隊(duì)列的頭、尾指針；例如：關(guān)鍵字549的記錄被分配到9號(hào)隊(duì)列。 第一趟收集，把所有非空隊(duì)列按隊(duì)列號(hào)由小到大的順序?qū)㈥P(guān)鍵字出隊(duì)。此序列關(guān)鍵字的個(gè)位已經(jīng)有序；高位仍處于無(wú)序狀態(tài)。 以后各他趟，分別根據(jù)關(guān)鍵字的十位、百位有效數(shù)字重復(fù)類似第、步的“分配”與“收集”操作，最終將得到一個(gè)按照關(guān)鍵字由小到大的序列。,2020年8月9日,45,第一趟“分配”，根據(jù)關(guān)鍵字個(gè)位有效數(shù)字，把所有記

26、錄分配到相應(yīng)的10個(gè)隊(duì)列中去。f0，e0表示0號(hào)隊(duì)列的頭、尾指針；f9，e9表示9號(hào)隊(duì)列的頭、尾指針；例如：關(guān)鍵字549的記錄被分配到9號(hào)隊(duì)列。 第一趟收集，把所有非空隊(duì)列按隊(duì)列號(hào)由小到大的順序?qū)㈥P(guān)鍵字出隊(duì)。此序列關(guān)鍵字的個(gè)位已經(jīng)有序；高位仍處于無(wú)序狀態(tài)。 以后各他趟，分別根據(jù)關(guān)鍵字的十位、百位有效數(shù)字重復(fù)類似第、步的“分配”與“收集”操作，最終將得到一個(gè)按照關(guān)鍵字由小到大的序列。,2020年8月9日,46,算法分析： 時(shí)間復(fù)雜度：設(shè)待排序列含n個(gè)記錄，d個(gè)關(guān)鍵碼，關(guān)鍵碼的基數(shù)為radix，則進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+radix)，其中，一趟分配時(shí)間復(fù)雜度為O(n)，一趟收集時(shí)

27、間復(fù)雜度為O(radix)，共進(jìn)行d趟分配和收集。,綜合比較上述討論的各種內(nèi)部排序方法，其性能指標(biāo)如表9-1所示。通常從下面二方面衡量排序方法的性能，一方面數(shù)據(jù)排序期間的運(yùn)算量，一般考慮關(guān)鍵字的比較次數(shù)和記錄的平均移動(dòng)次數(shù)；另一方面，數(shù)據(jù)排序期間所需要的輔助存儲(chǔ)空間。,2020年8月9日,47,10.7 內(nèi)部排序的比較,2020年8月9日,48,在應(yīng)用中，應(yīng)根據(jù)不同情況、不同要求選擇較合適的方法，甚至可將多種方法結(jié)合使用。下面幾點(diǎn)建議，僅供讀者參考。 (1)當(dāng)待排序的記錄數(shù)n不大時(shí)(約n50)，可選用表中前三種排序方法。它們的時(shí)間復(fù)雜度雖為O(n2)，但方法簡(jiǎn)單，容易實(shí)現(xiàn)。 (2)當(dāng)n值很大，

28、不強(qiáng)求排序穩(wěn)定性，并且內(nèi)存容量不寬余時(shí)，應(yīng)選用快速排序或堆排序。一般來(lái)講，他們排序速度非?？?。 (3)當(dāng)n值很大，對(duì)排序穩(wěn)定性有要求，并內(nèi)存容量寬余時(shí)，用歸并排序最為合適。,2020年8月9日,49,10.8.1 外部排序 在對(duì)大型文件排序時(shí)，由于文件很大，不可能將整個(gè)文件的所有記錄都同時(shí)調(diào)入內(nèi)存中進(jìn)行排序，就要利用外部排序技術(shù)來(lái)完成排序。,外部排序方法最常用的是多路歸并法。這種方法基本要經(jīng)過(guò)兩個(gè)步驟： 第一步，按可按內(nèi)存大小，將外存上含n個(gè)記錄的文件分成若干個(gè)長(zhǎng)度為k的子文件或段(segment)，依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序，并將排序結(jié)果重新寫入外存。通常稱這些有序子

29、文件為歸并段或順串；,10.8 外部排序,2020年8月9日,50,假設(shè)有一個(gè)含 10000 個(gè)記錄的文件，首先通過(guò)10次內(nèi)部排序得到10個(gè)初始?xì)w并段 A1A10 ，其中每一段都含1000個(gè)記錄。然后對(duì)它們作如圖9-12所示的兩兩歸并，直至得到一個(gè)有序文件為止。,將兩個(gè)有序段歸并成一個(gè)有序段的過(guò)程，若在內(nèi)存中進(jìn)行，前面討論的兩路歸并排序中的Merge函數(shù)便可實(shí)現(xiàn)此歸并。,第二步，對(duì)這些歸并段進(jìn)行逐趟歸并，使歸并段(有序子文件)逐漸由小到大，最后在外存上形成一個(gè)排序文件。,2020年8月9日,51,一般情況下，外部排序所需總時(shí)間=內(nèi)部排序所需時(shí)間mtis + 外存信息讀寫的時(shí)間dtio +內(nèi)部歸并排序所需時(shí)間sutmg,其中：tis是為得到一個(gè)初始?xì)w并段進(jìn)行的內(nèi)部排序所需時(shí)間的均值；tio是進(jìn)行一次外存讀/寫時(shí)間的均值；utmg是對(duì)u個(gè)記錄進(jìn)行內(nèi)部歸并所需時(shí)間；m為經(jīng)過(guò)內(nèi)部排