數(shù)據(jù)結(jié)構(gòu) ch10 排序課件

《數(shù)據(jù)結(jié)構(gòu) ch10 排序課件》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu) ch10 排序課件（89頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 王秀章王秀章 2005.82007.4物理系物理系 數(shù)據(jù)結(jié)構(gòu)排序數(shù)據(jù)結(jié)構(gòu) ch10 排序湖北師范學(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ī)內(nèi)經(jīng)常進(jìn)行的一種操

2、作，其目的是將一組“無序無序”的記錄序列調(diào)整為的記錄序列調(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個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個關(guān)系 Kp1Kp2Kpn按此固有關(guān)系將式(1)的記錄序列重新排列為 Rp1,

3、Rp2, ，Rpn 的操作稱作排序。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序 在本章內(nèi)先討論內(nèi)部排序的各種方法，然后介紹外部排序的基本過程。若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講三、內(nèi)部排序的方法三、內(nèi)部排序的方法有序序列區(qū) 無序序列區(qū)內(nèi)部排序的過程是一個逐步擴(kuò)大記錄的有序內(nèi)部排序的過程是一個逐步擴(kuò)大記錄的有序序列長度的過程序列長度的過程。在排序的過程中

4、，參與排序的。在排序的過程中，參與排序的記錄序列中存在兩個區(qū)域：有序區(qū)和無序區(qū)。記錄序列中存在兩個區(qū)域：有序區(qū)和無序區(qū)。使有序區(qū)中記錄的數(shù)目增加一個或幾個的操使有序區(qū)中記錄的數(shù)目增加一個或幾個的操作稱為作稱為一趟排序一趟排序。有 序 序 列 區(qū) 無 序 序 列 區(qū)湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講1.1.插入類插入類將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度；逐步擴(kuò)大記錄有序序列長度的方法大致逐步擴(kuò)大記錄有序序列長度的方法大致有下列幾類：有下列幾類：2.2.交換類交換類通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，

5、并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度;湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講3.3.選擇類選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度;4. 4. 歸并類歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度;5.5.其它方法其它方法下面將對每一類的排序算法介紹一至兩個排序算法。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講有序序列R1.i-1無序序列 Ri.nRi假設(shè)在排序過程中，記錄序列R1.n的狀態(tài)為：有序序列R1.i無序序列 Ri+1.n則

6、一趟直接插入排序的基本思想為：將記錄Ri插入到有序子序列R1.i-1中，使記錄的有序序列從R1.i-1變?yōu)镽1.i。10.2 插入排序插入排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講顯然，完成這個“插入”需分三步進(jìn)行：2將Rj+1.i-1中的記錄后移一個位置；3將Ri復(fù)制到Rj+1的位置上。1查找Ri的插入位置j+1；R1.j Ri Rj+1.i-1湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、直接插入排序一、直接插入排序二、折半插入排序二、折半插入排序三、希爾排序三、希爾排序10.2 插入排序插入排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、直

7、接插入排序一、直接插入排序利用順序查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置”的插入排序。 排序過程： 整個排序過程為i-1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進(jìn)行插入，直至整個序列有序。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講算法實(shí)現(xiàn)的要點(diǎn)：1.1.從Ri-1起向前進(jìn)行順序查找,監(jiān)視哨設(shè)置在R0; R0 = Ri; / 設(shè)置“哨兵” for (j=i-1; R0.keyRj.key; -j); / 從后往前找 return j+1; / 返回Ri的插入位置為j+12.2.對于在查找過程中找到的那些關(guān)鍵字不小于Ri.key的記錄，可以

8、在查找的同時實(shí)現(xiàn)向后移動； for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj3. 3. i = 2，3，, n, 實(shí)現(xiàn)整個序列的排序。for (i=2; i=2; +i); if(Ri.keyRi-1.key) 將Ri插入到= R1.i-1中 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void InsertionSort ( Elem R , int n) / 對記錄序列R1.n作直接插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 復(fù)制為監(jiān)視哨 for ( j=i-1; R0.key Rj.key; -j ) Rj+1

