數(shù)據(jù)結(jié)構(gòu)課件第十章2

1、110.1 10.1 概述概述10.2 10.2 插入排序插入排序10.3 10.3 交換排序交換排序10.4 10.4 選擇排序選擇排序10.5 10.5 歸并排序歸并排序10.6 10.6 基數(shù)排序基數(shù)排序210.2 10.2 插入排序插入排序插入排序有多種具體實現(xiàn)算法：插入排序有多種具體實現(xiàn)算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3）2-路插入排序路插入排序 4) 表插入排序表插入排序 5) 希爾排序希爾排序小改進小改進大改進大改進3課堂練習：課堂練習： 以關(guān)鍵字序列（以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，4

2、38）為例，分別寫出執(zhí)行以下算法的）為例，分別寫出執(zhí)行以下算法的各趟各趟排排序結(jié)束時，關(guān)鍵字序列的狀態(tài)，并說明這些排序方法中，序結(jié)束時，關(guān)鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？ 直接插入排序直接插入排序 希爾排序（取希爾排序（取dk=5,3,1）答：答：顯然，直接插入排序方法易于在鏈表上實現(xiàn)；但希爾排顯然，直接插入排序方法易于在鏈表上實現(xiàn)；但希爾排序方法因為是按增量選擇記錄，不易于在鏈表上實現(xiàn)。序方法因為是按增量選擇記錄，不易于在鏈表上實現(xiàn)。 兩種排序方法的中間狀態(tài)分別描述如后：兩種排序方法的中

3、間狀態(tài)分別描述如后：4原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438 256256，301301 ，751751，129129，937937，863863，742742，694694，076076，438438 256256，301301，751751 ，129129，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751 ，937937，863863，742742，694694，076076，43

4、8438 129129，256256，301301，751751，937937 ，863863，742742，694694，076076，438438 129129，256256，301301，751751，863863，937937 ，742742，694694，076076，438438 129129，256256，301301，742742，751751，863863，937937 ，694694，076076，438438 129129，256256，301301，694694，742742，751751，863863，937937 ，076076，438438 076076，1291

5、29，256256，301301，694694，742742，751751，863863，937937 ，438438 076076，129129，256256，301301，438438，694694，742742，751751，863863，937937 第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟5原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，74

6、2742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，93793

7、7第第1趟趟dk=5dk=5第第2趟趟dk=3dk=3第第3趟趟dk=1dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，7517

8、51，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，1

