1、10.1 插入排序10.2 交換排序10.3 選擇排序第十章 排序10.5 基數排序10.4 歸并排序1設有記錄序列： R1, R2, , Rn ;其相應的關鍵字序列為： K1, K2 , , Kn ; 若存在一種確定的關系： Ki1 Ki2 Kin ；則將記錄序列 R1, R2, . , Rn 排成按該關鍵字有序的序列： Ri1, Ri2, , Rin 的操作，稱之為排序。概述2內部排序：全部記錄都可以同時調入內存進行的排序。 外部排序：文件中的記錄太大，無法全部將其同時調入內存進行的排序。穩(wěn)定的排序方法：若記錄序列中的任意兩個記錄 Rx、Ry 的關鍵字 Kx = Ky ；如果在排序之前和排

2、序之后，它們的相對位置保持不變，則這種排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的排序方法簡單的排序方法： T(n)=O(n2)先進的排序方法： T(n)=O(nlog2n)3順序表的存儲結構：#define MAXSIZE /定義一個常數typedef struct KeyType key：； /關鍵字成員 ； /其它成員 RecordTypetypedef struct RecordType rMAXSIZE+1；/r0號單元不存記錄 int length； / 順序表的長度 SqList；4在數組r1，r2， ，rn 中從第二個元素起，將其依次插入到前面已排好序的序列中。10.1.1 直接插入排序

3、設立監(jiān)視哨：rir0r1 r2 rj rj+1 ri-1 ri 小 大 r0兩種移位方法(1) j從i-1開始，一邊比較，一邊移位。(2)先查找位置再移位。找j，使 rj ri rj+110.1 插入排序5 3 8 2 5 9 1 6i=13 1 2 3 5 6 8 9 1 2 3 5 8 9 6 2 3 5 8 9 1 6 2 3 5 8 9 1 6 2 3 8 5 9 1 625916例： 關鍵字序列（8，3，2，5，9，1，6)r= r0 r1 r2 r3 r4 r5 r6 r7 8 3 2 5 9 1 6i=2i=3i=4i=5i=6i=76void straightsort1(SqL

4、ist &L)/設立監(jiān)視哨：rir0，在查找的過程中同時后移記錄 for(i=2；iL.length；i+) L.r0=L.ri； j=i-1； x = L.r0.key； while(xL.rj.key) L.rj+1=L.rj； j- ； L.rj+1= L.r0； /straightsort時間分析：T=方法1：邊比較邊移動7void straightsort2(SqList &L) for(i=2；iL.length；i+) L.r0=L.ri； j=i-1； x=L.r0.key； while(xL.rj.key) j-； for(k=i-1；k j+1；k-) L.rk+1=L.r

5、k； L.rj+1=L.r0；/straightsort1方法2：先定位后移動8性能分析：(1) 時間： 總時間包括：關鍵字的比較和記錄的移動。最好情況：O(n)； 最壞情況：O(n2)平均時間： T(n)=O(n2)(2) 空間： 一個記錄空間。S(n)=O(1)；(3) 穩(wěn)定性： 穩(wěn)定的排序方法。當記錄“基本有序”或n不太大時，該方法為最佳方法910.1.2 折半(二分)插入排序與直接插入排序的區(qū)別： 在查找位置時使用折半查找。例: 在有序集(13,42,46,55,94) 中插入17和46lowmidhighhigh 1 2 3 4 5 6 7 8 913 42 46 55 94 low

6、mid 插入17 mid high1 2 3 4 5 6 7 8 913 17 42 46 55 9410插入46lowmidhighhigh low mid lowmid 1 2 3 4 5 6 7 8 913 17 42 46 46 55 941 2 3 4 5 6 7 8 913 17 42 46 55 9411void binsort(SqList &L)for(i=2；iL.length；i+) L.r0=L.ri； low=1； high=i-1； while(low high) /以下折半查找確定插入位置high+1 mid=(low + high)/2； if(L.r0.key

7、L.rmid.key) high=mid-1； else low = mid+1； ； for(k=i-1；khigh+1；k-) L.rk+1=L.rk；L.rhigh+1=L.r0； /end_for /binsort 12性能分析：(1)時間：減少了與關鍵字比較的次數，記錄移動次數不變。最好情況： 只需比較，不需移動。 比較次數：O(nlog2n)最壞情況：O(n2)；平均時間： T(n)=O(n2)(2)空間： 一個記錄空間。S(n)=O(1)；(3)穩(wěn)定性： 穩(wěn)定的排序方法。13基本思想：先取一個正整數d1n，把所有相隔d1的記錄放一組，組內進行直接插入排序；然后取d2=5時，di=