9、= 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 (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 (

10、13 27 38 49 65 76 97)排序結(jié)果：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講（1）“比較比較”序列中兩個關(guān)鍵字的大小序列中兩個關(guān)鍵字的大小；時間分析：時間分析：實(shí)現(xiàn)排序的基本操作有兩個：實(shí)現(xiàn)排序的基本操作有兩個：（2）“移動移動”記錄。記錄。 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講112nni2)1)(2(2nnini2)1)(4()1(2nnini最好的情況：最好的情況： 若待排序記錄按關(guān)鍵字從小到大排列若待排序記錄按關(guān)鍵字從小到大排列( (正序正序) )關(guān)鍵字“比較”次數(shù)：最壞的情況：最壞的情況： 若待排序記錄按關(guān)鍵字從大到小排列若待排序記

11、錄按關(guān)鍵字從大到小排列( (逆序逆序) )對于直接插入排序：對于直接插入排序：記錄“移動”次數(shù)：0記錄“移動”次數(shù)：關(guān)鍵字“比較”次數(shù)：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講42n42nT(n)=O(n)若待排序記錄是隨機(jī)的，取平均值若待排序記錄是隨機(jī)的，取平均值關(guān)鍵字“比較”次數(shù)：記錄“移動”次數(shù)：空間復(fù)雜度：時間復(fù)雜度：S(n)=O(1)湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講因?yàn)镽1.i-1是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉?二、折半插入排序二、折半插入排序排序過

12、程： 用折半查找方法確定插入位置的排序湖北師范學(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 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

13、42 70 85 )湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void BiInsertionSort (Elem R ， int n) / 對記錄序列R1.n作折半插入排序。 for ( i=2; i=L.length; +i ) R0 = Ri; / 將Ri暫存到R0 low = 1; high = i-1;while (low=high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1 = Rj; / 記錄后移 Rhigh+1 = R0; / 插入 / BInsertSor

14、t湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評價q時間復(fù)雜度：T(n)=O(n)q空間復(fù)雜度：S(n)=O(1)折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)，但記錄“移動”的次數(shù)不變。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講三、希爾排序三、希爾排序(縮小增量法縮小增量法)基本思想：對待排記錄系列，先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是“跳躍式”的插入排序。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講其中d為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。具體做法為：將記錄系列分成若干個子系列

15、，分別對每個子系列作插入排序。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 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

16、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 76jiji274jiji55ji38jijiji二趟排序： 13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji764湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講算法描述：void ShellInsert(SqList

17、&L,int dk) / 對順序表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 ShellSort(SqList &L,int dlta,int t) / 按增量序列dlta0.t-1對順序表L作希爾排序。 int k; for(k=0;k1) lastexchangeIndex=1; for(j=1; jAj+1) Swap(Aj,Aj+1); las

18、texchangeIndex=j; /if i=lastexchangeIndex; /while /bubble_sort起泡排序的結(jié)束條件為：最后一趟沒有進(jìn)行最后一趟沒有進(jìn)行“交換交換”。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評價q時間復(fù)雜度最好情況（正序） 只需進(jìn)行一趟起泡Y比較次數(shù)：n-1Y移動次數(shù)：0最壞情況（逆序）需進(jìn)行n-1趟起泡Y比較次數(shù)：) 1(21)(21nninniY移動次數(shù)：) 1(23)(321nninniq空間復(fù)雜度：S(n)=O(1)T(n)=O(n)湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講 目標(biāo)：目標(biāo)：找一個記錄，以它的關(guān)

19、鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動至該記錄之前移動至該記錄之前，反之，凡關(guān)鍵字大關(guān)鍵字大于樞軸于樞軸的記錄均移動至該記錄之后移動至該記錄之后。致使一趟排序一趟排序之后，記錄的無序序列Rs.t將分割成兩部分：分割成兩部分：Rs.i-1和和Ri+1.t,且且 Rj.key Ri.key Rj.key (sji-1) 樞軸樞軸 (i+1jt)二、一趟快速排序二、一趟快速排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例如例如: :關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36,

20、 (52) 58, 61, 97, 80, 75其中(52)為樞軸，在調(diào)整過程中，需設(shè)立兩個指針:low和high，它們的初值分別為:s和t, 之后逐漸減小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

21、(SqList &L,int low,int high) / 交換順序表L中子表L.rlow.high的記錄，使樞軸記錄到位， / 并返回其所在位置，此時在它之前(后)的記錄均不大(小)于它。算法10.6(a) RedType t; KeyType pivotkey; pivotkey=L.rlow.key; / 用子表的第一個記錄作樞軸記錄 while(lowhigh) / 從表的兩端交替地向中間掃描 while(low=pivotkey) -high; t=L.rlow; / 將比樞軸記錄小的記錄交換到低端 L.rlow=L.rhigh; L.rhigh=t; while(lowhigh&

22、L.rlow.key=pivotkey) +low; t=L.rlow; / 將比樞軸記錄大的記錄交換到高端 L.rlow=L.rhigh; L.rhigh=t; return low; / 返回樞軸所在位置 算法描述算法描述湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講在對無序序列中記錄進(jìn)行了一次分割之后，分別對分割所得兩個子序列進(jìn)行快速排序，依次類推，直至每個子序列中只含一個記錄為止。三、快速排序三、快速排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 4

23、9 (76 97 65 50) 分別進(jìn)行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講快速排序的算法描述如下:void QSort (Elem R, int low, int high) / 對記錄序列Rlow.high進(jìn)行快速排序 if (low high-1) / 長度大于1 pivotloc = Partition(L, low, high); / 將L.rlow.high一分為二 Q

24、Sort(L, low, pivotloc-1); / 對低子表遞歸排序，pivotloc是樞軸位置 QSort(L, pivotloc+1, high); / 對高子表遞歸排序 / QSort湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void QuickSort(Elem R, int n) / 對記錄序列進(jìn)行快速排序 QSort(R, 1, n); / QuickSort湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講q時間復(fù)雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n)v空間復(fù)雜度：

