《數(shù)據(jù)結(jié)構(gòu)課件排序ppt.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課件排序ppt.ppt（69頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確第第10章章 內(nèi)部排序內(nèi)部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 選擇排序選擇排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種內(nèi)部排序方法的比較討論各種內(nèi)部排序方法的比較討論1在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確10.1概述概述排序排序 是將數(shù)據(jù)元素的一個(gè)任意序列，重新排列成一是將數(shù)據(jù)元素的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。個(gè)按關(guān)鍵字有序

2、的序列。排序的一個(gè)確切定義：排序的一個(gè)確切定義：假設(shè)含假設(shè)含n個(gè)記錄的序列為個(gè)記錄的序列為 R1,R2,R3,Rn其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為K1,K2,Kn需確定需確定1,2,n的一種排列的一種排列P1,P2,P3,Pn,使其相應(yīng)的關(guān)使其相應(yīng)的關(guān)鍵字滿足如下的遞增鍵字滿足如下的遞增(或遞減或遞減)關(guān)系關(guān)系:Kp1Kp2Kpn即使序列即使序列R1,R2,R3,Rn成為一個(gè)按關(guān)鍵字有序的序列成為一個(gè)按關(guān)鍵字有序的序列:Rp1,Rp2,Rp3,Rpn這種操作稱為排序這種操作稱為排序.2在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也

3、很明確穩(wěn)定排序方法穩(wěn)定排序方法假設(shè)假設(shè)Ki=Kj(1=i,j=n,ij),且在排序前的序且在排序前的序列中列中Ri領(lǐng)先于領(lǐng)先于Rj，若在排序后的序列中，若在排序后的序列中Ri仍仍領(lǐng)先領(lǐng)先Rj，則稱所用的排序方法是，則稱所用的排序方法是穩(wěn)定的穩(wěn)定的。不穩(wěn)定排序方法不穩(wěn)定排序方法假設(shè)假設(shè)Ki=Kj(1=i,j=n,ij),且在排序前的序列且在排序前的序列中中Ri領(lǐng)先于領(lǐng)先于Rj，若在排序后的序列中，若在排序后的序列中Rj領(lǐng)先領(lǐng)先Ri，則稱所用的排序方法是，則稱所用的排序方法是不穩(wěn)定的不穩(wěn)定的。例：例：姓名姓名年齡年齡體重體重1李由李由57622王天王天54763七明七明24754張強(qiáng)張強(qiáng)24725

4、陳華陳華2453按某種按某種穩(wěn)定穩(wěn)定方法對(duì)年齡方法對(duì)年齡關(guān)鍵字進(jìn)行關(guān)鍵字進(jìn)行排序排序姓名姓名年齡年齡體重體重3七明七明24754張強(qiáng)張強(qiáng)24725陳華陳華24532王天王天54761李由李由57623在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確姓名姓名年齡年齡體重體重1李由李由57622王天王天54763七明七明24754張強(qiáng)張強(qiáng)24725陳華陳華2453按某種按某種不穩(wěn)不穩(wěn)定定方法對(duì)年方法對(duì)年齡關(guān)鍵字進(jìn)齡關(guān)鍵字進(jìn)行排序行排序姓名姓名年齡年齡體重體重4張強(qiáng)張強(qiáng)24723七明七明24755陳華陳華24532王天王天54761李由李由

5、5762待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行的排序過程；行的排序過程；內(nèi)部排序內(nèi)部排序待排序記錄的數(shù)量很大，以致內(nèi)存一次不待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對(duì)外能容納全部記錄，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序過程；存進(jìn)行訪問的排序過程；外部排序外部排序4在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確按排序過程中依據(jù)的不同原則對(duì)內(nèi)排方法分類：按排序過程中依據(jù)的不同原則對(duì)內(nèi)排方法分類：（1）插入排序）插入排序（2）交換排序）交換排序（3）選擇排序）選擇排序（4）

