基本數(shù)據(jù)結(jié)構(gòu)——排序10.10)

1、1 1。函數(shù)實(shí)現(xiàn)。函數(shù)實(shí)現(xiàn)( (初始化一個(gè)帶表頭結(jié)點(diǎn)的鏈表）初始化一個(gè)帶表頭結(jié)點(diǎn)的鏈表）node node * * initiatesl initiatesl (void) (void) node node * * h; h;h = (node h = (node * * )malloc(sizeof(node )malloc(sizeof(node); ); h-data = NULL;h-data = NULL;h-next = NULL; h-next = NULL; return (h);return (h); hNULLNULL NULLNULLwhile(p!=NULL)next=

2、p-next;p-next=pre;pre=p;p=next;nextpprepprea ai ia ai-1i-1a ai+1i+1a ai-2i-2a ai+2i+2void rev_list(node *h) /*請(qǐng)同學(xué)們?cè)诖颂幘幹颇孓D(zhuǎn)鏈表的程序段請(qǐng)同學(xué)們?cè)诖颂幘幹颇孓D(zhuǎn)鏈表的程序段*/node *pre,*next,*p;if(h=NULL) return;if(h-next=NULL) return;pre=h;p=h-next;while(p!=NULL)next=p-next;p-next=pre;pre=p;p=next;h-next-next=NULL;h-next = pre

3、;nexth hpprepprenextpprenextppreh ha a2 2a a1 1a a3 3a a0 0pprenext=nullh ha a2 2a a1 1a a3 3a a0 0P=nullpreh ha a2 2a a1 1a a3 3a a0 01.9 排序一、基本概念一、基本概念二、歸并排序二、歸并排序三、插入排序三、插入排序四、選擇排序四、選擇排序五、交換排序五、交換排序六、各種排序算法的六、各種排序算法的比較比較一、基本概念1. 1. 排序排序設(shè)有含設(shè)有含n n個(gè)記錄的序列為個(gè)記錄的序列為 R R1 1,R,R2 2, ,R,Rn n ，其相應(yīng)的關(guān)鍵字序列為，其相

4、應(yīng)的關(guān)鍵字序列為 K K1 1,K,K2 2,.,K,.,Kn n ?，F(xiàn)要求確定一種排序。現(xiàn)要求確定一種排序p p1 1,p,p2 2,.p,.pn n, , 使其關(guān)鍵字使其關(guān)鍵字滿足遞增（或遞減）的關(guān)系：滿足遞增（或遞減）的關(guān)系：K Kp1p1KKp2p2KKpnpn（或（或K Kp1p1KKp2p2 KKpnpn）使原序列成為一個(gè)按使原序列成為一個(gè)按關(guān)鍵字有序的序列關(guān)鍵字有序的序列： R Rp1p1,R,Rp2p2, ,R Rpnpn 一、基本概念2.2.排序方法的穩(wěn)定性排序方法的穩(wěn)定性若若K Ki i=K=Kj j(1in ,1jn ,ij)(1in ,1jn ,ij)，在排序前，在排序

5、前R Ri i領(lǐng)先于領(lǐng)先于R Rj j ，排序后排序后R Ri i仍領(lǐng)先于仍領(lǐng)先于R Rj j ，則稱此排序方法是，則稱此排序方法是穩(wěn)定穩(wěn)定的；反之稱為的；反之稱為不不穩(wěn)定穩(wěn)定的。的。3. 3. 排序的分類排序的分類o 若排序時(shí)待排序記錄存放在內(nèi)存中進(jìn)行排序，則稱為若排序時(shí)待排序記錄存放在內(nèi)存中進(jìn)行排序，則稱為內(nèi)部排序內(nèi)部排序；o 若待排序記錄數(shù)量很大，在內(nèi)存中一次不能容納全部記錄，需若待排序記錄數(shù)量很大，在內(nèi)存中一次不能容納全部記錄，需要在排序過(guò)程中對(duì)外存進(jìn)行訪問(wèn)，則稱為要在排序過(guò)程中對(duì)外存進(jìn)行訪問(wèn)，則稱為外部排序外部排序。一、基本概念4.4.基本操作基本操作1 1）對(duì)記錄中關(guān)鍵字大小進(jìn)行比

6、較；）對(duì)記錄中關(guān)鍵字大小進(jìn)行比較；2 2）將記錄從一個(gè)位置移到另一個(gè)位置。）將記錄從一個(gè)位置移到另一個(gè)位置。5. 5. 排序的時(shí)間開銷排序的時(shí)間開銷:(:(時(shí)間復(fù)雜度）時(shí)間復(fù)雜度） 排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來(lái)衡來(lái)衡量。量。6. 6. 算法執(zhí)行時(shí)所需的附加存儲(chǔ)算法執(zhí)行時(shí)所需的附加存儲(chǔ) 評(píng)價(jià)算法好壞的另一標(biāo)準(zhǔn)。評(píng)價(jià)算法好壞的另一標(biāo)準(zhǔn)。一、基本概念7. 7. 待排序的數(shù)據(jù)表待排序的數(shù)據(jù)表o 使用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)使用順序存儲(chǔ)結(jié)構(gòu)

7、存儲(chǔ)其數(shù)據(jù)類型定義如下：其數(shù)據(jù)類型定義如下：o 記錄結(jié)點(diǎn)的類型定義：記錄結(jié)點(diǎn)的類型定義：typedef structtypedef struct keywordtypekeywordtype key; key;datatypedatatype data; data;RECORDNODERECORDNODE;o 待排序的數(shù)據(jù)表是待排序的數(shù)據(jù)表是RECORDNODE類型的數(shù)組類型的數(shù)組structstruct RECORDNODE a; RECORDNODE a;二、歸并排序1 1. . 歸并，歸并，是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。o

8、 兩個(gè)有序表兩個(gè)有序表aal l aam m 和和aam m+1 +1 aan n 。它們可歸并成一個(gè)有序表。它們可歸并成一個(gè)有序表, , 存存于另一對(duì)象序列于另一對(duì)象序列b b的的bbl l bbn n 中。中。 這種歸并方法稱為這種歸并方法稱為兩路歸并兩路歸并 (2-way merging)(2-way merging)。i ik ki ik k1 m m+1 end1 m m+1 endab b08i ij jk k16k ki ij ji ij jk kk kj ji i2125k ki ij j25*k ki ij j37k kj ji i49k ki ij j54k ki i627

9、2 93設(shè)變量設(shè)變量 i i 和和 j j 分別是表分別是表aal l aam m 和和aam m+1 +1 aan n 的當(dāng)前檢測(cè)指針。的當(dāng)前檢測(cè)指針。變量變量 k k 是存放指針。是存放指針。當(dāng)當(dāng) i i 和和 j j 都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí)都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí), , 根據(jù)對(duì)應(yīng)項(xiàng)的排序碼的大小根據(jù)對(duì)應(yīng)項(xiàng)的排序碼的大小, ,依次把排序碼依次把排序碼小的對(duì)象排放到新表小的對(duì)象排放到新表 k k 所指位置所指位置中；中；當(dāng)當(dāng) i i 與與 j j 中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一個(gè)表中的剩余部分照抄到新表中。中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一個(gè)表中的剩余部分照抄到新表中。二、歸并排序o 兩路歸并

10、算法的函數(shù)實(shí)現(xiàn)兩路歸并算法的函數(shù)實(shí)現(xiàn)void merge(int start,int end,intvoid merge(int start,int end,int m,RECORDNODE a) m,RECORDNODE a)/ /* *將有序表將有序表a(start:start+m-1)a(start:start+m-1)和和a(start+m:end)a(start+m:end)歸并為一個(gè)新的有序表歸并為一個(gè)新的有序表a(start:end)a(start:end)* */ /RECORDNODE tempMAXSIZE;RECORDNODE tempMAXSIZE;intint i,j

11、,k; i,j,k;i=start;j=start+m;k=start;i=start;j=start+m;k=start;while(i=(start+m-1)&j=end)while(i=(start+m-1)&j=end)if(ai.keyaj.key)tempk=ai;k+;i+;if(ai.keyaj.key)tempk=ai;k+;i+;elsetempk=aj;k+;j+;elsetempk=aj;k+;j+;while(j=end)tempk=aj;k+;j+;while(j=end)tempk=aj;k+;j+;while(i=(start+m-1)tempk

12、=ai;k+;i+;while(i=(start+m-1)tempk=ai;k+;i+;for(i=start;i=end;i+)ai=tempi;for(i=start;i=end;i+)ai=tempi;/ /* *將臨時(shí)表的內(nèi)容存回到將臨時(shí)表的內(nèi)容存回到a a中中* */ / 二、歸并排序二、歸并排序2. 2. 歸并排序歸并排序o 歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序的。歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序的。其基本思想是：其基本思想是：o 假設(shè)初始對(duì)象序列有假設(shè)初始對(duì)象序列有 n n 個(gè)對(duì)象，首先把它看成是個(gè)對(duì)象，首先把它看成是 n n 個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為 1 1 的有序子序列的

13、有序子序列 ( (歸并項(xiàng)歸并項(xiàng)) )，先做兩兩，先做兩兩歸并，得到歸并，得到 n n / 2/ 2 個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為 2 2 的歸并項(xiàng)的歸并項(xiàng) ( (如果如果 n n 為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1)1)；再；再做兩兩歸并，做兩兩歸并，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為 n n 的有序序列。的有序序列。2125例：給出序列如圖。用歸并排序法排序過(guò)程如下例：給出序列如圖。用歸并排序法排序過(guò)程如下n=11o 歸并排序的算法Void MergeSort(RECORDNODE a,intVoid MergeSort(RECORDNOD

14、E a,int n) n)/ /* *對(duì)長(zhǎng)度為對(duì)長(zhǎng)度為n n的數(shù)組的數(shù)組a a排序排序* */ /intint length,left,right; length,left,right;left=1;length=1;left=1;length=1;while(lengthn)while(lengthn)right=min(n,left+2right=min(n,left+2* *length-1)length-1)Merge(left,right,length,a);Merge(left,right,length,a);if(right+lengthn) left=right+1;if(ri

15、ght+lengthn) left=right+1;/右邊還有待合并段右邊還有待合并段elselengthelselength* *=2;left=1;=2;left=1;/重新開始下一趟排序重新開始下一趟排序while(lengthn)while(lengthn)right=min(n,left+2right=min(n,left+2* *length-1)length-1)Merge(left,right,length,a);Merge(left,right,length,a);if(right+lengthn) left=right+1;if(right+lengthn) left=ri

16、ght+1;elselengthelselength* *=2;left=1;=2;left=1;o 歸并排序的算法Void MergeSort(RECORDNODE a,intVoid MergeSort(RECORDNODE a,int n) n)/ /* *對(duì)長(zhǎng)度為對(duì)長(zhǎng)度為n n的數(shù)組的數(shù)組a a排序排序* */ /intint length,left,right; length,left,right;left=1;length=1;left=1;length=1;while(lengthn)while(lengthn)right=min(n,left+2right=min(n,left

17、+2* *length-1)length-1)/限制限制rightright的值，使其不越界的值，使其不越界Merge(left,right,length,a);Merge(left,right,length,a);if(right+lengthn) left=right+1;if(right+lengthn) left=right+1;/右邊還有待合并段右邊還有待合并段elselengthelselength* *=2;left=1;=2;left=1;/重新開始下一趟排序重新開始下一趟排序二、歸并排序3. 3. 算法分析算法分析1) 1) 時(shí)間復(fù)雜度時(shí)間復(fù)雜度在函數(shù)在函數(shù)MergeSort

18、MergeSort中中whilewhile循環(huán)將被執(zhí)行循環(huán)將被執(zhí)行l(wèi)oglog2 2n n次次在每個(gè)在每個(gè)whilewhile循環(huán)中，將調(diào)用循環(huán)中，將調(diào)用MergeMerge函數(shù)函數(shù)n/(2length)n/(2length)次次而在每個(gè)而在每個(gè)MergeMerge函數(shù)中，將比較函數(shù)中，將比較lengthlength次次, ,故在每個(gè)故在每個(gè)whilewhile循環(huán)中，將比較循環(huán)中，將比較O(n)O(n)次次因此，此因此，此算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(nlogO(nlog2 2n)n)2) 2) 空間復(fù)雜度空間復(fù)雜度o 歸并排序占用附加存儲(chǔ)較多歸并排序占用附加存儲(chǔ)較多, , 需要另

19、外一個(gè)與原待排序需要另外一個(gè)與原待排序?qū)ο髮?duì)象數(shù)組同樣大小的輔助數(shù)組數(shù)組同樣大小的輔助數(shù)組。這是這個(gè)算法的缺點(diǎn)。這是這個(gè)算法的缺點(diǎn)。3) 3) 歸并排序是一個(gè)歸并排序是一個(gè)穩(wěn)定穩(wěn)定的排序算法的排序算法三、插入排序三、插入排序o 插入排序插入排序是將當(dāng)前是將當(dāng)前無(wú)序區(qū)中最前端無(wú)序區(qū)中最前端的記錄的記錄插入到有序區(qū)插入到有序區(qū)中，逐漸擴(kuò)大有中，逐漸擴(kuò)大有序區(qū)，直到所有記錄都插入到有序區(qū)中為止。序區(qū)，直到所有記錄都插入到有序區(qū)中為止。1. 直接插入排序直接插入排序1)1)基本思想是基本思想是 : : 當(dāng)插入第當(dāng)插入第i i ( (i i 1) 1) 個(gè)對(duì)象時(shí)個(gè)對(duì)象時(shí), , 前面的前面的 a1 , a