25、需?？臻g以實(shí)現(xiàn)遞歸l最壞情況：S(n)=O(n)l一般情況：S(n)=O(log2n)vT(n)=O(n)四、快速排序的時間分析四、快速排序的時間分析湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、簡單選擇排序一、簡單選擇排序二、堆排序二、堆排序10.4 選擇排序選擇排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講一、簡單選擇排序一、簡單選擇排序假設(shè)排序過程中，待排記錄序列的狀態(tài)為： 無序序列 Ri.n有序序列R1.i-1從中選出關(guān)鍵字最小的記錄加入有序序列。第i趟簡單選擇排序是有序序列R1.i無序序列 Ri+1.n有序序列中所有記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字

26、湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始： 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 排序結(jié)束： 13 27 38 49 65 76 97湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講void SelectS

27、ort(SqList &L) / 對順序表L作簡單選擇排序。 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個記錄交換 t=L.ri; L.ri=L.rj; L.rj=t; 算法描述算法描述湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評價q時間復(fù)雜度記錄移動次數(shù)Y最好情況：0Y最壞情況：3(n-1)比較次數(shù)：)(21)(211nninniq空間復(fù)雜度：S(n)=O(1)T(n)=O

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

29、子樹不空時，根結(jié)點(diǎn)的值小于時，根結(jié)點(diǎn)的值小于( (或大于或大于) )左左/ /右子樹根結(jié)右子樹根結(jié)點(diǎn)的值點(diǎn)的值。rir2iR2i+1湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例 （96，83，27，38，11，9） 例 （13，38，27，50，76，65，49，97）962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中（完全二叉樹的根）必為序列中n n個元素個元素的最大值或最小值的最大值或最小值, ,分別稱作大頂堆或小分別稱作大頂堆或小頂堆。頂堆。湖北師范學(xué)院物理系湖北師范學(xué)院

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

31、院物理系王秀章主講王秀章主講例如：例如：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é)院物理系王秀章主講王秀章主講所謂“篩選篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調(diào)整調(diào)整”根結(jié)點(diǎn)根結(jié)點(diǎn)使整個二叉樹為堆。 方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中大（?。┱哌M(jìn)行交換；

32、重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個從堆頂至葉子的調(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，36）4098814927367355126498498140273673551264（98，81，49，73，36，27，40

33、，55，64，12）湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例 含8個元素的無序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738

34、769713輸出：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 6597

35、65762738495013輸出：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成為一個大頂堆 /(對其中記錄的關(guān)鍵字而言) RedType rc; int j; rc=H.rs; for(j=2*s;j=m;j*=2) / 沿key較大的孩子結(jié)

36、點(diǎn)向下篩選 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中 / 最后一個記錄相互交換 t=H.r1; H.r1=H.ri; H.ri=t; HeapAdjust(H,1,i-1); / 將H.r1.i-1重新調(diào)整為大頂堆 算法描述算法描述湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評價q時間復(fù)雜度：最壞情況下T(n)=O(nlogn)q空間復(fù)雜度：S(n)=O(1)湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章

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

38、R, int 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ù)制到TR if (j=n) TRk.n = SRj.n; / 將剩余的SRj.n復(fù)制到TR / Merge“歸并歸并”算法描述如下算法描述如下： 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始關(guān)鍵

39、字： 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算法評價q時間復(fù)雜度：T(n)=O(nlog2n)q空間復(fù)雜度：S(n)=O(n)Ch8_9.c湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講歸并排序的算法可以有兩種形式：歸并排序的算法可以有兩種形式：遞歸的和遞推的，它是由兩種不同的遞歸的和遞推的，它是由兩種不同的程序設(shè)計思想得出的程序設(shè)計思想得出的 遞歸形式的歸并排序是

40、一種自頂向遞歸形式的歸并排序是一種自頂向下的分析方法下的分析方法 湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講如果記錄無序序列如果記錄無序序列Rs.t的兩部分的兩部分Rs. (s+t)/2 和和R (s+t)/2+1.t 分別按關(guān)分別按關(guān)鍵字有序，則利用上述歸并算法很容易鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序?qū)⑺鼈儦w并成整個記錄序列是一個有序序列序列，由此，應(yīng)該先分別對這兩部分進(jìn)由此，應(yīng)該先分別對這兩部分進(jìn)行行2-2-路歸并排序。路歸并排序。歸并排序的算法歸并排序的算法湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始關(guān)鍵字： 49 38