9、29129，256256，301301，438438，694694，742742，751751，863863，9379376void ShellSort(SqList &L，int dlta ，int t) /按增量序列按增量序列dlta0t-1對順序表對順序表L作作Shell排序排序 for(k=0；kt；+k) ShellSort(L，dltak)； / ShellSort時間效率：時間效率：空間效率：空間效率：因為僅占用因為僅占用1 1個緩沖單元個緩沖單元( (與算法有關(guān)）與算法有關(guān)）算法的穩(wěn)定性：算法的穩(wěn)定性：因為因為4949* *排序后卻到了排序后卻到了4949的前面的前面參

10、見教材參見教材P272P272由經(jīng)驗公式得到由經(jīng)驗公式得到dkdk值依次裝在值依次裝在dltadltat t 中中/增量為增量為dltak的一趟插入排序的一趟插入排序7理解難點：理解難點：整理動作是二合一的，整理動作是二合一的， r0 仍是每個仍是每個dk子集的哨兵，用于子集的徹子集的哨兵，用于子集的徹底排序！底排序！ for(i=dk+1；i=L.length； + i) if(ri.key 0&(r0.key0&(r0.keyrj.key); j-=dk) rj+dk=rj；rj+dk=r0； 5 7 45 7 4 i=1 i+dk=6 i+2dk=11 i=1 i+dk=

11、6 i+2dk=11 如果不用如果不用forfor循環(huán)，比較的結(jié)果是循環(huán)，比較的結(jié)果是 5 5，4 4，7 7 只有執(zhí)行只有執(zhí)行forfor循環(huán)后，比較結(jié)果才會是循環(huán)后，比較結(jié)果才會是 4 4，5 5，7 7for(i=dk+1；i=L.length； + i) if(ri.key ri-dk.key) r0=ri；大者后移大者后移空間效率與算法設(shè)計有關(guān)空間效率與算法設(shè)計有關(guān)910.3 10.3 交換排序交換排序交換排序的主要算法有：交換排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序10 1) 基本思路：基本思路：每趟不斷將記錄兩兩比較，并按每趟不斷將記錄兩兩比較，并按“前

12、小后大前小后大”（或（或“前大后小前大后小”）規(guī)則交換。）規(guī)則交換。優(yōu)點：優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能還能同時部分理順其他元素同時部分理順其他元素；一旦下趟沒有交換發(fā)；一旦下趟沒有交換發(fā)生，還可以生，還可以提前結(jié)束排序提前結(jié)束排序。前提：前提：順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，08），請寫出），請寫出冒泡排序的具體實現(xiàn)過程。冒泡排序的具體實現(xiàn)過程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25

13、*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初態(tài)：初態(tài)：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟11冒泡排序的算法分析冒泡排序的算法分析最好情況：最好情況：初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做 n- -1 次關(guān)鍵碼比較，不移動對象。次關(guān)鍵碼比較，不移動對象。最壞情形：最壞情形：初始排列逆序，初始排列逆序，算法要執(zhí)行算法要執(zhí)行n-1 1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次關(guān)鍵碼比較，執(zhí)行了次關(guān)鍵碼比較，執(zhí)行了n-i 次對象交換。次對象交

14、換。此時的比較總次數(shù)此時的比較總次數(shù)KCN和記錄移動次數(shù)和記錄移動次數(shù)RMN為：為：11111233121nininninRMNnninKCN)()()()(121314( )，設(shè)以首元素為樞軸中心設(shè)以首元素為樞軸中心例例1：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，08），請），請寫出快速排序的算法步驟。寫出快速排序的算法步驟。21， 25， 49， 25*，16， 08初態(tài)：初態(tài)：第第1趟：趟：第第2趟：趟：第第3趟：趟：08，16，21，25， 25*，(49)2116，08，( )25，25*，49(08)，16，21，25，(25*，49)15pivotkey=21

15、pivotkey=21( 08 ，16 ） 21 （ 25* ， 49， 25 ）例例2：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，08），計算），計算機如何實現(xiàn)快速排序算法的某機如何實現(xiàn)快速排序算法的某一趟一趟過程？過程？ri0123456初態(tài)初態(tài)21254925*1608第第1趟趟highhighlowlow2125*32108251649設(shè)計技巧：設(shè)計技巧：交替交替/振蕩式逼近振蕩式逼近16例例3：以關(guān)鍵字序列（以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的）為例，寫出執(zhí)行快速算法的各趟各趟排序排序

16、結(jié)束時，關(guān)鍵字序列的狀態(tài)。結(jié)束時，關(guān)鍵字序列的狀態(tài)。原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076076，438438，129129，937937，863863，742742，694694，301301，438438意即模擬算法實現(xiàn)步驟意即模擬算法實現(xiàn)步驟076076301301129129751751，129129，4384

17、38，301301，694694，742742，694694，863863，937937，301301，694694，742742，937937，301301，301301，694694，742742，937937，742742，( (存每層存每層lowlow，highhigh和和pivot)pivot)17討論討論1 1：如何編程實現(xiàn)？：如何編程實現(xiàn)？分析：分析：每一趟子表的形成是采用從兩頭向中間交替式逼近法；每一趟子表的形成是采用從兩頭向中間交替式逼近法；由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。見教材見教材P275int

18、int (SqList &L,int(SqList &L,int low low,int,int high high) ) /一趟快排一趟快排/交換子表交換子表 rlowhighrlowhigh的記錄，使支點（樞軸）記錄到位，并的記錄，使支點（樞軸）記錄到位，并返回其位置返回其位置。返回時，在支點之前的記錄均不大于它，支點之后的記錄均不小于它。返回時，在支點之前的記錄均不大于它，支點之后的記錄均不小于它。 r0=r0=rlowrlow; ; /以子表的首記錄作為支點記錄，放入以子表的首記錄作為支點記錄，放入r0r0單元單元（續(xù)下頁）（續(xù)下頁）一趟快速排序算法一趟快速排序算法（針

19、對一個子表的操作）（針對一個子表的操作）18pivotkey=pivotkey=rlow.keyrlow.key; ; /取支點的關(guān)鍵碼存入取支點的關(guān)鍵碼存入pivotkeypivotkey變量變量while(low high)while(low high) /從表的兩端交替地向中間掃描從表的兩端交替地向中間掃描while(while(lowhighlow=pivotkeyrhigh.key=pivotkey ) ) rlow=rhigh; rlow=rhigh; /比支點小的記錄交換到低端；比支點小的記錄交換到低端；while(while(lowhighlowhigh & &

20、 rlow.key=pivotkeyrlow.key=pivotkey) ) rhigh=rlow; rhigh=rlow; /比支點大的記錄交換到高端；比支點大的記錄交換到高端；rlow=r0; rlow=r0; /支點記錄到位；支點記錄到位；return return lowlow; ; /返回支點記錄所在位置。返回支點記錄所在位置。 /19從高端從高端掃描掃描尋找小于尋找小于pivot的元素的元素從低端從低端掃描掃描尋找大于尋找大于pivot的元素的元素r0=rlow; pivot=rlow.key;low highlow =pivot- high;rlow = rhigh;low hi

21、gh &rlow.key=pivot- low;rhigh = rlow;rlow = r0;return low;20if ( low 1/對順序表對順序表L中的子序列中的子序列r lowhigh 作快速排序作快速排序/一趟快排，將一趟快排，將r 一分為二一分為二/在左子區(qū)間進行遞歸快排，直到長度為在左子區(qū)間進行遞歸快排，直到長度為1/在右子區(qū)間進行遞歸快排，直到長度為在右子區(qū)間進行遞歸快排，直到長度為1是局部變量是局部變量 1, L.length 21設(shè)每個子表的支點都在中間（比較均衡），則：設(shè)每個子表的支點都在中間（比較均衡），則：第第1 1趟比較，可以確定趟比較，可以確定1 1

22、個元素的位置；個元素的位置；第第2 2趟比較（趟比較（2 2個子表），可以再確定個子表），可以再確定2 2個元素的位置；個元素的位置；第第3 3趟比較（趟比較（4 4個子表），可以再確定個子表），可以再確定4 4個元素的位置；個元素的位置；第第4 4趟比較（趟比較（8 8個子表），可以再確定個子表），可以再確定8 8個元素的位置；個元素的位置； 只需只需 loglog2 2n n 1 1趟便可排好序。趟便可排好序。而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程時使用了交替逼近技巧，更進一步減少了移動次數(shù)，所以速度時使用了交替逼近技巧，更

23、進一步減少了移動次數(shù)，所以速度特別快。特別快。教材教材P276P276有證明：快速排序的平均排序效率為有證明：快速排序的平均排序效率為O(nlogO(nlog2 2n)n)；但最壞情況下但最壞情況下( (例如天然有序例如天然有序) )仍為仍為O(nO(n2 2),),改進措施見改進措施見P277P277。22選擇排序有多種具體實現(xiàn)算法：選擇排序有多種具體實現(xiàn)算法： 1) 簡單選擇排序簡單選擇排序 2) 錦標賽排序錦標賽排序 3) 堆排序堆排序2324例：例：關(guān)鍵字序列關(guān)鍵字序列T= （21，25，49，25*，16，08），請），請給出簡單選擇排序的具體實現(xiàn)過程。給出簡單選擇排序的具體實現(xiàn)過程

24、。原始序列：原始序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49時間效率：時間效率： 雖移動次數(shù)較少，但比較次數(shù)仍多。雖移動次數(shù)較少，但比較次數(shù)仍多。 空間效率：空間效率：沒有附加單元（僅用到?jīng)]有附加單元（僅用到1 1個個temp)temp)算法的穩(wěn)定性：算法的穩(wěn)定性：因為排序時，因為排序時，2525* *到了到了2525的前面。的前面。最小值最小值 0808 與