20、1 , , , aai i-1-1已經(jīng)排好序。這時(shí)已經(jīng)排好序。這時(shí), , 用用aai i 的排序碼與的排序碼與aai i-1, a-1, ai i-2, -2, 的關(guān)的關(guān)鍵碼順序進(jìn)行比較鍵碼順序進(jìn)行比較, , 找到插入位置即將找到插入位置即將aai i 插入插入, , 原來(lái)位置上的對(duì)象向原來(lái)位置上的對(duì)象向后順移。后順移。在有序區(qū)的前端在有序區(qū)的前端a0a0處設(shè)一個(gè)處設(shè)一個(gè)監(jiān)視哨監(jiān)視哨，存放當(dāng)前要插入的關(guān)鍵字。，存放當(dāng)前要插入的關(guān)鍵字。各趟排序結(jié)果各趟排序結(jié)果1 2 3 4 5 6監(jiān)視監(jiān)視哨哨 0 1 2 3 4 5 6252525 0 1 2 3 4 5 6494949void straigh

21、tinsert(RECORDNODE a,intvoid straightinsert(RECORDNODE a,int n) n)/ /* *使用直接插入排序法對(duì)數(shù)組使用直接插入排序法對(duì)數(shù)組a(1:n)a(1:n)排序排序* */ /for (i=2;i=n;i+)for (i=2;i=n;i+)a0=ai; /a0=ai; /* *設(shè)置監(jiān)視哨設(shè)置監(jiān)視哨* */ / j=i-1; j=i-1;while (a0.keyaj.key)while (a0.keyaj.key)aj+1=aj;aj+1=aj;j-;j-; aj+1=a0; aj+1=a0;252525* * * 0 1 2 3 4

