[工學(xué)]數(shù)據(jù)結(jié)構(gòu)ch10 排序ppt課件

1、 王秀章王秀章 2005.82007.4物理系物理系 數(shù)據(jù)結(jié)構(gòu)排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講第十章第十章 排序排序10.1概述概述10.2 插入排序插入排序10.3 交換排序交換排序10.4 選擇排序選擇排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講10.1概述概述一、什么是排序？一、什么是排序？二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序三、內(nèi)部排序的方法三、內(nèi)部排序的方法湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講10.1概述概述排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)展的一種操作，其目的是將一組“無序

2、的記錄序列調(diào)整為“有序的記錄序列。 一、什么是排序？一、什么是排序？例如：將以下關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講普通情況下，假設(shè)含n個(gè)記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進(jìn)展比較，即在它們之間存在著這樣一個(gè)關(guān)系 Kp1Kp2Kpn按此固有關(guān)系將式(1)的記錄序列重新陳列為 Rp1, Rp2, ，Rpn 的操作稱作排序。湖北師范學(xué)院物理

3、系湖北師范學(xué)院物理系王秀章主講王秀章主講二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序 在本章內(nèi)先討論內(nèi)部排序的各種方法，然后引見外部排序的根本過程。假設(shè)整個(gè)排序過程不需求訪問外存便能完成，那么稱此類排序問題為內(nèi)部排序； 反之，假設(shè)參與排序的記錄數(shù)量很大，整個(gè)序列的排序過程不能夠在內(nèi)存中完成，那么稱此類排序問題為外部排序。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講三、內(nèi)部排序的方法三、內(nèi)部排序的方法有序序列區(qū) 無序序列區(qū)內(nèi)部排序的過程是一個(gè)逐漸擴(kuò)展記錄的有序內(nèi)部排序的過程是一個(gè)逐漸擴(kuò)展記錄的有序序列長度的過程。在排序的過程中，參與排序的序列長度的過程。在排序的過程中，參與排序的記錄

4、序列中存在兩個(gè)區(qū)域：有序區(qū)和無序區(qū)。記錄序列中存在兩個(gè)區(qū)域：有序區(qū)和無序區(qū)。使有序區(qū)中記錄的數(shù)目添加一個(gè)或幾個(gè)的操使有序區(qū)中記錄的數(shù)目添加一個(gè)或幾個(gè)的操作稱為一趟排序。作稱為一趟排序。有 序 序 列 區(qū) 無 序 序 列 區(qū)湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講1.1.插入類插入類將無序子序列中的一個(gè)或幾個(gè)記錄將無序子序列中的一個(gè)或幾個(gè)記錄“插入到插入到有序序列中，從而添加記錄的有序子序列的長度；有序序列中，從而添加記錄的有序子序列的長度；逐漸擴(kuò)展記錄有序序列長度的方法大致逐漸擴(kuò)展記錄有序序列長度的方法大致有以下幾類：有以下幾類：2.2.交換類交換類經(jīng)過經(jīng)過“交換無序序列中的記

5、錄從而得到其中交換無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它參與到有序子序關(guān)鍵字最小或最大的記錄，并將它參與到有序子序列中，以此方法添加記錄的有序子序列的長度列中，以此方法添加記錄的有序子序列的長度; ;湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講3.3.選擇類選擇類從記錄的無序子序列中從記錄的無序子序列中“選擇關(guān)鍵字最小或選擇關(guān)鍵字最小或最大的記錄，并將它參與到有序子序列中，以此方最大的記錄，并將它參與到有序子序列中，以此方法添加記錄的有序子序列的長度法添加記錄的有序子序列的長度; ;4. 4. 歸并類歸并類經(jīng)過經(jīng)過“歸并兩個(gè)或兩個(gè)以上的記錄有序子序列歸并兩個(gè)或兩