6、歸并排序）歸并排序（5）基數(shù)排序）基數(shù)排序按內(nèi)排過程中所需的工作量分類：按內(nèi)排過程中所需的工作量分類：（1）簡單的排序方法，其時(shí)間復(fù)雜度為）簡單的排序方法，其時(shí)間復(fù)雜度為O(nn)（2）先進(jìn)的排序方法，其時(shí)間復(fù)雜度為）先進(jìn)的排序方法，其時(shí)間復(fù)雜度為O(nlogn);（3）基數(shù)排序，其時(shí)間復(fù)雜度為）基數(shù)排序，其時(shí)間復(fù)雜度為O(dn)排序算法的兩種基本操作：排序算法的兩種基本操作：（1）比較比較兩個(gè)關(guān)鍵字的大小；兩個(gè)關(guān)鍵字的大??；（2）將記錄從一個(gè)位置）將記錄從一個(gè)位置移移至另一個(gè)位置；至另一個(gè)位置；5在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的

7、問題也很明確待排序的記錄序列可有三種存儲(chǔ)方式：待排序的記錄序列可有三種存儲(chǔ)方式：（1）待排序的記錄存放在地址連續(xù)的一組存儲(chǔ)單元上。）待排序的記錄存放在地址連續(xù)的一組存儲(chǔ)單元上。（2）待排序的記錄存放在靜態(tài)鏈表中。）待排序的記錄存放在靜態(tài)鏈表中。（3）待排序的記錄本身存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元）待排序的記錄本身存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元 內(nèi)內(nèi),同時(shí)另設(shè)一個(gè)指示各個(gè)記錄存儲(chǔ)位置的地址向量。同時(shí)另設(shè)一個(gè)指示各個(gè)記錄存儲(chǔ)位置的地址向量。待排序記錄的數(shù)據(jù)類型設(shè)為：待排序記錄的數(shù)據(jù)類型設(shè)為：P2646在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也

8、很明確10.2插入排序插入排序插入排序插入排序直接插入排序直接插入排序折半插入排序折半插入排序2-路插入排序路插入排序表插入排序表插入排序希爾排序希爾排序10.2.1直接插入排序直接插入排序直接插入排序的基本操作是將一個(gè)記錄插入到已排好序的直接插入排序的基本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。的有序表。例例:有一組待排序的記錄的關(guān)鍵字初始排列如下有一組待排序的記錄的關(guān)鍵字初始排列如下:(49,38,65,97,76,13,27,49)用用L(sqlist L)的的L.r1.key.L.r8.key依次存儲(chǔ)依次存儲(chǔ)L

9、.r1.key.L.r8.key是是遞增有序的遞增有序的直接插直接插入排序入排序7在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確直接插入排序的過程直接插入排序的過程:初始關(guān)鍵字初始關(guān)鍵字r0 r1 r2 r3 r4 r5 r6 r7 r8 49 38 65 97 76 13 27 49第一趟插入第一趟插入384965 97 76 13 27 49第二趟插入第二趟插入38496597 76 13 27 49第三趟插入第三趟插入38 49 65 97 76 13 27 49第四趟插入第四趟插入38 49 65 76 9713 27 49

10、第五趟插入第五趟插入13 38 49 65 76 9727 49第六趟插入第六趟插入13 27 38 49 65 76 9749第七趟插入第七趟插入13 27 38 49 49 65 76 97i=2i=3i=4i=5i=6i=7i=88在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確直接插入排序算法分析直接插入排序算法分析:有有n個(gè)記錄待排序個(gè)記錄待排序,需進(jìn)行需進(jìn)行2.n共共n-1趟插入趟插入;一級(jí)算一級(jí)算法：法：Void insertsort(sqlist&L)for (i=2;i=L.length;+i)第第i趟插入；趟插入；