22、 5 6161616 0 1 2 3 4 5 6080808 0 1 2 3 4 5 61 2 3 4 5 6完成三、插入排序2) 2) 算法分析算法分析o 設(shè)待排序?qū)ο髠€(gè)數(shù)為設(shè)待排序?qū)ο髠€(gè)數(shù)為n, n, 則該算法的則該算法的whilewhile循環(huán)執(zhí)行循環(huán)執(zhí)行n-1n-1趟。趟。o 關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵碼的初始排列有關(guān)。關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵碼的初始排列有關(guān)。最好情況下最好情況下( (正序正序),), 總的關(guān)鍵碼比較次數(shù)為總的關(guān)鍵碼比較次數(shù)為 n n-1, -1, 對(duì)象移動(dòng)次數(shù)為對(duì)象移動(dòng)次數(shù)為 2(2(n n-1)-1)。最壞情況下最壞情況下( (逆序逆序)

23、,), 則總關(guān)鍵碼比較次數(shù)則總關(guān)鍵碼比較次數(shù)KCNKCN和對(duì)象移動(dòng)次數(shù)和對(duì)象移動(dòng)次數(shù)RMNRMN分別為分別為nininnniRMNnn2)n1)-(iKCN2222141221/)()( ,/)(22void straightinsert(RECORDNODE a,intvoid straightinsert(RECORDNODE a,int n) n)/ /* *使用直接插入排序法對(duì)數(shù)組使用直接插入排序法對(duì)數(shù)組a(1:n)a(1:n)排序排序* */ /for (i=2;i=n;i+)for (i=2;i=n;i+)a0=ai; /a0=ai; /* *設(shè)置監(jiān)視哨設(shè)置監(jiān)視哨* */ j=i-

24、1;/ j=i-1;while (a0.keyaj.key)while (a0.keyaj.key)aj+1=aj;aj+1=aj;j-;j-; aj+1=a0; aj+1=a0;三、插入排序o 在平均情況下的排序碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為在平均情況下的排序碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n n2 2/4/4。因此，直接插。因此，直接插入入排序的時(shí)間復(fù)雜度為排序的時(shí)間復(fù)雜度為 o(o(n n2 2) )。o 空間復(fù)雜度空間復(fù)雜度:o(1):o(1)o 直接插入排序是一種直接插入排序是一種穩(wěn)定穩(wěn)定的排序方法的排序方法。練習(xí)：練習(xí)：在對(duì)一組記錄（在對(duì)一組記錄（54，38，96，23，15，72，6

25、0，45，83）進(jìn)）進(jìn)行直接插入排序時(shí)，當(dāng)把第行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄個(gè)記錄60插入到有序表時(shí)，為尋插入到有序表時(shí)，為尋找插入位置至少需比較找插入位置至少需比較 次。次。 三、插入排序2. 2. 折半插入排序折半插入排序1）與直接插入排序相比，除了采用的是折半查找尋找插入的位置外，其它類似。與直接插入排序相比，除了采用的是折半查找尋找插入的位置外，其它類似。2 2）算法）算法void BinarySort(RECORDNODE a,intvoid BinarySort(RECORDNODE a,int n) n)for (i=2;i=n;i+)for (i=2;i=n;i+)a0=ai

26、; low=1; high=i-1;a0=ai; low=1; high=i-1; while (lowhigh)while (lowhigh) mid=(low+high)/2;mid=(low+high)/2;if (a0.keyamid.key) high=mid-1;if (a0.key=low;j-) aj+1=aj;for (j=i-1;j=low;j-) aj+1=aj;alow=a0;alow=a0; 252525* * * 0 1 2 3 4 5 6161616 0 1 2 3 4 5 6三、插入排序3) 算法分析算法分析它所需的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o(wú)關(guān)它