6、個(gè)以上的記錄有序子序列，逐漸添加記錄有序序列的長度，逐漸添加記錄有序序列的長度; ;5.5.其它方法其它方法下面將對(duì)每一類的排序算法引見一至兩個(gè)排序算法。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講有序序列R1.i-1無序序列 Ri.nRi假設(shè)在排序過程中，記錄序列R1.n的形狀為：有序序列R1.i無序序列 Ri+1.n那么一趟直接插入排序的根本思想為：將記錄Ri插入到有序子序列R1.i-1中，使記錄的有序序列從R1.i-1變?yōu)镽1.i。10.2 插入排序插入排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講顯然，完成這個(gè)“插入需分三步進(jìn)展：2將Rj+1.i-1中的記錄后

7、移一個(gè)位置；3將Ri復(fù)制到Rj+1的位置上。1查找Ri的插入位置j+1；R1.j Ri Rj+1.i-1湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、直接插入排序一、直接插入排序二、折半插入排序二、折半插入排序三、希爾排序三、希爾排序10.2 插入排序插入排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、直接插入排序一、直接插入排序利用順序查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置的插入排序。 排序過程： 整個(gè)排序過程為i-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開場，逐個(gè)進(jìn)展插入，直至整個(gè)序列有序。湖北師范學(xué)院物理系湖北師范學(xué)院物理

8、系王秀章主講王秀章主講算法實(shí)現(xiàn)的要點(diǎn)：1.1.從從Ri-1Ri-1起向前進(jìn)展順序查找起向前進(jìn)展順序查找, ,監(jiān)視哨設(shè)置在監(jiān)視哨設(shè)置在R0;R0; R0 = Ri; / R0 = Ri; / 設(shè)置設(shè)置“哨兵哨兵 for (j=i-1; R0.keyRj.key; -j); / for (j=i-1; R0.keyRj.key; -j); / 從從后往前找后往前找 return j+1; / return j+1; / 前往前往RiRi的插入位置為的插入位置為j+1j+12.2.對(duì)于在查找過程中找到的那些關(guān)鍵字不小于對(duì)于在查找過程中找到的那些關(guān)鍵字不小于Ri.keyRi.key的記錄，可以在查找的

9、同時(shí)實(shí)現(xiàn)向后挪動(dòng)的記錄，可以在查找的同時(shí)實(shí)現(xiàn)向后挪動(dòng)； for (j=i-1; R0.keyRj.key; -j); for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj Rj+1 = Rj3. i = 23. i = 2，3 3，, n, , n, 實(shí)現(xiàn)整個(gè)序列的排序。實(shí)現(xiàn)整個(gè)序列的排序。for (i=2; i=2; +i); if(Ri.keyRi-1.key) 將Ri插入到= R1.i-1中 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void InsertionSort ( Elem R , int n) / 對(duì)記錄序列對(duì)記錄序列R1.n作直接插

10、入排序。作直接插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 復(fù)制為監(jiān)視哨復(fù)制為監(jiān)視哨 for ( j=i-1; R0.key Rj.key; -j ) Rj+1 = Rj; / 記錄后移記錄后移 Rj+1 = R0; / 插入到正確位置插入到正確位置 / InsertSort算法描畫：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76

