第十章 排序.ppt

1、第八章 內部排序,8.1 概述 8.2 插入類排序 8.3 交換類排序 8.4 選擇類排序 8.5 歸并類排序 8.6 基數排序 8.7 各種內部排序方法的比較討論,8.1 概述,記錄：記錄是由一個或多個數據項根據一定的目的而組成的數據項集合。 數據項：數據項是不可分的最小數據單位。一個數據項由若干個字符或數字組成，它代表某一事物的一種屬性。數據項又稱為數據域、字段、屬性。 關鍵字：是數據元素（或稱為“記錄”）中某個數據項的值，它可以標識（識別）一個數據元素。 主關鍵字：可以識別唯一一個數據元素。 次關鍵字：能夠識別若干個數據元素。,8.1 概述,8.1 概述,排序:是將一些數據元素（或記錄）

2、的任意序列，重新排列成一個按關鍵字有序的序列。 例如：將下列關鍵字序列 52，36，80，36，14，58，61，23，97，75 調整為 14，23，36，36，52，58，61，75，80，97,一般情況下:假設含n個記錄的序列為R1,R2,Rn 其相應的關鍵字序列為K1,K2,Kn這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系Kp1 Kp2 Kp3 Kpn按此固有關系將上式記錄序列重新排列為Rp1,Rp2,Rpn的操作稱作排序。,8.1 概述,排序算法的分類： 按排序過程中涉及的存儲器不同，可將排序方法分為兩大類： 內部排序：若整個排序過程不需要訪問外存便能完成，則稱此類

3、排序問題為內部排序； 外部排序：在排序過程中，若參加排序的記錄數量很大，不僅要使用內存，而且還需要訪問外存的排序過程稱為“外部排序。,排序算法的穩(wěn)定性： 如果待排序記錄中存在多條關鍵字相同的記錄，經過排序后，這些記錄之間的相對次序不變，則稱這種排序算法為“穩(wěn)定的”；反之，稱為“不穩(wěn)定的”。,內部排序的方法: 內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。,一趟排序,8.1 概述,內部排序的方法: 逐步擴大記錄有序序列長度的方法大致有以下幾類： 1、插入類:將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度 2、交換類:通過“交換”無序序列中的記錄從而得到

4、其中關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。,8.1 概述,內部排序的方法: 3、選擇類:從記錄的無序子序列中“選擇”無序子序列中關鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度。 4、歸并類:通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度。 5、其他方法,8.1 概述,8.1 概述,排序算法的評價標準： 1. 算法的時間復雜度 2. 執(zhí)行算法所需的附加空間 3. 算法本身的復雜性 排序過程中需進行的兩種基本操作： 1.比較兩個關鍵字的大?。ū仨殻?2.將記錄從一個位置移動到另一個位置(是

5、否需要移動記錄取決于記錄的存儲方式) 順序存儲：必須移動記錄 鏈式存儲：不須移動記錄，只需修改指針,本章實現排序算法時記錄所采用的存儲結構： typedef struct KeyType key; /主關鍵字域，KeyType為int等 / 其它屬性域 RecType ; 也即：本章所介紹的排序算法都是在一維結構體數組上實現的。,8.1 概述,8.2 插入類排序,8.2.1 直接插入排序 1. 基本思想 將一個記錄插入到已經排好序的有序表中，從而得到一個新的記錄數增加1的有序表。 一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列R1.i-1中插入一個記錄Ri，變成含有i

6、個記錄的有序子序列R1i。,8.2.1 直接插入排序,8.2.1 直接插入排序,2. 算法描述 void insertsort(RecType R, int n) /* R為存放待排序數據元素（記錄）的一維數組，大小為n+1，其中R0置空，R1到Rn為待排序的n個記錄*/ for(i=2;iR0.key; j- -) Rj+1=Rj; Rj+1=R0; ,8.2.1 直接插入排序,3.算法分析 直接插入排序的算法簡潔，容易實現。 從時間看，排序的基本操作為：比較兩個記錄的大小和移動記錄。其中：（1）最小比較次數：Cmin = n-1 = O(n)（2）最大比較次數：Cmax =(2+3+n)=