27、所需的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o(wú)關(guān), , 僅依賴僅依賴于對(duì)象個(gè)數(shù)。將于對(duì)象個(gè)數(shù)。將 n n 個(gè)對(duì)象個(gè)對(duì)象( (為推導(dǎo)方便為推導(dǎo)方便, , 設(shè)為設(shè)為 n n=2=2k k ) )用折半插入排用折半插入排序所進(jìn)行的排序碼比較次數(shù)為：序所進(jìn)行的排序碼比較次數(shù)為：ninni222log1logo其記錄移動(dòng)的數(shù)目與直接插入排序相同其記錄移動(dòng)的數(shù)目與直接插入排序相同因此，因此，此算法的時(shí)間復(fù)雜度為此算法的時(shí)間復(fù)雜度為O(n2)o空間復(fù)雜度同直接插入排序空間復(fù)雜度同直接插入排序:O(1)o折半插入排序是一個(gè)折半插入排序是一個(gè)穩(wěn)定穩(wěn)定的排序算法的排序算法三、插入排序3. 希爾排序希爾排序1)

28、1) 希爾排序方法又稱為希爾排序方法又稱為縮小增量排序?？s小增量排序。2) 2) 該方法的基本思想是該方法的基本思想是 : : 設(shè)待排序?qū)ο笮蛄杏性O(shè)待排序?qū)ο笮蛄杏?n n 個(gè)對(duì)象個(gè)對(duì)象, , 首先首先取一個(gè)整數(shù)取一個(gè)整數(shù) gap n gap =1)while(d=1) for(i=d+1;i=n;i+) for(i=d+1;i0& 0& sj.keysj.keys0.key)s0.key) sj+d sj+d=sj=sj sj sj=s0;=s0;d=(d+1)/2;d=(d+1)/2;1 2 3 4 5 6494949252525* * *08080821212149494

29、9252525161616080808494949161616252525* * *0808082121212525251 2 3 4 5 63 3）函數(shù)實(shí)現(xiàn)）函數(shù)實(shí)現(xiàn)Void shellsort(RECORDNODE s,intVoid shellsort(RECORDNODE s,int n) n)/ /* *對(duì)記錄數(shù)組對(duì)記錄數(shù)組s1:ns1:n進(jìn)行希爾排序進(jìn)行希爾排序* */ / /* * d d1 1=n/2,d=n/2,di i=(d=(di-1i-1+1)/2 +1)/2 * */ /intint i,j,d;d=n/2; i,j,d;d=n/2;while(d=1)while(d

30、=1) for(i=d+1;i=n;i+) for(i=d+1;i0& 0& sj.keysj.keys0.key)s0.key) sj+d sj+d=sj=sj sj sj=s0;=s0;d=(d+1)/2;d=(d+1)/2;1 2 3 4 5 6希爾排序是一種希爾排序是一種不穩(wěn)定不穩(wěn)定的排序方法。的排序方法。1 2 3 4 5 6初始序列初始序列3.希爾排序3 3）函數(shù)實(shí)現(xiàn)）函數(shù)實(shí)現(xiàn)Void shellsort(RECORDNODE s,intVoid shellsort(RECORDNODE s,int n) n)/ /* *對(duì)記錄數(shù)組對(duì)記錄數(shù)組s1:ns1:n進(jìn)行希爾

31、排序進(jìn)行希爾排序* */ / /* * d d1 1=n/2,d=n/2,di i=(d=(di-1i-1+1)/2 +1)/2 * */ /intint i,j,d;d=n/2; i,j,d;d=n/2;while(d=1)while(d=1) for(i=d+1;i=n;i+) for(i=d+1;i0& 0& sj.keysj.keys0.key)s0.key) sj+d sj+d=sj=sj sj sj=s0;=s0;d=(d+1)/2;d=(d+1)/2;設(shè)待排序的記錄為設(shè)待排序的記錄為(20,16,13,14,19)(20,16,13,14,19)，經(jīng)過(guò)下列過(guò)程將這