11、 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序結(jié)果：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講1“比較序列中兩個(gè)關(guān)鍵字的大??；比較序列中兩個(gè)關(guān)鍵字的大??；時(shí)間分析：時(shí)間分析：實(shí)現(xiàn)排序的根本操作有兩個(gè)：實(shí)現(xiàn)排序的根本操作有兩個(gè)：2“挪動(dòng)記錄。挪動(dòng)記錄。 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講112nni2)1)(2(2nnini2)1)(4()1(2nn

12、ini最好的情況：最好的情況： 假設(shè)待排序記錄按關(guān)鍵字從小到大陳列假設(shè)待排序記錄按關(guān)鍵字從小到大陳列( (正序正序) )關(guān)鍵字“比較次數(shù)：最壞的情況：最壞的情況： 假設(shè)待排序記錄按關(guān)鍵字從大到小陳列假設(shè)待排序記錄按關(guān)鍵字從大到小陳列( (逆序逆序) )對(duì)于直接插入排序：對(duì)于直接插入排序：記錄“挪動(dòng)次數(shù)：0記錄“挪動(dòng)次數(shù)：關(guān)鍵字“比較次數(shù)：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講42n42nT(n)=O(n)假設(shè)待排序記錄是隨機(jī)的，取平均假設(shè)待排序記錄是隨機(jī)的，取平均值值關(guān)鍵字“比較次數(shù)：記錄“挪動(dòng)次數(shù)：空間復(fù)雜度：時(shí)間復(fù)雜度：S(n)=O(1)湖北師范學(xué)院物理系湖北師范學(xué)院物理

13、系王秀章主講王秀章主講由于R1.i-1是一個(gè)按關(guān)鍵字有序的有序序列，那么可以利用折半查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉?二、折半插入排序二、折半插入排序排序過程： 用折半查找方法確定插入位置的排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70

14、 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void BiInsertionSort (Elem R ， int n) / 對(duì)記錄序列對(duì)記錄序列R1.n作折半插入排序。作折半插入排序。 for ( i=2; i=L.length; +i ) R0 = Ri; / 將將Ri暫存到暫存到R0 low = 1; high = i-1;while (low=high)

15、/在在Rlow.high中折半查找插入的位置中折半查找插入的位置 m = (low+high)/2; / 折半折半 if (R0.key =high+1; -j ) Rj+1 = Rj; / 記錄后移記錄后移 Rhigh+1 = R0; / 插入插入 / BInsertSort湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評(píng)價(jià)n時(shí)間復(fù)雜度：T(n)=O(n)n空間復(fù)雜度：S(n)=O(1)折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較次數(shù)，但記錄“挪動(dòng)的次數(shù)不變。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講三、希爾排序三、希爾排序(減少增量法減少增量法)根本

16、思想：對(duì)待排記錄系列，先作“宏觀調(diào)整，再作“微觀調(diào)整。所謂“宏觀調(diào)整，指的是“騰躍式的插入排序。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講其中d為增量，它的值在排序過程中從大到小逐漸減少，直至最后一趟排序減為1。詳細(xì)做法為：將記錄系列分成假設(shè)干個(gè)子系列，分別對(duì)每個(gè)子系列作插入排序。R1, R1+d, R1+2d, ,R1+kdR2, R2d, R3d, , R(k+1)d R2, R2+d, R2+2d, ,R2+kd湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講取d3=1三趟分組：13 4 48 38 27 49 55 65 97 76三趟排序：4 13 27 38

17、48 49 55 65 76 97例 初始： 49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分組：49 38 65 97 76 13 27 48 55 4取d2=3二趟分組：13 27 48 55 4 49 38 65 97 76湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講Ch8_3.c例49 38 65 97 76 13 27 48 55 4ji49133827一趟排序：13 27 48 55 4 49 38 65 97 76

18、jiji274jiji55ji38jijiji二趟排序： 13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji764湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講算法描畫：void ShellInsert(SqList &L,int dk) / 對(duì)順序表L作一趟希爾插入排序。 int i,j; for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk) L.rj+dk=L.rj; / 記錄后移，查找插入位置 L.rj+dk=L.r0; / 插入 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講 void Shell

19、Sort(SqList &L,int dlta,int t) / 按增量序列dlta0.t-1對(duì)順序表L作希爾排序。 int k; for(k=0;k1) lastexchangeIndex=1; for(j=1; jAj+1) Swap(Aj,Aj+1); lastexchangeIndex=j; /if i=lastexchangeIndex; /while /bubble_sort起泡排序的終了條件為：最后一趟沒有進(jìn)展“交換。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評(píng)價(jià)n時(shí)間復(fù)雜度n最好情況正序n 只需進(jìn)展一趟起泡n比較次數(shù)：n-1n挪動(dòng)次數(shù)：0n最壞情況逆序n需進(jìn)

20、展n-1趟起泡n比較次數(shù)：) 1(21)(21nninniY挪動(dòng)次數(shù)：) 1(23)(321nninniq空間復(fù)雜度：S(n)=O(1)T(n)=O(n)湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講 目的：找一個(gè)記錄，以它的關(guān)鍵字作目的：找一個(gè)記錄，以它的關(guān)鍵字作為為“樞軸，凡其關(guān)鍵字小于樞軸的記錄樞軸，凡其關(guān)鍵字小于樞軸的記錄均挪動(dòng)至該記錄之前，反之，凡關(guān)鍵字均挪動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均挪動(dòng)至該記錄之后。大于樞軸的記錄均挪動(dòng)至該記錄之后。致使一趟排序之后，記錄的無序序列致使一趟排序之后，記錄的無序序列Rs.tRs.t將分割成兩部分：將分割成兩部分：Rs.i-

21、1Rs.i-1和和Ri+1.t,Ri+1.t,且且 Rj.key Rj.key Ri.key Rj.keyRi.key Rj.key (sji-1) (sji-1) 樞軸樞軸 (i+1jt) (i+1jt)二、一趟快速排序二、一趟快速排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例如例如: :關(guān)鍵字序列關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75其中(52)為樞軸，在調(diào)整過程中，需設(shè)立兩個(gè)指針:low和high，它們的初值分別為:s和t, 之后逐漸減

22、小high，添加low，并保證Rhigh.key52，而Rlow.key52,否那么進(jìn)展記錄的“交換。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 lhxhl 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 4927lhlhlh4965hl1349lh4997lh湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講int Partition(SqList &L,int low,int high) / 交換順序表L中子表L.rlow.high的記錄，使樞軸記錄到位， / 并前往其所在位置，此時(shí)

23、在它之前(后)的記錄均不大(小)于它。算法10.6(a) RedType t; KeyType pivotkey; pivotkey=L.rlow.key; / 用子表的第一個(gè)記錄作樞軸記錄 while(lowhigh) / 從表的兩端交替地向中間掃描 while(low=pivotkey) -high; t=L.rlow; / 將比樞軸記錄小的記錄交換到低端 L.rlow=L.rhigh; L.rhigh=t; while(lowhigh&L.rlow.key=pivotkey) +low; t=L.rlow; / 將比樞軸記錄大的記錄交換到高端 L.rlow=L.rhigh; L.rhig

24、h=t; return low; / 前往樞軸所在位置 算法描畫算法描畫湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講在對(duì)無序序列中記錄進(jìn)展了一次分割之后，分別對(duì)分割所得兩個(gè)子序列進(jìn)展快速排序，依次類推，直至每個(gè)子序列中只含一個(gè)記錄為止。三、快速排序三、快速排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)展快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序終了： 13 27 38 4