8、 (di-1+1)/2 否則：di = (di-1+1)/3 又稱“縮小增量”排序14例：初始關鍵字如下：n=11， d1=5，d2=3，d3=1 49 38 65 97 76 13 27 49 55 04 1010 27 49 55 04 13 38 65 97 76 4910 04 13 38 27 49 55 49 97 76 65例1：當n=10時， d1=5， d2=3， d3=1。例2：n=27時，d1=13， d2=7，d3=4，d4=1。04 10 13 27 38 49 49 55 65 76 9715在每一趟shell排序中，可對相距為dk的dk組子序列分別進行直接插入排序

9、。設增量為step， 則step個子序列分別是：(1) r1， rstep+1， r2step+1， (2) r2， rstep+2， r2step+2， (step) rstep， r2step， r3step， ijijiiijjjj16例49 38 65 97 76 13 27 48 55 4ji49133827一趟排序： 13 27 48 55 4 49 38 65 97 76jiji274jiji5538jijiji二趟排序： 13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji7641 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6

10、 7 8 9 101 2 3 4 5 6 7 8 9 10ji增量序列：int d=5，3，1;17void shellpass(SqList &L，int step)/將L.r1.n按間距step分組進行一趟shell排序for(i=step+1;iL.length;i+) /從每組第二個元起處理 temp=L.ri； j=i-step； while(j1 & temp.keyd1d2 dt=1每一趟shell排序已用函數shellpass實現，共需要t 趟，其中第i趟的增量為di。void shellsort (SqList &L，int dt) for(k=0；kri+1.key，則ri

11、 ri+1， (i=1n-1)一趟起泡后，最大的元素就落在最底部。第二趟起泡排序的范圍是r1 . n-1；直到沒有任何交換；最多需要n-1趟冒泡排序10.2.1 冒泡排序10.2 交換排序20 37，18，64，14，96，48，96，42 例: 關鍵字序列 (37, 18, 64, 14, 96, 48, 96, 42)第1趟結果 18，37，14，64，48，96，42 9618，3714，6448，9642，9614，3748，64第2趟結果 18，14，37，48，42，64 96 96第3趟結果 14，18，37，42，48 64 96 96第4趟結果 14，18，37，42，48

12、64 96 9642，9614，1842，48無交換，完成。21void bubblesort(SqList &L)/設一個標志flag，當本趟有交換則flag置為1，否則為0 。 i=1； /初始化，i為趟數 while(iL.rj+1.key） L.rj L.rj+1； flag=1； if (flag) i+ ； /如果有交換，進行下一趟 else break； /bubblesort22性能分析：(1) 時間：最好情況：初始序列已經有序，只需一趟冒泡排序，不交換任何元素。T= O(n)最壞情況：初始序列與目標序列的順序相反。 T=O(n2)(2) 空間： 一個記錄空間。S(n)=O(1

13、)；(3) 穩(wěn)定性： 穩(wěn)定的排序方法。平均情況T=O(n2)2310.2.2 快速排序基本思想：在待排序列中選一個關鍵字，按某一規(guī)律進行多次比較交換后，它移到某一位置，此元素將記錄分割成獨立的兩部分，它左邊的關鍵字都小于或等于它，右邊的關鍵字都大于或等于它。之后對這兩部分分別進行快速排序24s k-1 k k+1 t k-1 k+1 s k txs t25 第四次交換 68 11 70 23 70 18 93 73 例： 70 73 70 23 93 18 11 68第一次交換 68 73 70 23 93 18 11 70 第二次交換 68 70 70 23 93 18 11 73ijiji

14、 第三次交換 68 11 70 23 93 18 70 73iij 第五次交換 68 11 70 23 18 70 93 73i 完成一趟排序 68 11 70 23 18 70 93 7326完成一趟排序 68 11 70 23 18 70 93 73ij第1次交換： 18 11 70 23 68 jii第2次交換： 18 11 68 23 70 第3次交換： 18 11 23 68 70 i完成兩趟排序： 18 11 23 68 70 ij 73 93i 73 93第1次交換 ： 18 11 23ijj第2次交換 ： 11 18 23i完成三趟排序：11 18 23 27快速排序 (分兩步

15、)：(1) 求劃分元素的位置。(2) 分別對兩個子序列進行快速排序。void qksort(SqList &L，int s，int t) if (st) k=partition(L，s，t)；/求劃分元素的位置 qksort(L，s，k-1)； qksort(L，k+1，t) /qksort 28int partition(SqList &L，int s，int t) /對L.rst中的記錄進行一趟快速排序，返回k的值，當uk時，L.ru.key L.rk.key，當kv時，L.rk.key L.rv.key i=s； j=t； while(ij) while (ij & L.ri.keyL.

16、rj.key) j-； L.ri L.rj； while (ij & L.ri.key L.rj.key) i+； L.ri L.rj； return i； / partition29性能分析：(1) 時間：最壞情況：初始序列已經有序或基本有序，則劃分不能將序列劃分成兩個子序列。T=O(n2)最好情況：初始序列分布比較均勻，劃分將序列劃分成長度近似相等的兩個子序列。T =O(nlog2n) 例：4 1 3 2 6 5 7平均情況： O(nlog2n)(2) 空間： 最好情況：S(n)=O(log2n) 最壞情況：S(n)=O(n)(3) 穩(wěn)定性： 方法不穩(wěn)定。30第1趟：在r1.n中進行n-1

17、次比較，選擇最小的rk，讓rk r1；第i趟：在ri.n中進行n-i次比較，選擇最小的rk，讓rk ri；第n-1趟：在rn-1.n中進行1次比較，選擇最小的rk，讓rk rn-1；第i趟：在n-i+1(i=1，2，n-1)個記錄中選擇值最小的記錄作為有序序列的第i個記錄。10.3.1 直接選擇排序10.3 選擇排序31例：數組：（37，18，64，14，96，48，42）第1 趟結果 14 18，64，37，96，48，42(i=2，k=2)第2趟結果 14 18 64，37，96，48，42(i=3,k=4)第3趟結果 14 18 37 64，96，48，42 (i=4，k=7)第4趟結果

18、 14 18 37 42 96，48，64(i=5，k=6)當i=1時 : 37，18，64，14，96，48，42(i=1，k=4)第5趟結果 14 18 37 42 48 96，64(i=6，k=7)第6趟結果 14 18 37 42 48 64 9632void selectsort(SqList &L) for(i=1；iL.length；i+) k=i； for(j=i+1；jL.length；j+) if(L.rj.keyL.rk.key) k=j； if(ki) L.rk L.ri /selectsort時間：33性能分析：(1) 時間： 該算法不受初始序列特征的影響。 T(n)

19、= O(n2)(2) 空間： 一個記錄空間：S(n)= O(1）(3) 穩(wěn)定性： 不穩(wěn)定的排序方法。例：（6，6，4）3410.3.2 樹型選擇排序又稱錦標賽排序?；舅枷耄菏紫葘個記錄的關鍵字進行兩兩比較，然后在其中 n/2 個較小者之間再進行兩兩比較，如此重復，直到選出最小關鍵字的記錄為止。這個排序過程可用一棵有n個葉子結點的完全二叉樹表示。35輸出最小關鍵字之后，將該關鍵字對應的葉子結點中的關鍵字改為最大值，然后從該葉子結點開始，和其左（右）兄弟的關鍵字進行比較， 49389765132776493865132738131336含n個葉子結點的完全二叉樹的深度為 log2n +1， 除

20、了最小的關鍵字之外，每選擇一個次小關鍵字需進行l(wèi)og2n次比較。缺點：(1) 輔助存儲空間較多，對n個記錄需2n-1個存儲單元。(2) 和最大值的比較是多余的。T(n) = O(nlog2n)49389765132776493865132738131376272737堆：n個元素的序列k1，k2，kn，當且僅當滿足以下關系時，稱之為堆。 ki k2i ki k2i ki k2i +1 ki k2i +110.3.3 堆排序或i=1，2， ，n/2小根堆大根堆若將此序列看成是完全二叉樹的按層次遍歷的序列，則完全二叉樹中所有非終端結點的值均不大于(或不小于)其左右孩子的值。2i2i+1i38例：序

21、列96，83，27，38，11，09 對應的完全二叉樹為：大根堆96832738110939例：序列12，36，24，85，47，30，53，91 對應的完全二叉樹為：小根堆123624854730539140堆排序：輸出堆頂的最小值之后，使得剩余的n-1個元素的序列重又建成一個堆，則得到次小值，如此反復執(zhí)行，便得到有序序列。實現堆排序需解決兩個問題：(1) 如何由一個無序序列建成一個堆？(2) 如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆？41堆排序：已知一個堆，將堆頂元素與堆中最后一個元素交換，之后只需調整根結點即可。123624854730539112914291362485473

22、05312篩選：自堆頂到葉子的調整過程。假設 rk+1 . m中各元素已滿足堆的性質，編寫篩選算法 sift 調整rk， 使整個序列rk . m中各元素滿足堆的性質。91912430itjjiji43void sift(SqList &L，int k，int m)/ L.rk. m是以L.rk為根的完全二叉樹 ，以L.r2k和/L.r2k+1為根的完全二叉樹滿足堆的性質，調整L.rk， 使整/個序列L.rk . m中各元素滿足堆的性質。 i=k； j=2*i； t=L.rk； while (jm) if(jm & L.rj+1.key L.rj.key) j+； / 在i的左右孩子中選小的為j

23、 if(t.keyL.rj.key) break； else L.ri=L.rj；i=j；j=2*i； ； L.ri=t；最壞時間： log2n +1-1= log2(m-k+1)44初始建堆： 從一個無序序列建堆的過程就是一個反復“篩選”的過程。 將 n 個元素的序列看成是一個完全二叉樹，則最后一個非葉子結點是第n/2個元素。 從第n/2個元素開始篩選，一直篩選到第1個元素，就建立了堆。45例：已知序列 49，38，65，97，76，13，27，49， 將此序列初始建堆。從 i=4開始：i=3時，調整49386597761327499749651349491327i=2不用調整i=1時，調整

24、46973827497665491313382749766549972797堆排序如下：974997384949766527133849499776652713篩選后476549499776382713篩選后49654997763827137665499749382713篩選后4965769749382713489765764949382713篩選后65977649493827137697654949382713977665494938271349void heapsort(SqList &L)/對L.r1.L.length進行堆排序，使L.r1.L.length按關鍵字從大到小有序 for(

25、i=L.length/2；i1；i-) sift(L.r，i，L.length)； /以ri為根初始建隊 for(i=L.length；i2；i-) L.ri L.r1； sift(L.r，1，i-1)；/調整r1，使r1.i-1是堆 ； /heapsort50(n*log2n)/2 +n*log2n=(3*n*log2n)/2平均時間： T(n)=O(n*log2n)(2) 空間： 一個記錄空間。 S(n)=O(1)；(3) 穩(wěn)定性： 不穩(wěn)定的排序方法。 適合大量記錄的排序。性能分析：(1) 時間：最壞情況：T=-+-=niniiin222/121)(log)1(log51歸并：將兩個或兩個

26、以上的有序表合并成一個有序表二路歸并：將兩個有序表合并成一個有序表。多路歸并：將兩個以上的有序表合并成一個有序表。二路歸并排序： 設初始序列含有n個記錄，歸并排序把此序列看成是由n個只包含一個記錄的有序表組成，然后進行兩兩歸并，最后形成包含n個記錄的有序表。10.4 歸并排序52例：已知關鍵字序列： 46，55，13，42，94，05，17，70，60 第一趟：46 5513 4205 9417 7060第二趟：13 42 46 5505 17 70 9460第三趟：05 13 17 42 46 55 70 9460第四趟：05 13 17 42 46 55 60 70 94 歸并排序過程如下

27、：初始狀態(tài)：46551342940517706053算法： 假設n個記錄的序列放在數組r1.n中，設 L為歸并段（子表）的長度，在一趟歸并中要進行兩兩歸并，分別使長度為 L 的兩兩相鄰的子表歸并為一個有序的子表。開始時取 L=1；第一趟歸并排序后，L=L*2；再進行下一趟歸并， ，直到排序結束。子表的長度L分別： 1，2，4，8，2i-154 已知： rs.m和 rm+1.n分別按關鍵字有序，本算法將其歸并為一個有序序列，歸并后的結果存放在數組 r1s.n 中。設變量 i， j分別指向兩個歸并段的開始位置， rs . m rm+1 . n i所指的關鍵字與j所指的關鍵字進行比較， 取小者放在結

28、果數組r1中。ij算法1:兩個相鄰的有序表歸并成一個有序表merge(r，r1，s，m，n)55void merge(RecordType r ，RecordType &newr ，int s，int m，int n)/已知數組rs.m和rm+1.n分別按關鍵字有序，將它們歸并新/數組newrs.n中，使newrs.n按關鍵字有序 i=s； j= m+1； k= s-1； /初始化 while (im & jn) k+； / 插入位置 if(ri.keyrj.key) newrk=ri； i+； else newrk=rj； j+ ； while(im) k+；newrk=ri；i+； whi

29、le(jn) k+；newrk=rj；j+； /merge 56算法2: 一趟歸并 mergpass(r，r1，L，n) 兩段等長數組的歸并： 從待排序列的第一個記錄開始，按歸并長度L進行“兩兩歸并”， 設變量i記錄第一個歸并段的起始位置。則相鄰的兩個歸并段的位置如下：開始時 i=1，相鄰的兩段歸并完成后 i=i+2*L；再進行下兩個歸并段的歸并。循環(huán)的條件：下兩個歸并段存在；即： i+2L-1 n 兩段不等長數組的歸并; (最后一段長度 L) 最后一段的長度L； i i+L-1 i+L i+2L-157void mergpass(RecordType r ， RecordType &r1，

30、int L，int n)/將數組r中長度各為L的相鄰的兩個子列歸并為長度為2L的子/列,歸并后的結果存入數組r1中；n為數組總長度。 i=1； while (i+2*L-1n) / 夠兩組時歸并 merge(r，r1，i，i+L-1，i+2*L-1)；/兩組歸并 i = i+2*L ； if(i+L-1n) merge(r，r1，i，i+L-1，n)； / 剩余數據比一組多，但不夠兩組 else r1i.n= ri.n； /剩余數據不超過一組 / mergpass58算法3: 2-路歸并排序算法void mergsort(SqList &LS )/對數組LS.r中的記錄進行2-路歸并排序，te

31、mp為輔助數組 m =1； /子列長度初始化 while (mLS.length) mergpass(LS，temp，m，LS.length)； /將LS.r按長度L歸并到temp數組中 LS.r1.LS.length=temp1.LS.length； /將一趟排序結果回送到r中 m = 2*m； /改變子列長度 /mergsort59性能分析：（1）時間：時間為歸并趟數與每一趟時間復雜性的乘積。歸并趟數為 log2n 。每一趟的比較次數和移動次數均等于數組中記錄的個數 n。 T(n) = O(nlog2n)（2）空間復雜度： S(n) = O(n)（3）穩(wěn)定性： 是穩(wěn)定的排序方法。60多關鍵字排序例: 對52張撲克牌按以下次序排序： 兩個關鍵字：花色（） 面值（23A）并且“花色”地位高于“面值” 23A23A23A23A10.5 基數排序61兩種方法：最高位優(yōu)先 (MSD)先對最高位關鍵字k1(如花色)排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關鍵字k2(如面值)排序，又分成若干更小的子序列；依次重復，直至就每個子序列對最低位關鍵字kd排