32、些記錄排，經(jīng)過(guò)下列過(guò)程將這些記錄排序。序。20,16,13,14,1920,16,13,14,1916,20,13,14,1916,20,13,14,1913,16,20,14,1913,16,20,14,1913,14,16,20,1913,14,16,20,1913,14,16,19,2013,14,16,19,20所用的排序方法是所用的排序方法是 。A. A. 直接插入排序直接插入排序B. B. 冒泡排序冒泡排序C. C. 希爾排序希爾排序D. D. 堆排序堆排序四、選擇排序o 選擇排序選擇排序是不斷在待排序序列是不斷在待排序序列（無(wú)序區(qū)）中按記錄關(guān)鍵（無(wú)序區(qū)）中按記錄關(guān)鍵字遞增（或遞減

33、）次序選擇記錄字遞增（或遞減）次序選擇記錄，放入，放入有序區(qū)的一端有序區(qū)的一端，逐漸擴(kuò)大有序區(qū)，直到整個(gè)記錄區(qū)為有序區(qū)為止。逐漸擴(kuò)大有序區(qū)，直到整個(gè)記錄區(qū)為有序區(qū)為止。 其基本思想是其基本思想是: : 每一趟每一趟 ( (例如第例如第 i i 趟趟, , i i =1, 2, =1, 2, , , n n-1) -1) 在后面在后面 n-i n-i 個(gè)待排序?qū)ο笾羞x出排序碼最小的對(duì)個(gè)待排序?qū)ο笾羞x出排序碼最小的對(duì)象象, , 作為有序?qū)ο笮蛄械牡谧鳛橛行驅(qū)ο笮蛄械牡?i i 個(gè)對(duì)象。待到第個(gè)對(duì)象。待到第 n n-1 -1 趟作完趟作完, , 待排序?qū)ο笾皇Ｏ麓判驅(qū)ο笾皇Ｏ? 1個(gè)個(gè), , 就不

34、用再選了。就不用再選了。四、選擇排序1.1. 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序 基本步驟：在第基本步驟：在第i i趟趟(i=1(i=1開始開始) )(1)(1)在一組對(duì)象在一組對(duì)象 aai i aan n 中選擇具有最小關(guān)鍵字的對(duì)象；中選擇具有最小關(guān)鍵字的對(duì)象；(2)(2)若它不是這組對(duì)象中的第一個(gè)對(duì)象若它不是這組對(duì)象中的第一個(gè)對(duì)象, , 則將它與這組對(duì)象中的第則將它與這組對(duì)象中的第一個(gè)對(duì)象一個(gè)對(duì)象aiai對(duì)調(diào)對(duì)調(diào); ;(3)(3)在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵字的對(duì)象。在剩下的對(duì)象在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵字的對(duì)象。在剩下的對(duì)象aai i+1+1aan n 中重復(fù)執(zhí)行第中重復(fù)執(zhí)行第(1)(1

35、)、(2)(2)步步, , 直到剩余對(duì)象只有一直到剩余對(duì)象只有一個(gè)為止。個(gè)為止。251625*4921i = 1結(jié)束結(jié)束最小者最小者212525*16081 2 3 4 5 6初始初始493 3）算法）算法void SelectSort(RECORDNODE a,intvoid SelectSort(RECORDNODE a,int n) n)/ /* *對(duì)記錄數(shù)組對(duì)記錄數(shù)組a1:na1:n進(jìn)行簡(jiǎn)單選擇排序進(jìn)行簡(jiǎn)單選擇排序* */ /intint i,j,min;RECORDNODE t; i,j,min;RECORDNODE t;for (i=1;in;i+)for (i=1;in;i+)m

36、in=i;min=i;/ /* *記下位置記下位置* */ /for(j=i+1;j=n;j+)for(j=i+1;jaj.key) min=j;if (amin.keyaj.key) min=j;if (min!=i)if (min!=i)/ /* *交換交換* */ /t=amin; amin=ai; ai=t;t=amin; amin=ai; ai=t;jminjjj minj mini=12125251608491 2 3 4 5 649i = 2結(jié)束結(jié)束25*2521251625*4921i = 2最小者最小者3 3）算法）算法void SelectSort(RECORDNODE a

37、,intvoid SelectSort(RECORDNODE a,int n) n)/ /* *對(duì)記錄數(shù)組對(duì)記錄數(shù)組a1:na1:n進(jìn)行簡(jiǎn)單選擇排序進(jìn)行簡(jiǎn)單選擇排序* */ /intint i,j,min;RECORDNODE t; i,j,min;RECORDNODE t;for (i=1;in;i+)for (i=1;in;i+)min=i;min=i;/ /* *記下位置記下位置* */ /for(j=i+1;j=n;j+)for(j=i+1;jaj.key) min=j;if (amin.keyaj.key) min=j;if (min!=i)if (min!=i)/ /* *交換交換

38、* */ /t=amin; amin=ai; ai=t;t=amin; amin=ai; ai=t;minjjj minj49結(jié)果結(jié)果4925*1 2 3 4 5 6i = 425最小者最小者最小者最小者i = 54925各趟排序后的結(jié)果各趟排序后的結(jié)果49i = 325*2521最小者最小者1. 簡(jiǎn)單選擇排序4 4）算法分析）算法分析o 算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需進(jìn)行算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需進(jìn)行n-1n-1趟排序趟排序. .每趟內(nèi)層循每趟內(nèi)層循環(huán)需進(jìn)行環(huán)需進(jìn)行n-in-i次比較次比較. .每趟最好情況不交換每趟最好情況不交換. .最壞情況做一次交換，即最壞情況做一次交換