25、9 50 65 76 974927ijijij4965ji1349ij4997ij湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講快速排序的算法描畫如下:void QSort (Elem R, int low, int high) / 對(duì)記錄序列對(duì)記錄序列Rlow.high進(jìn)展快速排序進(jìn)展快速排序 if (low high-1) / 長度大于長度大于1 pivotloc = Partition(L, low, high); / 將將L.rlow.high一分為二一分為二 QSort(L, low, pivotloc-1); / 對(duì)低子表遞歸排序，對(duì)低子表遞歸排序，pivotloc是樞軸

26、位置是樞軸位置 QSort(L, pivotloc+1, high); / 對(duì)高子表遞歸排序?qū)Ω咦颖磉f歸排序 / QSort湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void QuickSort(Elem R, int n) / 對(duì)記錄序列進(jìn)展快速排序?qū)τ涗浶蛄羞M(jìn)展快速排序 QSort(R, 1, n); / QuickSort湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講q時(shí)間復(fù)雜度q最好情況每次總是選到中間值作樞軸T(n)=O(nlog2n)q最壞情況每次總是選到最小或最大元素作樞軸T(n)=O(n)v空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸v最壞情況：S(n)=O(n)v普

27、通情況：S(n)=O(log2n)vT(n)=O(n)四、快速排序的時(shí)間分析四、快速排序的時(shí)間分析湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、簡單項(xiàng)選擇擇排序一、簡單項(xiàng)選擇擇排序二、堆排序二、堆排序10.4 選擇排序選擇排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、簡單項(xiàng)選擇擇排序一、簡單項(xiàng)選擇擇排序假設(shè)排序過程中，待排記錄序列的形狀為： 無序序列 Ri.n有序序列R1.i-1從中選出關(guān)鍵字最小的記錄參與有序序列。第i趟簡單項(xiàng)選擇擇排序是有序序列R1.i無序序列 Ri+1.n有序序列中一切記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字湖北師范學(xué)院物理系湖北師范學(xué)院物