41、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)行2-路歸并排序?yàn)門R1s.t。 if (s=t) TR1s = SRs; else m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.tMsort (SR, TR2, s, m

42、); / 遞歸地將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) / 對記錄序列R1.n作2-路歸并排序。 MSort(R, R, 1, n); / MergeSort湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評價q時間復(fù)雜度：T(n)=O(nlog

43、n)q空間復(fù)雜度：S(n)=O(n)Ch8_9.c湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講q多關(guān)鍵字排序n定義：例 對52張撲克牌按以下次序排序：23A23A23A23A兩個關(guān)鍵字：花色（ ） 面值（23A）并且“花色”地位高于“面值”n多關(guān)鍵字排序方法q最高位優(yōu)先法（MSD)：先對最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至將每個子序列對最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個有序序列10.6 基數(shù)排序基數(shù)排序湖北師范學(xué)院物理系湖北師范學(xué)

44、院物理系王秀章主講王秀章主講q最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對高一位的關(guān)鍵字排序，依次重復(fù)，直至對最高位關(guān)鍵字k1排序后，便成為一個有序序列qMSD與LSD不同特點(diǎn)按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序按LSD排序，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序q鏈?zhǔn)交鶖?shù)排序n基數(shù)排序：借助“分配”和“收集”對單邏輯關(guān)鍵字進(jìn)行排序的一種方法n鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n鏈?zhǔn)交鶖?shù)排序步驟q設(shè)置10個隊(duì)列，fi和

45、ei分別為第i個隊(duì)列的頭指針和尾指針q第一趟分配對最低位關(guān)鍵字（個位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊(duì)列中，每個隊(duì)列記錄的關(guān)鍵字的個位相同q第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個非空隊(duì)列的隊(duì)頭記錄，重新將10個隊(duì)列鏈成一個鏈表q重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對十位、百位進(jìn)行，最后得到一個有序序列湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f

46、3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講008063083109184269278505589930三趟收集：109008184930e

47、0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講n算法評價q時間復(fù)雜度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n記錄數(shù) d關(guān)鍵字?jǐn)?shù) rd關(guān)鍵字取值范圍 q空間復(fù)雜度：S(n)=2rd個隊(duì)列指針+n個指針域空間湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講初始狀態(tài)：1278109063930589184505269008083023456789

48、10f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=011223344566778910493006308318450527800810958926903106719258湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=0134477 910493006308318450527800

49、810958926903106719258一趟收集：31016258750500810993006326927808318458909243811065二趟收集：湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講750500810993006326927808318458909243811065二趟收集：f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=04479287928900806308310918426927850558993003102681754三趟

50、收集：311065湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講10.5各種排序方法的綜合比較各種排序方法的綜合比較 一、時間性能一、時間性能按平均的時間性能平均的時間性能來分，有三類有三類排序方法： 時間復(fù)雜度為O(nlogn)的方法有：快速排序、堆排序和歸并排序，其中以快速排序?yàn)樽詈茫?時間復(fù)雜度為O(n2)的有：直接插入排序、起泡排序和簡單選擇排序，其中以直接插入為最好，特別是對那些對關(guān)鍵字近似有序的記錄序列尤為如此； 時間復(fù)雜度為O(n)的排序方法只有，基數(shù)排序。 當(dāng)待排記錄序列按關(guān)鍵字順序有序時，直接插入排序和起泡排序能達(dá)到O(n)的時間復(fù)雜度;而對于快速排序而言，這是最不

51、好的情況，此時的時間性能蛻化為O(n2)，因此是應(yīng)該盡量避免的情況。簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講 指的是排序過程中所需的輔助空間大小。1. 所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復(fù)雜度為O(1)；2. 快速排序?yàn)镺(logn)，為棧所需的輔助空間;3. 歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(rd)。二、空間性能二、空間性能湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講 穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。 當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時，必須采用穩(wěn)定的排序方法。 對于不穩(wěn)定的排序方法，只要能舉出一個實(shí)例說明即可。三、排序方法的穩(wěn)定性能三、排序方法的穩(wěn)定性能 快速排序和堆排序是不穩(wěn)定的排序方法快速排序和堆排序是不穩(wěn)定的排序方法。湖北師范學(xué)院物理系湖北師范學(xué)院物理系王秀章主講王秀章主講作業(yè)：P60：10.1、 10.2、 10.3、10.11、 10.25、10.30、 10.43