39、，即記錄移動(dòng)次數(shù)最多為記錄移動(dòng)次數(shù)最多為3 3。o 總的時(shí)間性能為總的時(shí)間性能為 比較次數(shù)：比較次數(shù)：n(n-1)/2(n(n-1)/2(所有情況相同所有情況相同) ) 移動(dòng)次數(shù)：移動(dòng)次數(shù)：最好情況為最好情況為0,0,最壞情況下為最壞情況下為3(n-1)3(n-1)o 所以總的時(shí)間復(fù)雜度為：所以總的時(shí)間復(fù)雜度為：O(nO(n2 2) )o 空間復(fù)雜度為：空間復(fù)雜度為：O(1) O(1) 交換記錄時(shí)用交換記錄時(shí)用3 3）算法）算法void SelectSort(RECORDNODE a,intvoid SelectSort(RECORDNODE a,int n) n)/ /* *對(duì)記錄數(shù)組對(duì)記錄

40、數(shù)組a1:na1:n進(jìn)行簡(jiǎn)單選擇排序進(jìn)行簡(jiǎn)單選擇排序* */ /intint i,j,min;RECORDNODE t; i,j,min;RECORDNODE t;for (i=1;in;i+)for (i=1;in;i+)min=i;min=i;/ /* *記下位置記下位置* */ /for(j=i+1;j=n;j+)for(j=i+1;jaj.key) min=j;if (amin.keyaj.key) min=j;if (min!=i)if (min!=i)/ /* *交換交換* */ /t=amin; amin=ai; ai=t;t=amin; amin=ai; ai=t;49i =

41、2結(jié)束結(jié)束25*2521251625*4921i = 2最小者最小者212525*16081 2 3 4 5 6初始初始4949結(jié)果結(jié)果o簡(jiǎn)單選擇排序是一種簡(jiǎn)單選擇排序是一種不穩(wěn)定不穩(wěn)定的排序算法的排序算法簡(jiǎn)單選擇排序是否是簡(jiǎn)單選擇排序是否是穩(wěn)穩(wěn)定定的排序算法？的排序算法？1 1：設(shè)待排序的記錄為：設(shè)待排序的記錄為(20,16,13,14,19)(20,16,13,14,19)，經(jīng)過(guò)下列過(guò)程將這些記，經(jīng)過(guò)下列過(guò)程將這些記錄排序。錄排序。20,16,13,14,1920,16,13,14,1916,20,13,14,1916,20,13,14,1913,16,20,14,1913,16,20,1

42、4,1913,14,16,20,1913,14,16,20,1913,14,16,19,2013,14,16,19,20所用的排序方法是所用的排序方法是 。A. A. 直接插入排序直接插入排序B. B. 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序 C. C. 希爾排序希爾排序2 2。設(shè)待排序的記錄為。設(shè)待排序的記錄為(20,16,13,14,19)(20,16,13,14,19)，經(jīng)過(guò)下列過(guò)程將這些記，經(jīng)過(guò)下列過(guò)程將這些記錄排序。錄排序。13,16,20,14,1913,16,20,14,1913,14,20,16,1913,14,20,16,1913,14,16,20,1913,14,16,20,1913,1

43、4,16,19,2013,14,16,19,20所用的排序方法是所用的排序方法是 。A. A. 直接插入排序直接插入排序B. B. 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序C. C. 希爾排序希爾排序四、選擇排序2. 2. 堆排序堆排序1) 1) 堆堆設(shè)有序列設(shè)有序列 k k1 1,k,k2 2, ,k,kn n ，若滿足：，若滿足： ），（或212212221niiiiiiiikkkkkkkk則稱該序列構(gòu)成的則稱該序列構(gòu)成的完全二叉樹完全二叉樹是一個(gè)是一個(gè)堆堆。 o 例，將序列：例，將序列： 96，83，27，38，11，9 構(gòu)成一棵完全二叉樹，構(gòu)成一棵完全二叉樹，并判斷是否是堆。并判斷是否是堆。96832

44、738119它是一個(gè)堆。堆頂元素為所有元素中的它是一個(gè)堆。堆頂元素為所有元素中的最大值最大堆最大值最大堆給定序列如何構(gòu)成完全二叉樹？給定序列如何構(gòu)成完全二叉樹？滿足堆條件的完全二叉樹有何特點(diǎn)？滿足堆條件的完全二叉樹有何特點(diǎn)？練習(xí)：練習(xí)：1 1。下列關(guān)鍵字序列中，。下列關(guān)鍵字序列中， 是堆。是堆。. 16, 72, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94，31, 72 . 16, 23, 53, 31, 94, 722. 堆排序2 2）堆的構(gòu)造：）堆的構(gòu)造： 由所給序列生成對(duì)應(yīng)的完全二叉樹；由所給序列生成對(duì)應(yīng)的完全二叉樹；

45、983273811序列：序列： 9，83，27，38，11 設(shè)完全二叉樹設(shè)完全二叉樹a1.na1.n中結(jié)點(diǎn)中結(jié)點(diǎn)akak的左右子樹均為堆，為的左右子樹均為堆，為構(gòu)成以構(gòu)成以akak為根結(jié)點(diǎn)的堆，需進(jìn)行調(diào)整。方法是將為根結(jié)點(diǎn)的堆，需進(jìn)行調(diào)整。方法是將akak的值的值與其左右子樹的根結(jié)點(diǎn)進(jìn)行比較，若不滿足堆的條件，則與其左右子樹的根結(jié)點(diǎn)進(jìn)行比較，若不滿足堆的條件，則將將akak與其左右子樹中根結(jié)點(diǎn)大的交換與其左右子樹中根結(jié)點(diǎn)大的交換，繼續(xù)進(jìn)行比較，直到，繼續(xù)進(jìn)行比較，直到所有子樹均滿足堆的定義為止。所有子樹均滿足堆的定義為止。2. 堆排序最大堆的向下調(diào)整算法最大堆的向下調(diào)整算法( (將大關(guān)鍵字移向

46、堆頂篩選算法將大關(guān)鍵字移向堆頂篩選算法) )Void Sieve(RECORDNODE a,int t,intVoid Sieve(RECORDNODE a,int t,int n) n)/ /* *將將at:nat:n建立為以建立為以atat為根的最大堆為根的最大堆* */ /intint i,j,k; i,j,k;i=t; j=2i=t; j=2* *i;a0=ai;/i;a0=ai;/* *aiai暫存到暫存到a0a0中中* */ /while(j=n)while(j=n)if(jn&aj.keyaj+1.key) j+;/if(jn&aj.keyaj+1.key) j+