28、理系王秀章主講王秀章主講例初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序終了： 13 27 38 49 65 76 97湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void SelectSort(SqList &L) /

29、 對(duì)順序表L作簡單項(xiàng)選擇擇排序。 int i,j; RedType t; for(i=1;iL.length;+i) / 選擇第i小的記錄，并交換到位 j=SelectMinKey(L,i); / 在L.ri.L.length中選擇key最小的記錄 if(i!=j) / 與第i個(gè)記錄交換 t=L.ri; L.ri=L.rj; L.rj=t; 算法描畫算法描畫湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評(píng)價(jià)n時(shí)間復(fù)雜度n記錄挪動(dòng)次數(shù)n最好情況：0n最壞情況：3(n-1)n比較次數(shù)：)(21)(211nninniq空間復(fù)雜度：S(n)=O(1)T(n)=O(n)湖北師范學(xué)院物理系

30、湖北師范學(xué)院物理系王秀章主講王秀章主講二、堆排序二、堆排序堆排序的特點(diǎn)是，在以后各趟的堆排序的特點(diǎn)是，在以后各趟的“選擇中利用在選擇中利用在第一趟選擇中曾經(jīng)得到的關(guān)鍵字比較的結(jié)果。第一趟選擇中曾經(jīng)得到的關(guān)鍵字比較的結(jié)果。堆的定義：堆的定義：堆是滿足以下性質(zhì)的數(shù)列r1, r2, ，rn：122iriririr 或 122iiiirrrrrir2iR2i+1湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講假設(shè)將此數(shù)列看成是一棵完全二叉樹，那假設(shè)將此數(shù)列看成是一棵完全二叉樹，那么堆或是空樹或是滿足以下特性的完全二叉樹么堆或是空樹或是滿足以下特性的完全二叉樹：其左、右子樹分別是堆，并且當(dāng)左：其

31、左、右子樹分別是堆，并且當(dāng)左/ /右子樹右子樹不空時(shí)，根結(jié)點(diǎn)的值小于不空時(shí)，根結(jié)點(diǎn)的值小于( (或大于或大于) )左左/ /右子樹右子樹根結(jié)點(diǎn)的值。根結(jié)點(diǎn)的值。rir2iR2i+1湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例 96，83，27，38，11，9 例 13，38，27，50，76，65，49，97962791138831327384965765097可將堆序列看成完全二叉樹，那么堆頂元可將堆序列看成完全二叉樹，那么堆頂元素完全二叉樹的根必為序列中素完全二叉樹的根必為序列中n n個(gè)元個(gè)元素的最大值或最小值素的最大值或最小值, ,分別稱作大頂堆或分別稱作大頂堆或小頂堆。小

32、頂堆。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講 先建一個(gè)先建一個(gè)“大頂堆，即先選得一個(gè)關(guān)鍵字大頂堆，即先選得一個(gè)關(guān)鍵字為最大的記錄，然后與序列中最后一個(gè)記錄交換為最大的記錄，然后與序列中最后一個(gè)記錄交換，之后繼續(xù)對(duì)序列中前，之后繼續(xù)對(duì)序列中前n-1n-1記錄進(jìn)展記錄進(jìn)展“挑選，重挑選，重新將它調(diào)整為一個(gè)新將它調(diào)整為一個(gè)“大頂堆，再將堆頂記錄和第大頂堆，再將堆頂記錄和第n-1n-1個(gè)記錄交換，如此反復(fù)直至排序終了。個(gè)記錄交換，如此反復(fù)直至排序終了。堆排序即是利用堆的特性對(duì)記錄序列進(jìn)展排堆排序即是利用堆的特性對(duì)記錄序列進(jìn)展排序的一種排序方法。詳細(xì)作法是：序的一種排序方法。詳細(xì)作法是

33、：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例如：例如：40，55，49，73，12，27，98，81，64，3698，81，49，73，36，27，40，55，64，1212，81，49，73，36，27，40，55，64，9881，73，49，64，36，27，40，55，12，98建大頂堆建大頂堆交換交換98和和12挑選挑選湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講所謂“挑選指的是，對(duì)一棵左/右子樹均為堆的完全二叉樹，“調(diào)整根結(jié)點(diǎn)使整個(gè)二叉樹為堆。 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)展比較，并與其中大小者進(jìn)