11、第第i趟插入完成的功能趟插入完成的功能:在含有在含有i-1個(gè)記錄的有序序列個(gè)記錄的有序序列r1.i-1 中插入一個(gè)記錄中插入一個(gè)記錄ri,插入后變成含插入后變成含 有有i個(gè)記錄的有序序列個(gè)記錄的有序序列r1.i。9在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確第第i趟插入的算法趟插入的算法二級(jí)算二級(jí)算法：法：例：第例：第i=7趟插入：趟插入：if (LT(L.ri.key,L.ri-1.key)L.ri插入到插入到 L.r1.L.ri-1中中 L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,

12、L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;13 38 49 65 76 97 27 491 2 3 4 5 6 7 810在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確三級(jí)算三級(jí)算法：法：Void insertsort(sqlist&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;11

13、在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確直接插入排序的性能分析直接插入排序的性能分析:(1)空間空間:只需一個(gè)記錄的輔助空間只需一個(gè)記錄的輔助空間r0.(2)時(shí)間時(shí)間:基本運(yùn)算基本運(yùn)算:比較和移動(dòng)記錄比較和移動(dòng)記錄;比較和移動(dòng)記錄的次數(shù)與關(guān)鍵字的初始序列有關(guān)比較和移動(dòng)記錄的次數(shù)與關(guān)鍵字的初始序列有關(guān):(1)待排序序列關(guān)鍵字正序排序待排序序列關(guān)鍵字正序排序:關(guān)鍵字比較次數(shù)關(guān)鍵字比較次數(shù):n-1 移動(dòng)記錄的次數(shù)移動(dòng)記錄的次數(shù):0(2)待排序序列關(guān)鍵字逆序排序待排序序列關(guān)鍵字逆序排序:關(guān)鍵字比較次數(shù)關(guān)鍵字比較次數(shù):2+3+n=(n+

14、2)(n-1)/2 移動(dòng)記錄的次數(shù)移動(dòng)記錄的次數(shù):3+4+5+(n+1)=(n+4)(n-1)/2(3)待排序序列關(guān)鍵字隨機(jī)排序待排序序列關(guān)鍵字隨機(jī)排序:關(guān)鍵字比較次數(shù)關(guān)鍵字比較次數(shù):(n-1)(n+4)/4 移動(dòng)記錄的次數(shù)移動(dòng)記錄的次數(shù):(n+4)(n-1)/4直接插入排序算直接插入排序算法的時(shí)間復(fù)雜度法的時(shí)間復(fù)雜度為為O(nn)12在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確10.2.2 其它插入排序其它插入排序折半插入排序折半插入排序:把直接插入算法中對(duì)插入位置的搜索從把直接插入算法中對(duì)插入位置的搜索從順序搜索順序搜索改進(jìn)為

15、改進(jìn)為折半搜索折半搜索.Void Binsertsort(sqlist&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;P267算法算法10.213在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確折半插入排序的性能分析折半插入排序的性能分析:(1)空間空間:只需一個(gè)記錄的輔助空間只需一個(gè)記錄的輔助空間r0;(2)時(shí)間時(shí)

16、間:基本運(yùn)算基本運(yùn)算:比較和移動(dòng)記錄比較和移動(dòng)記錄;折半插入排序算法的時(shí)間復(fù)雜度為折半插入排序算法的時(shí)間復(fù)雜度為O(nn)14在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確2-路插入排序路插入排序?yàn)闇p少排序過程中移動(dòng)記錄的次數(shù)，在折半插入排序的為減少排序過程中移動(dòng)記錄的次數(shù)，在折半插入排序的基礎(chǔ)上加以改進(jìn)：基礎(chǔ)上加以改進(jìn)：例例:有一組待排序的記錄的關(guān)鍵字初始排列如下有一組待排序的記錄的關(guān)鍵字初始排列如下:(49,38,65,97,76,13,27,49)另設(shè)一個(gè)和另設(shè)一個(gè)和r同類型的數(shù)組同類型的數(shù)組d,首先將首先將r1賦值給賦值給d

17、1,并將并將d1看成看成是在排好序的序列中處于中間位置的記錄是在排好序的序列中處于中間位置的記錄,然后從然后從r中第中第2個(gè)記錄起個(gè)記錄起依次插入到依次插入到d1之前或之后的有序序列中之前或之后的有序序列中.先將待插記錄的關(guān)鍵字和先將待插記錄的關(guān)鍵字和d1的關(guān)鍵字進(jìn)行比較的關(guān)鍵字進(jìn)行比較.若若ri.keyd1.key,則將則將ri插入到插入到d1之前之前的有序表中的有序表中,反之反之,則將則將ri插入到插入到d1之后的有序表中之后的有序表中.算法實(shí)現(xiàn)的關(guān)鍵設(shè)計(jì)算法實(shí)現(xiàn)的關(guān)鍵設(shè)計(jì):將將d看成是一個(gè)循環(huán)數(shù)組看成是一個(gè)循環(huán)數(shù)組,并設(shè)兩個(gè)指針并設(shè)兩個(gè)指針first和和final分別指示排序過分別指示排

18、序過程中得到的有序序列中的第一個(gè)記錄和最后一個(gè)記錄在程中得到的有序序列中的第一個(gè)記錄和最后一個(gè)記錄在d中的位置中的位置.15在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確 d1 d2 d3 d4 d5 d6 d7 d8 初始關(guān)鍵字初始關(guān)鍵字49 38 65 97 76 13 27 49i=1:49first finali=2:4938firstfinali=3:493865finalfirsti=4:49386597finalfirsti=5:4938657697finalfirsti=6:493865769713finalfirs

19、ti=7:49386576971327finalfirsti=8:4949657697132738finalfirst16在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確2-路插入排序的性能分析路插入排序的性能分析:(1)空間空間:(2)時(shí)間時(shí)間:基本運(yùn)算基本運(yùn)算:比較和移動(dòng)記錄比較和移動(dòng)記錄;2-路插入排序算法的時(shí)間復(fù)雜度為路插入排序算法的時(shí)間復(fù)雜度為O(nn)17在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確10.2.3希爾排序希爾排序從直接插入排序從直接插入排序待排序

20、序列基本有序可提高效率待排序序列基本有序可提高效率待排序序列的記錄數(shù)待排序序列的記錄數(shù)n很小時(shí)可提高效率很小時(shí)可提高效率希爾排序的基本思想希爾排序的基本思想:先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序直接插入排序,待整個(gè)序列中的記錄待整個(gè)序列中的記錄“基本有序基本有序”時(shí)時(shí),再對(duì)再對(duì)全全體記錄進(jìn)行一次直接插入排序體記錄進(jìn)行一次直接插入排序.例例:有一組待排序的記錄的關(guān)鍵字初始排列如下有一組待排序的記錄的關(guān)鍵字初始排列如下:(49,38,65,97,76,13,27,49)18在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的

21、設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確初始關(guān)鍵字初始關(guān)鍵字r0 r1 r2 r3 r4 r5 r6 r7 r8 49 38 65 97 76 13 27 49第一趟排序后第一趟排序后:(d1=3)27 38 13 49 49 65 97 76第二趟排序后第二趟排序后:(d2=2)13 27 49 97第三趟排序后第三趟排序后:(d3=1)13 27 38 49 49 65 76 97 38 49 65 7619在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確希爾排序算法的實(shí)現(xiàn)希爾排序算法的實(shí)現(xiàn):Void shellsort

22、(sqlist&L,int dlta,int t)for (i=0;it;+i)以以dltai為增量的一趟排序；為增量的一趟排序；Shellinsert（sqlist&L,dltai);Void insertsort(sqlist&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;(1)記錄的增量記錄的增量為為dk;(2)r0不是哨不是哨兵。兵。j=0，插，插入位置已找到。入位置

23、已找到。P272算法算法10.420在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確希爾排序的性能分析：希爾排序的性能分析：(1)空間空間:只需一個(gè)記錄的輔助空間只需一個(gè)記錄的輔助空間r0;(2)時(shí)間時(shí)間:基本運(yùn)算基本運(yùn)算:比較和移動(dòng)記錄比較和移動(dòng)記錄;時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：O（n3/2）增量的取法應(yīng)注意：使增量序列中的值沒有除增量的取法應(yīng)注意：使增量序列中的值沒有除1之外的公之外的公 因子，并且最后一個(gè)增量值必須為因子，并且最后一個(gè)增量值必須為1。21在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度

24、，由淺入深，所提出的問題也很明確10.3快速排序快速排序起泡排序的基本思想起泡排序的基本思想:首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。直至第個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。直至第n-1個(gè)記錄和第個(gè)記錄和第n個(gè)個(gè)記錄的關(guān)鍵字進(jìn)行過比較為止。記錄的關(guān)鍵字進(jìn)行過比較為止。然后進(jìn)行第二趟起泡排序，對(duì)前然后進(jìn)行第二趟起泡排序，對(duì)前n-1個(gè)記錄進(jìn)行同樣操作。個(gè)記錄進(jìn)行同樣操作。結(jié)束的條件結(jié)束的條件:(1)趟數(shù)為趟數(shù)為n-1;(2)直

25、到在某趟排序過程中沒有直到在某趟排序過程中沒有進(jìn)行過交換進(jìn)行過交換記錄的操作為止。記錄的操作為止。22在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確例例:有一組待排序的記錄的關(guān)鍵字初始排列如下有一組待排序的記錄的關(guān)鍵字初始排列如下:(49,38,65,97,76,13,27,49)第一趟第一趟:4938659776132749384965977613274938496597761327493849659776132749384965769713274938496576139727493849657613279749384965761

26、3274997第一趟進(jìn)行第一趟進(jìn)行7次比較次比較23在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確49386597761327493849657613274997初初始始關(guān)關(guān)鍵鍵字字第第一一趟趟排排序序后后38496513274976第第二二趟趟排排序序后后384913274965第第三三趟趟排排序序后后3813274949第第四四趟趟排排序序后后13273849第第五五趟趟排排序序后后132738第第六六趟趟排排序序后后1327第第七七趟趟排排序序后后整整個(gè)個(gè)排排序序過過程程24在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而

27、問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確起泡排序算法的性能分析起泡排序算法的性能分析:(1)空間空間:只需一個(gè)記錄的輔助空間只需一個(gè)記錄的輔助空間.(2)時(shí)間時(shí)間:基本運(yùn)算基本運(yùn)算:比較和移動(dòng)記錄比較和移動(dòng)記錄;比較和移動(dòng)記錄的次數(shù)與關(guān)鍵字的初始序列有關(guān)比較和移動(dòng)記錄的次數(shù)與關(guān)鍵字的初始序列有關(guān):(1)待排序序列關(guān)鍵字正序排序待排序序列關(guān)鍵字正序排序:關(guān)鍵字比較次數(shù)關(guān)鍵字比較次數(shù):n-1 移動(dòng)記錄的次數(shù)移動(dòng)記錄的次數(shù):0(2)待排序序列關(guān)鍵字逆序排序待排序序列關(guān)鍵字逆序排序:關(guān)鍵字比較次數(shù)關(guān)鍵字比較次數(shù):(n-1)+(n-2)+1=n(n-1)/2 移動(dòng)記錄的次數(shù)移動(dòng)記錄的次數(shù)

28、:3n(n-1)/2(3)待排序序列關(guān)鍵字隨機(jī)排序待排序序列關(guān)鍵字隨機(jī)排序:關(guān)鍵字比較次數(shù)關(guān)鍵字比較次數(shù):(n-1)(n+2)/4 移動(dòng)記錄的次數(shù)移動(dòng)記錄的次數(shù):3n(n-1)/4起泡排序算法的起泡排序算法的時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(nn)25在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確快速排序的基本思想快速排序的基本思想:通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可

29、分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。算法實(shí)現(xiàn)分析：算法實(shí)現(xiàn)分析：（1）假設(shè)待排序的序列為）假設(shè)待排序的序列為L.rs,L.rs+1,L.rt；（2）任意選取一個(gè)記錄作為樞軸，然后重新排列其余記錄，將所）任意選取一個(gè)記錄作為樞軸，然后重新排列其余記錄，將所 有關(guān)鍵字較它小的記錄都安置在它的位置之前，所有關(guān)鍵字有關(guān)鍵字較它小的記錄都安置在它的位置之前，所有關(guān)鍵字 較它大的記錄都安置在它的位置之后。較它大的記錄都安置在它的位置之后。由此可由此可以該樞軸記錄所在的位置以該樞軸記錄所在的位置i作分界線作分界線，將序列分割成兩，將序列分割成兩 個(gè)子序列個(gè)

30、子序列:L.rs,L.rs+1,L.ri-1和和 L.ri+1,L.ri+2,L.rt 這個(gè)過程稱作一趟快速排序。這個(gè)過程稱作一趟快速排序。（3）對(duì)子序列）對(duì)子序列L.rs,L.rs+1,L.ri-1和和L.ri+1,L.ri+2,L.rt 分別重復(fù)（分別重復(fù)（1）、（）、（2）。）。26在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確一趟快速排序的具體做法：一趟快速排序的具體做法：(1)附設(shè)兩個(gè)指針附設(shè)兩個(gè)指針i和和j，它們的初值分別為，它們的初值分別為s和和t，設(shè)樞，設(shè)樞 軸記錄的關(guān)鍵字為軸記錄的關(guān)鍵字為pivotkeyL.rs.

31、key.(2)從從j所指位置起向前搜索找到第一個(gè)關(guān)鍵字所指位置起向前搜索找到第一個(gè)關(guān)鍵字小于小于 pivotkey的記錄和樞軸記錄互相交換，然后從的記錄和樞軸記錄互相交換，然后從i所所 指位置起向后搜索，找到第一個(gè)關(guān)鍵字指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于大于 pivotkey的記錄和樞軸記錄互相交換的記錄和樞軸記錄互相交換;(3)重復(fù)重復(fù)(2)直到直到i=j為止。為止。例例:有一組待排序的記錄的關(guān)鍵字初始排列如下有一組待排序的記錄的關(guān)鍵字初始排列如下:(49,38,65,97,76,13,27,49)27在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深

32、，所提出的問題也很明確第一趟快速排序：第一趟快速排序：初始關(guān)鍵字初始關(guān)鍵字49 38 65 97 76 13 27 49pivotkey=ijj進(jìn)行進(jìn)行1次交換之后次交換之后27 38 65 97 76 13 49 49iji進(jìn)行進(jìn)行2次交換之后次交換之后27 38 49 97 76 13 65 49ijj進(jìn)行進(jìn)行3次交換之后次交換之后27 38 13 97 76 49 65 49iji進(jìn)行進(jìn)行4次交換之后次交換之后27 38 13 49 76 97 65 49ijj完成一趟排序完成一趟排序27 38 13 49 76 97 65 4928在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問

33、題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確Int partition(sqlist&L,int low,int high)pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlowL.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rlowL.rhigh;return low;29在整堂課的教學(xué)中，劉教師總是讓學(xué)生帶著問題來學(xué)習(xí)，而問題的設(shè)置具有一定的梯度，由淺入深，所提出的問題也很明確Int partition(sqlist&L,int low,int high)L.r0=L.rlow;pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlow=L.rhigh;while(lowhigh&