47、;/* *選兩選兩子女的較大者子女的較大者* */ /if(a0.keyaj.key)if(a0.key=1;i-)for (i=p;i=1;i-)Sieve(a,i,n);Sieve(a,i,n);212525*4916081234564212525*16490813652例：序列：例：序列： 21，25，49，25*，16, 08，n=6,建建立初始的最大堆立初始的最大堆Sieve(a,3,6);Sieve(a,3,6);Sieve(a,2,6);Sieve(a,2,6);4212525*491608123564492525*210813652Sieve(a,1,6);Sieve(a,1,

48、6);練習(xí)：若一組記錄的排序碼為（練習(xí)：若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利），則利用堆排序的方法建立的初始堆為用堆排序的方法建立的初始堆為. 79, 46, 56, 38, 40, 84 . 84, 79, 56, 38, 40, 46 . 84, 79, 56, 46, 40, 38 . 84, 56, 79, 40, 46, 38 2. 堆排序3 3）堆排序）堆排序o 由以下兩個(gè)步驟進(jìn)行：由以下兩個(gè)步驟進(jìn)行： 由給定的無(wú)序序列構(gòu)造最大堆；由給定的無(wú)序序列構(gòu)造最大堆；最大堆堆頂最大堆堆頂a1a1具有最大的關(guān)鍵字具有最大的關(guān)鍵字, ,將將a1a1與與aa

49、n n 對(duì)調(diào)對(duì)調(diào), ,把具有最大關(guān)鍵字的對(duì)象交換到最后把具有最大關(guān)鍵字的對(duì)象交換到最后, ,再對(duì)前面的再對(duì)前面的n n-1-1個(gè)對(duì)象個(gè)對(duì)象, ,使用堆的調(diào)整算法使用堆的調(diào)整算法Sieve(a,1,Sieve(a,1,n n-1),-1),重新建立最大堆重新建立最大堆, ,具有次具有次最大關(guān)鍵字的對(duì)象又上浮到最大關(guān)鍵字的對(duì)象又上浮到a1a1位置。位置。o 再對(duì)調(diào)再對(duì)調(diào)a1a1和和aan-1n-1,調(diào)用調(diào)用Sieve(a,1,Sieve(a,1,n n-2),-2),對(duì)前對(duì)前n n-2-2個(gè)對(duì)象個(gè)對(duì)象重新調(diào)整，重新調(diào)整，。o 如此反復(fù)執(zhí)行，最后得到全部排序好的對(duì)象序列。這個(gè)算法如此反復(fù)執(zhí)行，最后得

50、到全部排序好的對(duì)象序列。這個(gè)算法即堆排序算法。即堆排序算法。4925211608123456082525*162149136542例：序列：例：序列： 21，25，49，25*，16, 08，建立初始，建立初始的最大堆，并進(jìn)行堆排序。的最大堆，并進(jìn)行堆排序。2525*0821161234564081625*252113652 21，25，49，25*，16, 0825*1608211234564081625*211365221160812345608162113654231608124561365422. 堆排序堆排序的算法堆排序的算法Void HeapSort(RECORDNODE a,in

51、tVoid HeapSort(RECORDNODE a,int n) n)/ /* *使用堆排序算法對(duì)記錄數(shù)組使用堆排序算法對(duì)記錄數(shù)組a1:na1:n按關(guān)鍵字遞增排序按關(guān)鍵字遞增排序* */ /intint i; i;for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n/2;i=1;i-) Sieve(a,i,n);/ /* *建立初始最大堆建立初始最大堆* */ /for(i=n;i=2;i-)for(i=n;i=2;i-)a0=a1; a1=ai;ai=a0;a0=a1; a1=ai;ai=a0;/ /* *交換交換a1a1和和aiai* */ /Sieve(a,1

52、,i-1);Sieve(a,1,i-1);/ /* *重建最大堆重建最大堆* */ / 練習(xí)：給定序列練習(xí)：給定序列19,01,23,68,35,19*,84,27,14.給出堆排序給出堆排序的各次過(guò)程。的各次過(guò)程。19012368 35 19* 8427 1419012368 35 19* 8427 1484682327 35 19* 1901 1414682327 35 19* 190168352327 14 19* 190101352327 14 19* 1935272301 14 19* 1919272301 14 19*27192301 14 19*19*192301 1423191

53、9*01 14141919*0119*19140101191419011414011401結(jié)束。結(jié)束。排序結(jié)果排序結(jié)果01,14,19,19*,23,27,35,68,84初始序列初始序列19,01,23,68,35,19*,84,27,142. 堆排序4) 4) 算法分析算法分析o 若設(shè)堆中有若設(shè)堆中有 n n 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), , 且且 2 2k k-1-1 n n 2 2k k, , 則對(duì)應(yīng)的完全二叉樹則對(duì)應(yīng)的完全二叉樹有有 k k 層。在第層。在第 i i 層上的結(jié)點(diǎn)數(shù)層上的結(jié)點(diǎn)數(shù) 2 2i-1 i-1 ( (i i = 1, 2, = 1, 2, , , k k) )。o 在第一個(gè)形成