34、展交換；反復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“挑選湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講40，55，49，73，12，27，98，81，64，36，40495598271273813664404955982736738112644049559827368173126440985549273681731264湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講40，55，49，73，12，27，98，81，64，36409881492736735512649849814027367355126498，81，49，73，36，27，40，5

35、5，64，12湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例 含8個(gè)元素的無序序列49，38，65，97，76，13，27，5049653827137697504965382713765097491338276576509749133827657650971327384965765097湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 27654950273876971

36、3輸出：13 27 38湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講4965502738769713輸出：13 27 387665502738499713輸出：13 27 38 495065762738499713輸出：13 27 38 499765762738495013輸出：13 27 38 49 506597762738495013輸出：13 27 38 49 509765762738495013輸出：13 27 38 49 50 65湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講7665972738495013輸出：13 27 38 49 50 659765762

37、738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38 49 50 65 76 97湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void HeapAdjust(HeapType &H,int s,int m) / 算法10.10 / 知H.rs.m中記錄的關(guān)鍵字除H.rs.key之外均滿足堆的定義， /本函數(shù)調(diào)整H.rs的關(guān)鍵字,使H.rs.m成為一個(gè)大頂堆 /(對(duì)其中記錄的關(guān)鍵字而言) RedType rc; int j; rc=H.rs; for(j=2*s;j=m;j*=2) / 沿key較大的孩子結(jié)點(diǎn)向下挑選

38、if(j0;-i) / 把H.r1.H.length建成大頂堆 HeapAdjust(H,i,H.length); for(i=H.length;i1;-i) / 將堆頂記錄和當(dāng)前未經(jīng)排序子序列H.r1.i中 / 最后一個(gè)記錄相互交換 t=H.r1; H.r1=H.ri; H.ri=t; HeapAdjust(H,1,i-1); / 將H.r1.i-1重新調(diào)整為大頂堆 算法描畫算法描畫湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評(píng)價(jià)n時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)n空間復(fù)雜度：S(n)=O(1)湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講 歸并排

39、序的根本思想是：歸并排序的根本思想是：將兩個(gè)或兩個(gè)以上的有序子序列將兩個(gè)或兩個(gè)以上的有序子序列“歸并為一個(gè)有序序列。歸并為一個(gè)有序序列。10.5 歸并排序歸并排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講在內(nèi)部排序中，通常采用的是在內(nèi)部排序中，通常采用的是2-2-路歸并路歸并排序。即：將兩個(gè)位置相鄰的有序子序列排序。即：將兩個(gè)位置相鄰的有序子序列 有序子序列有序子序列R1.m有序子序列有序子序列Rm+1.n有有 序序 序序 列列 R1.n歸并為一個(gè)有序序列。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void Merge (Elem SR, Elem TR, int

40、i, int m, int n) / 將有序的將有序的SRi.m和和SRm+1.n歸并為歸并為 / 有序的有序的TRi.n for (j=m+1, k=i; i=m & j=n; +k) / 將將SR中記錄由小到大地并入中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 將剩余的將剩余的SRi.m復(fù)制到復(fù)制到TR if (j=n) TRk.n = SRj.n; / 將剩余的將剩余的SRj.n復(fù)制到復(fù)制到TR / Merge“歸并算法描畫如下：歸并算法描畫如下： 湖北師范

