嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)(排序)【業(yè)界相關(guān)】

1、第九章 內(nèi)部排序,分類(lèi)： 內(nèi)部排序：全部記錄都可以同時(shí)調(diào)入內(nèi)存進(jìn)行的排序。 外部排序：文件中的記錄太大，無(wú)法全部將其同時(shí)調(diào)入內(nèi)存進(jìn)行的排序,定義：設(shè)有記錄序列： R1、R2 . Rn 其相應(yīng)的關(guān)鍵字序列為： K1、K2 . Kn ; 若存在一種確定的關(guān)系： Kx = Ky = = Kz則將記錄序列 R1、R2 . Rn 排成按該關(guān)鍵字有序的序列： Rx、Ry . Rz 的操作，稱(chēng)之為排序。 關(guān)系是任意的，如通常經(jīng)常使用的小于、大于等關(guān)系。 穩(wěn)定與不穩(wěn)定：若記錄序列中的任意兩個(gè)記錄 Rx、Ry 的關(guān)鍵字 Kx = Ky ；如果在排序之前和排序之后，它們的相對(duì)位置保持不變，則這種排序方法是穩(wěn)定的，

2、否則是不穩(wěn)定的,9.1 插入排序 直接插入排序 排序過(guò)程：整個(gè)排序過(guò)程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序,算法描述,例,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49 65 76 97) 27,i=1 (,i=7 (13 38 49 65 76 97)

3、27,27,97,76,65,49,38,27,0 1 2 3 4 5 6 7,算法評(píng)價(jià) 時(shí)間復(fù)雜度 若待排序記錄按關(guān)鍵字從小到大排列(正序) 關(guān)鍵字比較次數(shù),記錄移動(dòng)次數(shù),0 1 2 3 4 5 6 7,13 27 38 49 65 76 97,若待排序記錄按關(guān)鍵字從大到小排列(逆序) 關(guān)鍵字比較次數(shù),記錄移動(dòng)次數(shù),0 1 2 3 4 5 6 7,97 76 65 49 38 27 13,若待排序記錄是隨機(jī)的，取平均值 關(guān)鍵字比較次數(shù),記錄移動(dòng)次數(shù),T(n)=O(n,空間雜度：S(n)=O(1,折半插入排序 排序過(guò)程：用折半查找方法確定插入位置的排序叫,例,i=1 (30) 13 70 85

4、 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,i=8 20 (6 13 20 30 39 42 70 85,算法描述,算法評(píng)價(jià) 時(shí)間復(fù)雜度：T(n)=O(n) 空間復(fù)雜度：S(n)=O(1,希爾排序(縮小增量法) 排序過(guò)程：先取一個(gè)正整數(shù)d1n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹?算法描述,define T 3 int d=5,3,1,49,13,38,27,27,4,55,38,65,48

5、,97,55,76,4,1 2 3 4 5 6 7 8 9 10,1 2 3 4 5 6 7 8 9 10,1 2 3 4 5 6 7 8 9 10,希爾排序特點(diǎn) 子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列 希爾排序可提高排序速度，因?yàn)?分組后n值減小，n更小，而T(n)=O(n),所以T(n)從總體上看是減小了 關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序 增量序列取法 沒(méi)有除1以外的公因子 最后一個(gè)增量值必須為1,9.2 快速排序 冒泡排序 排序過(guò)程 將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r1.keyr2

6、.key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類(lèi)推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上 對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置 重復(fù)上述過(guò)程，直到“在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作”為止,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,1 2 3 4 5 6 7 8,算法描述,算法評(píng)價(jià) 時(shí)間復(fù)雜度 最好情況（正序）

7、 比較次數(shù)：n-1 移動(dòng)次數(shù)：0 最壞情況（逆序） 比較次數(shù),移動(dòng)次數(shù),空間復(fù)雜度：S(n)=O(1,T(n)=O(n,快速排序 基本思想：通過(guò)一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序,排序過(guò)程：對(duì)rst中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，設(shè)樞軸記錄rp=rs，x=rp.key 初始時(shí)令i=s,j=t 首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并和rp交換 再?gòu)膇所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄，和rp交換 重復(fù)上述兩步，直至i=j為止 再分別對(duì)兩個(gè)子序列進(jìn)行快

8、速排序，直到每個(gè)子序列只含有一個(gè)記錄為止,完成一趟排序： ( 27 38 13) 49 (76 97 65 50,分別進(jìn)行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97,快速排序結(jié)束： 13 27 38 49 50 65 76 97,49,27,49,65,13,49,49,97,x.key=49,完成一趟排序： ( 27 38 13) 49 (76 97 65 50,27,65,13,49,97,算法描述,算法評(píng)價(jià) 時(shí)間復(fù)雜度 最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n) 最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n,空間復(fù)雜度

9、：需?？臻g以實(shí)現(xiàn)遞歸 最壞情況：S(n)=O(n) 一般情況：S(n)=O(log2n,T(n)=O(n,9.3 選擇排序 簡(jiǎn)單選擇排序 排序過(guò)程 首先通過(guò)n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換 再通過(guò)n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換 重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束,例,初始： 49 38 65 97 76 13 27,i=1,13,49,一趟： 13 38 65 97 76 49 27,i=2,27,38,六趟： 13 27 38 49 65 76 97,排序結(jié)束： 13 27 38 49 65

10、76 97,算法描述,算法評(píng)價(jià) 時(shí)間復(fù)雜度 記錄移動(dòng)次數(shù) 最好情況：0 最壞情況：3(n-1) 比較次數(shù),空間復(fù)雜度：S(n)=O(1,T(n)=O(n,堆排序 堆的定義：n個(gè)元素的序列(k1,k2,kn)，當(dāng)且僅當(dāng)滿(mǎn)足下列關(guān)系時(shí)，稱(chēng)之為堆,例 （96，83，27，38，11，9,例 （13，38，27，50，76，65，49，97,可將堆序列看成完全二叉樹(shù)，則堆頂 元素（完全二叉樹(shù)的根）必為序列中 n個(gè)元素的最小值或最大值,堆排序：將無(wú)序序列建成一個(gè)堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù螅┲岛螅故Ｓ嗟膎-1個(gè)元素重又建成一個(gè)堆，則可得到n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有

11、序序列，這個(gè)過(guò)程叫 堆排序需解決的兩個(gè)問(wèn)題： 如何由一個(gè)無(wú)序序列建成一個(gè)堆？ 如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？ 第二個(gè)問(wèn)題解決方法篩選 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，若根結(jié)點(diǎn)值小于子樹(shù)的根結(jié)點(diǎn)值則與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱(chēng)這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選,例,算法描述,第一個(gè)問(wèn)題解決方法 方法：按關(guān)鍵字的初始序列建立一棵完全二叉樹(shù)，然后從無(wú)序序列的第n/2個(gè)元素（即此無(wú)序序列對(duì)應(yīng)的完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選,例 含8個(gè)元素的無(wú)

12、序序列（49，38，65，97，76，13，27，50,50,97,13,65,38,13,27,49,算法描述,算法評(píng)價(jià) 時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn) 空間復(fù)雜度：S(n)=O(1,9.4 歸并排序 歸并將兩個(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的有序序列為止,將下屬兩個(gè)已排序的順序表合并成一個(gè)有序表。 順序比較兩者的相應(yīng)元素，小者移入另一表中，反 復(fù)如此，直至其中任一表都移入另一

13、表為止,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,i,j,k,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,i,j,k,7,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,0 1 2 3

14、 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,1

15、3,49,65,76,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4 5 6 7,C,7,13,49,65,76,80,至此 B 表的元素都已移入 C 表，只需將 A 表的剩余部分移入 C 表即可,0 1 2 3 4,49,13,65,97,76,7,80,A,B,0 1 2 3 4

16、 5 6 7,C,7,13,49,65,76,80,至此 B 表的元素都已移入 C 表，只需將 A 表的剩余部分移入 C 表即可,97,例,初始關(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(nlog2n) 空間復(fù)雜度：S(n)=O(n,9.5 基數(shù)排序 多關(guān)鍵字排序 定義,例 對(duì)52張撲克牌按以下次序排序： 23A23A 23A23A 兩個(gè)關(guān)鍵字：花色（ ） 面值（23A） 并

17、且“花色”地位高于“面值,多關(guān)鍵字排序方法 最高位優(yōu)先法（MSD)：先對(duì)最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個(gè)有序序列,最低位優(yōu)先法(LSD)：從最低位關(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)鍵字都

18、是整個(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ì)列，fi和ei分別為第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è)有序序列,例,算法描述,算法評(píng)價(jià) 時(shí)間復(fù)雜度： 分配：T(n)=O(n) 收集：T(n)=O(rd) T(n)=O(d(n+rd) 其中：n記錄數(shù) d關(guān)鍵字?jǐn)?shù) rd關(guān)鍵字取值范圍 空間復(fù)雜度：S(n)=2rd個(gè)隊(duì)列指針+n個(gè)指針域空間,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,