54、初始堆的在第一個(gè)形成初始堆的 for for 循環(huán)中對(duì)每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆循環(huán)中對(duì)每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法調(diào)整算法Sieve( ),Sieve( ),因此該循環(huán)所用的計(jì)算時(shí)間為：因此該循環(huán)所用的計(jì)算時(shí)間為：112ki1- iik其中其中, , i i 是層序號(hào)是層序號(hào), 2, 2i-1 i-1 是第是第 i i 層的最大結(jié)點(diǎn)數(shù)層的最大結(jié)點(diǎn)數(shù), (, (k-ik-i) )是第是第 i i 層結(jié)點(diǎn)能夠移動(dòng)的最大距離。層結(jié)點(diǎn)能夠移動(dòng)的最大距離。njnjjikkjkjjjkkjjkki1- i2 2111111111122222)(Void HeapSort(RECORDNODE a,

55、intVoid HeapSort(RECORDNODE a,int n) n)intint i; i;for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n;i=2;i-)for(i=n;i=2;i-)a0=a1; a1=ai;ai=a0;a0=a1; a1=ai;ai=a0;Sieve(a,1,i-1);Sieve(a,1,i-1);因此形成初始堆的時(shí)間復(fù)雜度為因此形成初始堆的時(shí)間復(fù)雜度為O(n)2. 堆排序o 第二個(gè)第二個(gè)forfor循環(huán)中調(diào)用了循環(huán)中調(diào)用了n n-1-1次次Sieve( )Sieve( )

56、算法算法, , 該循環(huán)的該循環(huán)的計(jì)算時(shí)間為計(jì)算時(shí)間為O(O(n nloglog2 2n n) )。因此。因此, , 堆排序的時(shí)間復(fù)雜性堆排序的時(shí)間復(fù)雜性為為O(O(n nloglog2 2n n) )。o 該算法的附加存儲(chǔ)主要是在第二個(gè)該算法的附加存儲(chǔ)主要是在第二個(gè)forfor循環(huán)中用來(lái)執(zhí)行循環(huán)中用來(lái)執(zhí)行對(duì)象交換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該對(duì)象交換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間算法的空間復(fù)雜性復(fù)雜性為為O(1)O(1)。o 堆排序是一個(gè)堆排序是一個(gè)不穩(wěn)定不穩(wěn)定的排序方法。的排序方法。Void HeapSort(RECORDNODE a,intVoid HeapSort(RECORD

57、NODE a,int n) n)intint i; i;for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n/2;i=1;i-) Sieve(a,i,n);for(i=n;i=2;i-)for(i=n;i=2;i-)a0=a1; a1=ai;ai=a0;a0=a1; a1=ai;ai=a0;Sieve(a,1,i-1);Sieve(a,1,i-1);1.1.從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，

58、稱為稱為. 希爾排序希爾排序 . 冒泡排序冒泡排序 . 插入排序插入排序 . 選擇排序選擇排序2從未排序序列中挑選元素，并將其依次插入已排序序列從未排序序列中挑選元素，并將其依次插入已排序序列（初始時(shí)為空）的一端的方法，稱為（初始時(shí)為空）的一端的方法，稱為. 希爾排序希爾排序 . 歸并排序歸并排序 . 插入排序插入排序 . 選擇排序選擇排序課堂練習(xí)：課堂練習(xí)：五、交換排序o 交換排序交換排序是根據(jù)序列中兩個(gè)結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果，來(lái)對(duì)換是根據(jù)序列中兩個(gè)結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果，來(lái)對(duì)換在序列中的位置。在序列中的位置?；舅枷牖舅枷胧莾蓛杀容^待排序?qū)ο蟮呐判虼a是兩兩比較待排序?qū)ο蟮呐判虼a, ,如發(fā)生逆

59、序如發(fā)生逆序( (即排列順序與排序后的次序正好相反即排列順序與排序后的次序正好相反) )，則交換，則交換之。直到所有對(duì)象都排好序?yàn)橹?。之。直到所有?duì)象都排好序?yàn)橹?。o 算法的特點(diǎn)算法的特點(diǎn)是將關(guān)鍵字較大的結(jié)點(diǎn)向序列的尾部移動(dòng)，關(guān)鍵是將關(guān)鍵字較大的結(jié)點(diǎn)向序列的尾部移動(dòng)，關(guān)鍵字較小的結(jié)點(diǎn)向序列的前部移動(dòng)字較小的結(jié)點(diǎn)向序列的前部移動(dòng)五、交換排序1.1.冒泡排序冒泡排序1 1）過(guò)程：對(duì)無(wú)序表進(jìn)行掃描，當(dāng)發(fā)現(xiàn)相鄰兩個(gè)記錄關(guān)鍵字逆序時(shí)就進(jìn)）過(guò)程：對(duì)無(wú)序表進(jìn)行掃描，當(dāng)發(fā)現(xiàn)相鄰兩個(gè)記錄關(guān)鍵字逆序時(shí)就進(jìn)行交換，第一次掃描后就將最小關(guān)鍵字記錄像氣泡一樣逐漸上浮行交換，第一次掃描后就將最小關(guān)鍵字記錄像氣泡一樣逐漸上

60、浮頂部。然后對(duì)剩下的記錄再進(jìn)行掃描，直到某次掃描時(shí)不發(fā)生交頂部。然后對(duì)剩下的記錄再進(jìn)行掃描，直到某次掃描時(shí)不發(fā)生交換，則排序完成換，則排序完成。2)2)算法算法void BubbleSort(RECORDNODE a,intvoid BubbleSort(RECORDNODE a,int n) n)/ /* *使用冒泡排序算法，對(duì)記錄數(shù)組使用冒泡排序算法，對(duì)記錄數(shù)組a1:na1:n排序排序* */ /int i,j;intint i,j;int exchange = 1; exchange = 1; for(i=1;in & exchange;i+)for(i=1;ii;j-)for(j=n;ji;j-)if(aj-1.keyaj.key)if(aj-1.keyaj.ke