41、學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始關(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湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評(píng)價(jià)n時(shí)間復(fù)雜度：T(n)=O(nlog2n)n空間復(fù)雜度：S(n)=O(n)Ch8_9.c湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講歸并排序的算法可以有兩種方式：歸并排序的算法可以有兩種方式：遞歸的和遞推的，它是由兩種不同的遞歸的和遞推的，它是由兩種不同的

42、程序設(shè)計(jì)思想得出的程序設(shè)計(jì)思想得出的 遞歸方式的歸并排序是一種自頂向遞歸方式的歸并排序是一種自頂向下的分析方法下的分析方法 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講假設(shè)記錄無序序列假設(shè)記錄無序序列Rs.tRs.t的兩部分的兩部分Rs.Rs.(s+t)/2(s+t)/2 和和RR(s+t)/2+1.t(s+t)/2+1.t 分別按關(guān)鍵字有序，那么利用上述歸并分別按關(guān)鍵字有序，那么利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列，由此，應(yīng)該先分別對(duì)是一個(gè)有序序列，由此，應(yīng)該先分別對(duì)這兩部分進(jìn)展這兩部分進(jìn)展2-2-路歸并排序。路歸并排序。

43、歸并排序的算法歸并排序的算法湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始關(guān)鍵字： 49 38 65 97 76 13 2738 49 65 97 13 76 2738 49 65 97 13 27 7613 27 38 49 65 76 9749 38 65 97 76 13 27 49 38 65 97 76 13 27 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void Msort ( Elem SR, Elem TR1, int s, int t ) / 將將SRs.t進(jìn)展進(jìn)展2-路歸并排序?yàn)槁窔w并排序?yàn)門R1s.t。 if (s=t) TR1s = SR

44、s; else m = (s+t)/2; / 將將SRs.t平分為平分為SRs.m和和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將遞歸地將SRs.m歸并為有序的歸并為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地遞歸地SRm+1.t歸并為有序的歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將將TR2s.m和和TR2m+1.t歸并到歸并到TR1s.t / MSort算法描畫算法描畫湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void MergeSort (Elem R) / 對(duì)記錄序列對(duì)

45、記錄序列R1.n作作2-路歸并排序。路歸并排序。 MSort(R, R, 1, n); / MergeSort湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評(píng)價(jià)n時(shí)間復(fù)雜度：T(n)=O(nlogn)n空間復(fù)雜度：S(n)=O(n)Ch8_9.c湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講多關(guān)鍵字排序定義：例 對(duì)52張撲克牌按以下次序排序：23A23A23A23A兩個(gè)關(guān)鍵字：花樣 面值23A并且“花樣位置高于“面值n多關(guān)鍵字排序方法n最高位優(yōu)先法MSD)：先對(duì)最高位關(guān)鍵字k1如花樣排序，將序列分成假設(shè)干子序列，每個(gè)子序列有一樣的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2

46、如面值排序，又分成假設(shè)干更小的子序列；依次反復(fù)，直至將每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序；最后將一切子序列依次銜接在一同成為一個(gè)有序序列10.6 基數(shù)排序基數(shù)排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講q最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)展排序，然后再對(duì)高一位的關(guān)鍵字排序，依次反復(fù)，直至對(duì)最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列qMSD與LSD不同特點(diǎn)q按MSD排序，必需將序列逐層分割成假設(shè)干子序列，然后對(duì)各子序列分別排序q按LSD排序，不用分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參與排序；并且可不經(jīng)過關(guān)鍵字比較，而經(jīng)過假設(shè)干次分配與搜集實(shí)現(xiàn)排序q鏈?zhǔn)交鶖?shù)排序q基數(shù)排序

47、：借助“分配和“搜集對(duì)單邏輯關(guān)鍵字進(jìn)展排序的一種方法q鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲(chǔ)構(gòu)造的基數(shù)排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n鏈?zhǔn)交鶖?shù)排序步驟n設(shè)置10個(gè)隊(duì)列，fi和ei分別為第i個(gè)隊(duì)列的頭指針和尾指針n第一趟分配對(duì)最低位關(guān)鍵字個(gè)位進(jìn)展，改動(dòng)記錄的指針值，將鏈表中記錄分配至10個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位一樣n第一趟搜集是改動(dòng)一切非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表n反復(fù)上述兩步，進(jìn)展第二趟、第三趟分配和搜集，分別對(duì)十位、百位進(jìn)展，最后得到一個(gè)有序序列湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主

48、講例初始形狀：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟搜集：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講505008109930063269278083184589二趟搜集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟搜集：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講008063083109184269278505589930三趟搜集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟搜集：湖北師范學(xué)院