25、與r1r1交換位置交換位置25（亦可參見教材（亦可參見教材P276P276）Void SelectSort(SqList &L ) for (i=1; i0; - - i ) HeapAdjust(r, i, length ); HeapSortHeapAdjust是針對結(jié)點是針對結(jié)點 i 的堆調(diào)整函數(shù)，的堆調(diào)整函數(shù)，其含義是：其含義是：從結(jié)點從結(jié)點i i開始到開始到堆尾堆尾為止，自上向下比較，如果子女為止，自上向下比較，如果子女的值大于雙親結(jié)點的值，則互相交換，即把局部調(diào)整的值大于雙親結(jié)點的值，則互相交換，即把局部調(diào)整為大根堆。為大根堆。參見教材參見教材P281-28239while

26、(child=m) /檢查是否到達當前堆尾，未到尾則整理檢查是否到達當前堆尾，未到尾則整理 if ( childm & rchild.key=rchild.key ) breack; /根大則不必調(diào)整，函數(shù)結(jié)束根大則不必調(diào)整，函數(shù)結(jié)束 else rcurrent=rchild; /否則子女中的大者上移否則子女中的大者上移 current= child; child=2* child; /將根下降到子女位置將根下降到子女位置 / while rcurrent=temp; /直到自下而上都滿足堆定義，再安置直到自下而上都滿足堆定義，再安置入口入口結(jié)點結(jié)點 / HeapAdjust針對結(jié)點針

27、對結(jié)點 i 的堆調(diào)整函數(shù)的堆調(diào)整函數(shù)HeapAdjust 表述如下：表述如下：HeapAdjust(r, i, m )current=i; temp=ri; child=2*i; /temp暫存暫存ri值，值，child是其左孩子是其左孩子 從結(jié)點從結(jié)點i i開始到開始到當前堆尾當前堆尾m m為止，自上向下比較，如果子女的為止，自上向下比較，如果子女的值大于雙親結(jié)點的值，則互相交換，即把局部調(diào)整為大根堆。值大于雙親結(jié)點的值，則互相交換，即把局部調(diào)整為大根堆。40H.rim中除中除ri外，其他都具有堆特征。外，其他都具有堆特征?，F(xiàn)調(diào)整現(xiàn)調(diào)整ri的值的值 ，使，使H.rim為堆。為堆。41421234561365424312345613654244123456136542451234561365424612345613654247void HeapSort (HeapType &H ) /對順序表對順序表H進行堆排序進行堆排序 for ( i = H.length / 2; i 0; - - i ) HeapAdjust(H