7、 (n+2)(n-1)/2 = O(n2 )（3）最小移動次數：Mmin = 0 （4）最大移動次數：Mmax = (3+n+n+1) = O(n2) 故：該算法適應于待排序記錄的數量n很小的情況。 從空間看，直接插入排序只需一個輔助空間。,8.2.1 直接插入排序,4.改進算法 在直接插入排序的基礎上，從減少“比較”和“移動”這兩種操作的次數著手，可得到一些改進的插入排序算法，如： 折半插入排序：可以減少關鍵字之間的比較次數，但移動次數不變，故時間復雜度仍為O（n2）。其基本思想是利用折半查找來找要插入的位置。,2_路插入排序:可以減少排序過程中移動記錄的次數，但為此需要n個記錄的輔助空間。

8、 例：初始關鍵字： 49 38 65 97 76 13 27 49 i=1: (49) first| final i=2: （49) (38) final| |first i=3: (49 65) (38) |final |first i=4: (49 65 97) (38) |final |first i=5: (49 65 76 97) (38) |final |first i=6: (49 65 76 97) (13 38) |final |first i=7: (49 65 76 97) (13 27 38) |final |first i=8: (49 49 65 76 97 13

9、27 38) |final |first,移動次數約為n2/8.因此，這種方法只能減少移動次數，而不能避免移動。并且當第一個元素是待排序記錄中最小或最大的記錄時，該方法就完全失去它的優(yōu)越性。,表插入排序：就是通過鏈接指針，按關鍵碼的大小，實現從小到大的鏈接過程，為此需增設一個指針項。操作方法與直接插入排序類似，所不同的是直接插入排序要移動記錄，而表插入排序是修改鏈接指針。用靜態(tài)鏈表來說明。,表插入排序得到一個有序的鏈表，查找則只能進行順序查找，而不能進行隨機查找，如折半查找。為此，還需要對記錄進行重排。 重排記錄方法：按鏈表順序掃描各結點，將第i個結點中的數據元素調整到數組的第i個分量數據域。

10、因為第i個結點可能是數組的第j個分量，數據元素調整僅需將兩個數組分量中數據元素交換即可，但為了能對所有數據元素進行正常調整，指針域也需處理。,void Arrange (SqList / p 指向下一個將要調整的記錄 / for / Arrange,8.2.3 希爾排序,Shell排序，又稱“縮小增量排序”，它也屬于插入類排序，它是對直接插入排序的一種改進算法。在時間效率上比直接插入排序有較大的提高。 從對直接插入排序的分析可知，其最好的情況下時間復雜度是O（n），最壞的情況下時間復雜度為O(n2), 但是當待排序的記錄已經處于“基本有序”狀態(tài)時或當n值較小時，直接插入排序的效率均可大大提高。

11、 Shell 排序方法正是基于這兩點考慮，對直接插入排序加以改進而提出的一種插入排序算法。,8.2.3 希爾排序,1.基本思想 Shell排序，又稱“縮小增量排序”， 先將整個待排序序列分割成為若干個子序列，分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。 例如：假設待排序的10個記錄，其關鍵字分別是： 49，38，65，97，76，13，27，49/，55，04 。增量序列取值依次為：5，3，1。則對其進行希爾排序的過程如下：,8.2.3 希爾排序,49 38 65 97 76 13 27 49/ 55 04,13 27 49/ 55 04 49 3

12、8 65 97 76,一趟排序結果（步長為5）,二趟排序結果（步長為3）,13 04 49/ 38 27 49 55 65 97 76,04 13 27 38 49/ 49 55 65 76 97,三趟排序結果,8.2.3 希爾排序,2.算法分析 Shell 排序的分析是一個復雜的數學問題，特別是如何選擇增量序列才能產生最好的排序效果問題。因此，到目前為止還沒能求得一種最好的增量序列。但不管是哪一種增量序列，最后一個增量值必須是1。 增量序列可以有多種取法，常用的增量序列是Shell本人最初提出的：取di=n/2, di+1=di/2, , dt=1,其中t=log2n。 目前研究已得知，當n

13、在某個特定范圍內時，Shell 排序的平均比較次數和平均移動次數都是n1.3左右，當n時可減少至n ( log2n )2。,8.2.3 希爾排序,練習題：已知待排序的11個數據元素，其關鍵字分別是： 67，58，25，97，82，11，24，6，39，4，56 ，采用希爾排序將其按關鍵字排列為遞增有序的序列，增量序列取值依次為：5，3，1。,8.3 交換類排序,一、冒泡排序 1.算法思想（從小到大排序） 相鄰兩數比較，若前面數大，則兩數交換位置，直至最后一個元素被處理，最大的元素就“沉”到最下面，即在最后一個元素位置。這樣，如有n個元素，共進行上述操作n-1趟，每趟讓剩余元素中最大的元素“沉”

14、到下面，從而完成排序。,第一次65和78比較后結果： 65 78 43 21 90 17,輸入數據： 65 78 43 21 90 17 第一趟排序過程如下：,第二次78和43比較后結果 ： 65 43 78 21 90 17,第三次78和21比較后結果： 65 43 21 78 90 17,第四次78和90比較后結果： 65 43 21 78 90 17,第五次90和17比較后結果： 65 43 21 78 17 90,8.3 交換類排序,結果：經過第一趟排序，得到最大值為90，放入最 后一個位置。,8.3 交換類排序,整個排序排序過程如下：,65 78 43 21 90 17,65 43

15、21 78 17 90,43 21 65 17 78 90,21 43 17 65 78 90,21 17 43 65 78 90,17 21 43 65 78 90,第1趟冒泡排序,第2趟冒泡排序,第3趟冒泡排序,第4趟冒泡排序,第5趟冒泡排序,結論：6個數據需要進行5趟排序， n個數據需要進行n1趟排序，第i趟排序需要比較n-i次。,2.算法描述（從小到大排序） void BubbleSort(RecType R,int k) int i,j, flag; RecType t; for (j=0;jRi+1.key) t=Ri; Ri=Ri+1; Ri+1=t; /*相鄰記錄交換位置*/

16、flag=1; /*有元素交換,標志置1*/ if (flag=0) break; /*沒有交換元素，結束循環(huán)*/ ,8.3 交換類排序,8.3 交換類排序,3.算法分析 最好的情況下:初始序列為“正序”，只需進行一趟排序，進行n-1次比較，不需要移動任何記錄； 最壞的情況下:初始序列為“逆序”，則需要進行n-1趟排序，第i（1in-1）趟排序需要比較n-i次共(n-1)n/2次比較，同時還要移動元素3n(n-1)/2次。 因此，冒泡排序總的時間復雜度是O(n2).,二、快速排序 1.基本思想 通過一趟排序將待排序的記錄分割成兩個獨立的部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，然

17、后再分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。 2.做法 首先選取一個記錄作為“樞軸”（通常選第一個記錄），以它的關鍵字為基準重排其余記錄：將所有關鍵字比它大的記錄都排在它之后，而將所有關鍵字比它小的記錄都排在它之前，由此完成一趟快速排序。之后，分別再對這兩個子序列進行快速排序。,8.3 交換類排序,具體操作為： 附設兩個指針low和high，它們的初值分別為1和n，設樞軸記錄的關鍵字為key（一般取第一個關鍵字作為key）。 首先從high所指的位置起向前搜索，找到第一個比key小的關鍵字，交換位置； 然后從low所指的位置起向后搜索，找到第一個比key大的關鍵字，交換位置； 重復

18、上兩步直至low=high為止。,8.3 交換類排序,49 38 65 97 76 13 27 49/,27 38 65 97 76 13 49 49/,27 38 49 97 76 13 65 49/,27 38 13 97 76 49 65 49/,27 38 13 49 76 97 65 49/,初始關鍵字,第2次交換后,第3次交換后,第4次交換后,第1次交換后,完成一趟快 速排序,8.3 交換類排序, 27 38 13 49 76 97 65 49/ , 49 38 65 97 76 13 27 49/ , 13 27 38 , 49/ 65 76 97 ,49/ 65, 13 27

19、38 49 49/ 65 76 97 ,一次劃分之后,初始狀態(tài),分別進行快速排序,最后結果,快速排序示例,8.3 交換類排序,2.算法描述（從小到大排序） void QuickSort(RecType R, int low,int high) /* R為待排序記錄的集合*/ int mid; if(lowhigh) mid=Partition(R,low,high); QuickSort(R,low,mid-1); QuickSort (R,mid+1,high); ,8.3 交換類排序,int Partition(RecType R, int low,int high) int mid=Rl

20、ow.key; RecType pass; while(low=mid) -high; pass=Rlow; Rlow=Rhigh; Rhigh=pass; while(lowhigh ,8.3 交換類排序,3.性能分析 快速排序的平均時間復雜度是O(nlogn),它是目前基于比較的內部排序方法中速度最快的一種，快速排序也因此而得名。 但是，若初始的關鍵字序列已經“基本有序”時，快速排序將退化為冒泡排序，其時間復雜度為O（n2）。如：初始關鍵字序列為： 45 50 70 60 15 10 23 17 快速排序過程中需要一個?？臻g來實現遞歸，因此空間復雜度不如前幾種排序方法。,8.3 交換類排序

21、,練習題：已知待排序的關鍵字序列是： 67，25，82，11，24，6，39，4 ，采用快速排序法將其按關鍵字排列為遞增有序的序列。,8.3 交換類排序,8.4 選擇類排序,選擇排序的基本思想：每一趟在n-i+1（i1,2,n-1)個記錄中選取關鍵字最小的記錄，作為有序序列中的第i個記錄。 8.4.1 簡單選擇排序 1.基本思想 第i 趟（1in）簡單選擇排序的操作為：通過n-i次關鍵字的比較，從n-i+1個記錄中選出關鍵字最小的記錄，并和第i個記錄交換位置。,8.4.1 簡單選擇排序,例如，用簡單選擇排序對如下關鍵字序列進行排序：,65 78 43 21 90 17,17 78 43 21

22、90 65,17 21 43 78 90 65,17 21 43 78 90 65,17 21 43 65 90 78,17 21 43 65 78 90,第1趟選擇排序,第2趟選擇排序,第3趟選擇排序,第4趟選擇排序,第5趟選擇排序,2.算法描述 void SelectSort(SecType R ,int n) /* R為待排序記錄的集合，n為待排序記錄的條數*/ int i; SecType t; for(i=0;iRj.key) k=j; if(k!=i)t=Ri;Ri=Rk;Rk=t; ,8.4.1 簡單選擇排序,8.4.1 簡單選擇排序,3.性能分析 最好的情況下：記錄移動的次數為

23、0；最壞的情況下，記錄移動的次數為 3(n-1) 次。 但無論在什么情況下，需要進行的關鍵字間的比較次數均為 n(n-1)/2。 因此，總的時間復雜度是O(n2).,改進的方法：減少關鍵字間的比較次數。 如何減少？ 體育錦標賽就是一種改進了的選擇排序方法。,8.4.2 堆排序,1.堆的定義 堆是一個關鍵字序列k1,k2,kn,它具有如下特性： ki k2i , ki k2i+1 或者 ki k2i , ki k2i+1 其中 (i=1,2, n/2),若將此序列所對應的一維數組看作是一棵完全二叉樹的順序存儲結構，則堆的含義表明： 完全二叉樹中任一結點的關鍵字都小于或等于它的左右孩子的關鍵字（小

24、頂堆）； 或者完全二叉樹中任一結點的關鍵字都大于或等于它的左右孩子的關鍵字（大頂堆）。,8.4.3 堆排序,判斷下列關鍵字序列是否是堆： 5,23,16,68,94, 20,71,73 96,83,27,38,11,9,最小值,最大值,8.4.3 堆排序,2.堆排序的基本思想 若在輸出堆頂的最小值之后，調整剩余的n-1個元素序列為一個新的堆，則可得到n個元素中的次小值。如此反復，便能得到一個有序序列，這個過程稱之為堆排序。 實現堆排序要解決的兩個問題是： （1）如何由一個無序序列建成一個堆？ （2）如何在輸出堆頂元素后，調整剩余元素為一個堆？,8.4.3 堆排序,如何在輸出堆頂元素后，調整剩余

25、元素為一個堆？ 方法是：以堆中的最后一個元素和堆頂元素進行交換，此時根結點的左、右子樹均為堆，然后從上到下逐層調整即可。,左右子樹均為堆,8.4.3 堆排序,逐步調整為新堆的過程如下:,左子樹為堆,調整右子樹,8.4.3 堆排序,重復此過程，直至輸出所有關鍵字為止,輸出：5，16，20，,上述從堆頂到葉子的調整過程稱為“篩選”。 從一個無序序列建堆的過程就是一個反復“篩選”的過程。,8.4.3 堆排序,3.建堆過程 將無序序列看成是一個完全二叉樹，則最后一個非葉子結點就是第n/2個結點，因此“篩選”只需要從第n/2個結點開始（一個葉子結點一定是一個堆）。 例如：已知8個元素的無序序列為： 49

26、，38，65，97，76，13，27，49/ ， 它所對應的完全二叉樹如下圖a 所示，要求創(chuàng)建一個小頂堆。 逐步篩選，從第4個元素97開始：,8.4.3 堆排序,無序序列： 49，38，65，97，76，13，27，49/ ,圖a：無序序列,圖b：97被篩選后的狀態(tài),調整以97為根的子樹,8.4.3 堆排序,圖d：65被篩選后的狀態(tài),圖c：調整以65為根的子樹,8.4.3 堆排序,圖f：38被篩選后的狀態(tài),圖e：調整以38為根的子樹,圖g：調整以49為根的樹,圖h：49被篩選后建成的堆,圖h即為一個新建的小頂堆，小頂堆建立后，堆頂就是最小關鍵字。,void HeapAdjust (Elem R

27、 , int s, int m) rc=Rs; for ( j=2*s;j=Rj.key) break; /rc應插入在位置s上 Rs=Rj; s=j; Rs=rc; /插入,void HeapSort (Elem R , int n) / 對記錄序列R1n進行堆排序 for (i=n/2;i0;-i) HeapAdjust (R,i,n); /建大頂堆 for (i=n;i1;-i) R1 Ri; /將堆頂記錄和當前未經排序子序列 /R1i中最后一個記錄相互交換 HeapAdjust(R,1,i-1); / 對R1進行篩選 ,10.4.3 堆排序,4.性能分析： 堆排序的時間主要由建立初始堆

28、和不斷重復調整堆這兩部分的時間開銷構成。 經分析，堆排序在最壞情況下的總的時間復雜度是 ：O(n log2n)。相對于快速排序來說，這是堆排序的最大優(yōu)點。 在空間上，堆排序僅需一個記錄大小供交換使用的輔助空間。 由于初始建堆所需的比較次數較多，所以堆排序不適于記錄數較少的文件，但對n較大的文件是很有效的。,8.5 歸并類排序,所謂“歸并”是指：將兩個有序的序列合并為一個新的有序序列。 1.基本思想 將待排序序列看成為n個長度為1 的有序子序列，把這些子序列兩兩進行歸并，便得到n/2 個長度為2的有序子序列，然后再兩兩歸并，, 如此重復，直到最后得到一個長度為n的有序序列為止，這種方法成為二路歸

29、并方法。,8.5 歸并類排序,例如：采用2路歸并法將無序序列 49, 38, 65, 97, 76, 13, 27, 49/ 排列為一個遞增有序序列。,49 38 65 97 76 13 27 49/,38 49 65 97 13 76 27 49/,38 49 65 97 13 27 49/ 76,13 27 38 49 49/ 65 76 97,初始無序序列,第一趟歸并之后,第二趟歸并之后,第三趟歸并之后,8.5 歸并類排序,2.性能分析 對n個記錄的序列進行2-路歸并排序時，必須進行 log2n 趟歸并，而每趟歸并所需的時間是O(n), 所以二路歸并排序算法時間復雜度為O(nlog2n)。 與快速排序相比，歸并排序的最大優(yōu)點是，它是一種穩(wěn)定的排序方法，但在一般情況下，很少利用2-路歸并排序進行內部排序。,前介紹的