1、本章主要內容：本章主要內容： 主要介紹以下各種內部排序方法的基本思想、算主要介紹以下各種內部排序方法的基本思想、算法特點、排序過程及時間復雜度分析。法特點、排序過程及時間復雜度分析。本章重點：本章重點：1.1.掌握各種排序方法中的高效方法掌握各種排序方法中的高效方法( (插入排序的希爾排序插入排序的希爾排序、交換排序的快速排序、選擇排序的堆排序、歸并排序、交換排序的快速排序、選擇排序的堆排序、歸并排序) )；2.2.掌握各種排序方法的掌握各種排序方法的時間復雜度時間復雜度；3.3.理解排序方法理解排序方法“穩定穩定”和和“不穩定不穩定”的含義。的含義。 第十章第十章 內部排序內部排序第十章第十

2、章 內部排序內部排序 10.1 10.1 概概 述述 10.2 10.2 插入排序插入排序 10.3 10.3 快速排序快速排序 10.4 10.4 選擇排序選擇排序 10.5 10.5 歸并排序歸并排序 10.6 10.6 基數排序基數排序 10.7 10.7 各種排序方法的比較各種排序方法的比較 10.1 10.1 概概 述述一、排序的定義一、排序的定義二、二、一些排序的術語一些排序的術語一、一、排序的定義排序的定義 10.1 概概 述述 排序排序是計算機程序設計中的一種重要操作，它的功能是將是計算機程序設計中的一種重要操作，它的功能是將一個數據元素一個數據元素( (或記錄或記錄) )的任

3、意序列，重新排列成一個按關鍵字的任意序列，重新排列成一個按關鍵字有序的序列。排序的目的之一是方便數據查找。有序的序列。排序的目的之一是方便數據查找。 對排序下一個對排序下一個確切的定義確切的定義：假設含假設含n n個記錄的序列為：個記錄的序列為：RR1 1，R R2 2，R Rn n 其相應的關鍵字序列為：其相應的關鍵字序列為：KK1 1，K K2 2，K Kn n 需確定需確定1 1，2 2，n n的一種排列的一種排列p p1 1，p p2 2，p pn n，使其相應，使其相應的關鍵字滿足如下的非遞減的關鍵字滿足如下的非遞減( (或非遞增或非遞增) )關系：關系： KpKp1 1KpKp2

4、2KpKpn n使使RR1 1，R R2 2，R Rn n 成為關鍵字有序的序列：成為關鍵字有序的序列： RpRp1 1，RpRp2 2，RpRpn n 這種操作稱為排序。這種操作稱為排序。 二、一些排序的術語二、一些排序的術語 10.110.1 概概 述述1. 1. 排序方法的穩定與不穩定排序方法的穩定與不穩定 在排序過程中，有若干記錄的在排序過程中，有若干記錄的關鍵字相等關鍵字相等，即，即K Ki i=K=Kj j(1in(1in，1 1jn1 1jn，ij) ij) ，在排序前后，含相等，在排序前后，含相等關鍵字的記錄的相對位置保持不變，即排序前關鍵字的記錄的相對位置保持不變，即排序前R

5、 Ri i在在R Rj j之前，之前，排序后排序后R Ri i仍在仍在R Rj j之前，稱這種排序方法是之前，稱這種排序方法是穩定的穩定的； 反之，若可能使排序后的序列中反之，若可能使排序后的序列中R Ri i在在R Rj j之后，稱所用排之后，稱所用排序方法是序方法是不穩定的不穩定的。 2. 2. 內部排序和外部排序內部排序和外部排序 內部排序內部排序如果在排序過程中，只使用計算機的如果在排序過程中，只使用計算機的內存存放待排序所有記錄，稱這種排序為內部排序。內存存放待排序所有記錄，稱這種排序為內部排序。( (或或對內存中的記錄進行的排序對內存中的記錄進行的排序) )。 外部排序外部排序如果

6、待排序的文件較大，排序期間文如果待排序的文件較大，排序期間文件的全部記錄不能同時存放在計算機的內存里，要借助件的全部記錄不能同時存放在計算機的內存里，要借助計算機的外存才能完成排序，稱之為計算機的外存才能完成排序，稱之為“外部排序外部排序”。 在外部排序過程中，記錄必須在計算機的內存和外在外部排序過程中，記錄必須在計算機的內存和外存之間移動。這樣，內外存之間的數據交換次數就成為存之間移動。這樣，內外存之間的數據交換次數就成為影響外部排序速度的主要因素。影響外部排序速度的主要因素。 二、一些排序的術語二、一些排序的術語 10.110.1 概概 述述3. 3. 排序方法的種類排序方法的種類 (1)

7、(1)按排序過程中依據不同的原則分為五大類：按排序過程中依據不同的原則分為五大類：插入排序、交插入排序、交換排序、選擇排序、歸并排序和基數排序。換排序、選擇排序、歸并排序和基數排序。(2)(2)按時間復雜度劃分為三類按時間復雜度劃分為三類： 簡單排序方法簡單排序方法：其時間復雜度為：其時間復雜度為O(nO(n2 2) )，該方法是，該方法是，屬于簡單排序的排序方法包括：除希爾排序的屬于簡單排序的排序方法包括：除希爾排序的插入排序、冒泡插入排序、冒泡排序和簡單排序。排序和簡單排序。 先進先進( (高效高效) )的排序方法的排序方法：其時間復雜度為：其時間復雜度為O(nlogn)O(nlogn)，

8、屬于，屬于此排序方法的有：此排序方法的有：快速排序、堆排序、歸并排序快速排序、堆排序、歸并排序。其中。其中的排序方法。的排序方法。 基數排序方法基數排序方法：其時間復雜度為：其時間復雜度為O(dO(d* *n)n)，該方法是，該方法是。 二、一些排序的術語二、一些排序的術語 10.110.1 概概 述述 二、一些排序的術語二、一些排序的術語 10.110.1 概概 述述4. 4. 效率分析效率分析 (1)(1)時間復雜度：關鍵字的比較次數和記錄移動次數。時間復雜度：關鍵字的比較次數和記錄移動次數。 (2)(2)空間復雜度：執行算法所需的附加存儲空間。空間復雜度：執行算法所需的附加存儲空間。5

9、5排序的基本操作排序的基本操作 排序的基本操作主要有兩種：排序的基本操作主要有兩種： (1)(1)比較兩個關鍵字大小比較兩個關鍵字大小 (2)(2)根據比較的結果將記錄從一個位置移到另一個位置。根據比較的結果將記錄從一個位置移到另一個位置。 二、一些排序的術語二、一些排序的術語 10.110.1 概概 述述6 6排序記錄的存儲方式排序記錄的存儲方式 (1) (1) 采用順序表，采用順序表，相鄰的記錄，存儲位置也相鄰，記錄相鄰的記錄，存儲位置也相鄰，記錄的次序關系由其存儲位置決定，實現排序必須借助移動記錄。的次序關系由其存儲位置決定，實現排序必須借助移動記錄。 (2) (2) 采用靜態鏈表，采用

10、靜態鏈表，記錄之間的次序關系由指針指示，記錄之間的次序關系由指針指示，則實現排序不需要移動記錄，僅需修改指針即可。這種方式則實現排序不需要移動記錄，僅需修改指針即可。這種方式下實現的排序又稱表排序。下實現的排序又稱表排序。 (3)(3)待排序記錄本身存儲在一組地址連續的存儲單元內，待排序記錄本身存儲在一組地址連續的存儲單元內，同時另設一個指示各記錄存儲位置的地址向量，在排序同時另設一個指示各記錄存儲位置的地址向量，在排序過程過程中不移動記錄本身，而移動地址向量中這些記錄的中不移動記錄本身，而移動地址向量中這些記錄的“地址地址”，在排序結束之后再按照地址向量中的值調整記錄的存儲位置，在排序結束之

11、后再按照地址向量中的值調整記錄的存儲位置，這種方式下實現的排序又稱地址排序。這種方式下實現的排序又稱地址排序。10.2 10.2 插入排序插入排序一、一、插入排序概述插入排序概述二、二、直接插入排序直接插入排序三、三、折半插入排序折半插入排序四、四、希爾排序希爾排序(Shell)(Shell)一、一、插入排序概述插入排序概述1 1插入排序思想插入排序思想 插入排序的基本思想是，每一次只考慮一個待排序的插入排序的基本思想是，每一次只考慮一個待排序的元素，同已排序的元素作比較，在比較完畢之后，把待排序元素，同已排序的元素作比較，在比較完畢之后，把待排序的元素放到合適的位置，然后再選下一個待排序的元

12、素。的元素放到合適的位置，然后再選下一個待排序的元素。10.210.2插插入入排排序序2 2插入排序的基本算法插入排序的基本算法假設所有待排序的元素在數組假設所有待排序的元素在數組rnrn之內。之內。(1)(1)初始狀態初始狀態 排序開始之前，整個數組排序開始之前，整個數組r r被劃分被劃分兩個部分：有序區兩個部分：有序區和無序區。和無序區。 有序區有序區內存放的是已排好順序的元素；內存放的是已排好順序的元素； 無序區無序區內存放的是尚未排好順序的元素內存放的是尚未排好順序的元素。 初始時，有序區只有初始時，有序區只有1 1個元素個元素r1r1。 無序區里的元素是無序區里的元素是r2 r2 r

13、nrn。(2)(2)終態終態 在排序操作完成之后，在有序區中包含整個數組在排序操作完成之后，在有序區中包含整個數組r r，而，而在無序區內則為空。整個狀態稱為終態。在無序區內則為空。整個狀態稱為終態。一、一、插入排序概述插入排序概述10.210.2插插入入排排序序(3)(3)基本操作步驟基本操作步驟a.a.首先從無序區中取一個記錄，通常是第一個記錄；首先從無序區中取一個記錄，通常是第一個記錄；b.b.然后將其同有序區中的元素比較，并按其關鍵字值大然后將其同有序區中的元素比較，并按其關鍵字值大小，把該記錄插入到有序區中的適當位置，這樣有序區小，把該記錄插入到有序區中的適當位置，這樣有序區中始終保

14、持有序性；中始終保持有序性；c.c.再從無序區中取一個記錄，重復再從無序區中取一個記錄，重復b.b.操作，直到終態。操作，直到終態。一、一、插入排序概述插入排序概述10.210.2插插入入排排序序 直接插入排序是一種最簡單的排序方法。它的基本操直接插入排序是一種最簡單的排序方法。它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數增個新的、記錄數增1 1的有序表。的有序表。 1 1排序思想排序思想 2 2算法算法 將序列中的第將序列中的第1 1個記錄看成是一個有序的子序列個記錄看成是一個有序的子序列; ;從第從第2 2個記

15、錄起逐個進行插入，直至整個序列變成按關鍵個記錄起逐個進行插入，直至整個序列變成按關鍵字非遞減有序序列為止。整個排序過程為進行字非遞減有序序列為止。整個排序過程為進行n-1n-1趟插入。趟插入。同時后移記錄。同時后移記錄。二、二、直接排序概述直接排序概述10.210.2插插入入排排序序3 3算法描述算法描述void InsertSort(Sqlist &L)void InsertSort(Sqlist &L) for(i=2;i=L.length;+i) for(i=2;i=L.length;+i) L.r0=L.ri; / L.r0=L.ri; /設置哨兵設置哨兵 for(j=

16、i-1;L.r0.keyL.rj.key;-j)for(j=i-1;L.r0.keyL.rj.key;-j) L.rj+1=L.rj; / L.rj+1=L.rj; /記錄后移記錄后移 L.rj+1=L.r0; /L.rj+1=L.r0; /插入到正確位置插入到正確位置 二、二、直接排序概述直接排序概述10.210.2插插入入排排序序例例1 1 直接插入排序的過程。直接插入排序的過程。初始關鍵字：初始關鍵字： ( (4949) ) 3838 65 97 76 13 27 65 97 76 13 27 4949 i=2: ( i=2: (3838) () (3838 4949) ) 6565 9

17、7 76 13 27 97 76 13 27 4949 i=3: ( i=3: (6565) () (38 4938 49 6565) ) 9797 76 13 27 76 13 27 4949 i=4: ( i=4: (9797) () (38 49 6538 49 65 9797) ) 7676 13 27 13 27 4949 i=5: (i=5: (7676) () (38 49 6538 49 65 7676 97 97) ) 1313 27 27 4949 i=6: ( i=6: (1313) () (1313 38 49 65 76 9738 49 65 76 97) ) 27

18、27 4949 i=7: ( i=7: (2727) () (1313 27 27 38 49 65 76 9738 49 65 76 97) ) 4949 i=8: ( i=8: (4949) () (13 27 38 4913 27 38 49 4949 65 76 9765 76 97) )二、二、直接排序概述直接排序概述10.210.2插插入入排排序序 4. 4. 算法分析算法分析 (1)(1)穩定性穩定性 直接插入排序是直接插入排序是的排序方法。的排序方法。 (2)(2)算法效率算法效率 a.a.時間復雜度時間復雜度 時間復雜度為時間復雜度為。 b.b.空間復雜度空間復雜度 它只需要

19、一個記錄的輔助空間，它只需要一個記錄的輔助空間，O(1)O(1)。 二、二、直接排序概述直接排序概述10.210.2插插入入排排序序三、折半插入排序三、折半插入排序 從減少從減少“比較比較”和和“移動移動”兩種操作的次數考慮，兩種操作的次數考慮，折半插入排序折半插入排序是是直接插入排序直接插入排序的一種改進方法。的一種改進方法。1 1折半插入排序思想折半插入排序思想 由于插入排序的基本操作是在由于插入排序的基本操作是在有序表有序表中進行查找和中進行查找和插入，在有序表中用插入，在有序表中用折半查找折半查找方法可以提高查找效率，方法可以提高查找效率，利用折半查找的方法來進行插入排序可以減少比較次

20、數，利用折半查找的方法來進行插入排序可以減少比較次數，從而提高整個算法的執行效率。從而提高整個算法的執行效率。 10.210.2插插入入排排序序2.2.算法描述算法描述void BInsertSort(Sqlist &L)void BInsertSort(Sqlist &L) for(i=2;i=L.length;+i) for(i=2;i=L.length;+i) L.r0=L.ri; / L.r0=L.ri; /將將L.riL.ri暫存到暫存到L.r0L.r0 low=1;high=i-1;low=1;high=i-1; while(low=high) while(low=

21、high) m=(low+high)/2; m=(low+high)/2; if(L.r0.keyL.rm.key) high=m-1; if(L.r0.key=high+1;-j) for(j=i-1;j=high+1;-j) L.rj+1=L.rj; / L.rj+1=L.rj; /記錄后移記錄后移 L.rhigh+1=L.r0; /L.rhigh+1=L.r0; /插入到正確位置插入到正確位置 三、折半插入排序三、折半插入排序10.210.2插插入入排排序序3 3算法分析算法分析(1)(1)穩定性穩定性折半排序是折半排序是排序方法。排序方法。(2)(2)算法效率算法效率時間復雜度仍為時間

22、復雜度仍為O(nO(n2 2) )。空間復雜度為空間復雜度為O(1)O(1)，附加存儲空間同直接插入排序。，附加存儲空間同直接插入排序。三、折半插入排序三、折半插入排序10.210.2插插入入排排序序四、希爾排序四、希爾排序(Shell)(Shell) 又稱又稱“縮小增量排序縮小增量排序”，屬于插入排序類的方法，但在，屬于插入排序類的方法，但在時間效率上較前幾種排序方法有較大的改進時間效率上較前幾種排序方法有較大的改進。1.1.基本思想基本思想 在直接插入排序中，當在直接插入排序中，當n n較小時，排序的效率比較高。較小時，排序的效率比較高。 希爾排序方法希爾排序方法是先將待排序記錄是先將待排

23、序記錄分割成為若干子序列分割成為若干子序列，分別在分別在子序列中進行直接插入排序子序列中進行直接插入排序，待整個序列中的記錄，待整個序列中的記錄“基本有序基本有序”時，再對全體記錄進行一次直接排序。時，再對全體記錄進行一次直接排序。10.210.2插插入入排排序序 子序的分割不是簡單的子序的分割不是簡單的“逐段分割逐段分割”，而是將待排序，而是將待排序的記錄按照的記錄按照某個增量某個增量d d分成若干子序列，將相隔分成若干子序列，將相隔d d的記錄組的記錄組成一個子序列。在成一個子序列。在子序列中進行直接插入排序子序列中進行直接插入排序。隨著增量。隨著增量d d的逐步變小，各子序列中的記錄逐漸

24、增多，各子序列中的逐步變小，各子序列中的記錄逐漸增多，各子序列中的記錄隨著的記錄隨著d d的減小而趨于有序。當增量減小到的減小而趨于有序。當增量減小到1 1時，已達時，已達到基本有序，再進行直接排序，排序就完成了。到基本有序，再進行直接排序，排序就完成了。 在希爾排序中關鍵字較小的記錄不是一步一步的前移，在希爾排序中關鍵字較小的記錄不是一步一步的前移，而是而是跳躍式的前移跳躍式的前移，因此效率提高。，因此效率提高。 四、希爾排序四、希爾排序(Shell)(Shell)10.210.2插插入入排排序序 2. 2. 算法算法 (1)(1)按距離按距離d d將待排序數組將待排序數組r r 分成若干個

25、小組，等距離分成若干個小組，等距離者在同一個組中，初始距離為者在同一個組中，初始距離為d d1 1； (2)(2)在每個小組中進行直接插入排序；在每個小組中進行直接插入排序； (3)(3)修改距離，選一個小于上次距離修改距離，選一個小于上次距離d d1 1的距離的距離d d2 2； (4)(4)重復重復(1)(1)、(2)(2)和和(3)(3)，直到直到d=1d=1為止為止。四、希爾排序四、希爾排序(Shell)(Shell)10.210.2插插入入排排序序3. 3. 舉例舉例 例例2 2初始關鍵字：初始關鍵字： 49 38 65 97 76 13 27 49 55 04第一次：第一次： d

26、d1 1= = n/2n/2 =5=5分成分成5 5組：組：49,13，38,27，65,49，97,55，76,04各組排序后：各組排序后： 13 27 49 55 04 49 38 65 97 76第二次：第二次：d2= d1/2 =3分成分成3 3組：組：13,55,38,76，27,04,65，49,49,97排序后：排序后： 13 04 49 38 27 49 55 65 97 76第三次：第三次：d d3 3=2=2 分成分成2 2組組：13,49,27,55,97，04,38,49,65,76排序后：排序后：13 04 27 38 49 49 55 65 97 76第四次：第四次

27、：d4=1 04 13 27 38 49 49 55 65 76 97四、希爾排序四、希爾排序(Shell)(Shell)10.210.2插插入入排排序序4 4算法描述算法描述void shellsort(Sqlist &L,int dlta,int t)void shellsort(Sqlist &L,int dlta,int t)/按增量序列按增量序列dlta0t-1 dlta0t-1 對順序表對順序表L L作希爾排序作希爾排序 for(k=0;kt;+k)for(k=0;kt;+k) ShellInsert(L, ShellInsert(L,dltakdltak););

28、void ShellInsert(&L,void ShellInsert(&L,&dk&dk) )for(i=for(i=dkdk+1;i=L.length;+i) +1;i=L.length;+i) /增量是增量是dkdk而不是而不是1 1 if (l.ri.keyL.ri- if (l.ri.key0& (L.r0.key0& (L.r0.keyL.r2L.r1L.r2，則將兩個記錄交換；依次類推，則將兩個記錄交換；依次類推，L.riL.ri與與Li+1Li+1比較，直比較，直至第至第n-1n-1個記錄和第個記錄和第n n個記錄的關鍵字進行比

29、較完畢。個記錄的關鍵字進行比較完畢。 第第1 1趟比較結果將序列中趟比較結果將序列中關鍵字最大關鍵字最大的記錄的記錄放置到最后放置到最后一個位置一個位置，稱為，稱為“沉底沉底”，而，而最小最小的則的則上浮一個位置上浮一個位置，如，如水泡在水中上浮，且水泡在水中上浮，且n n個記錄比較個記錄比較n-1n-1次。次。 第第i i 趟比較，將趟比較，將L.r1L.r1到到L.rn-i+1L.rn-i+1依次比較相鄰兩依次比較相鄰兩個記錄的關鍵字，并在個記錄的關鍵字，并在“逆序逆序”時交換相鄰記錄，結果時交換相鄰記錄，結果n-n-i+1i+1個記錄中關鍵字最大的記錄放置到個記錄中關鍵字最大的記錄放置到

30、n-i+1n-i+1位置上。位置上。 n n個記錄的整個排序過程需進行個記錄的整個排序過程需進行n-1n-1趟冒泡排序。趟冒泡排序。2. 圖示：圖示：第一輪：第一輪：a1 10a2 5a3 8a4 010 5 5 1051080108 810 5 810 0第二輪：第二輪： a1 5a2 8a3 0 10010 0沉低沉低上浮上浮5 58 858080 0 8沉低沉低上浮上浮第三輪：第三輪：a1 5a2 0 0 5結果：結果：a1 a2 a3 a4 0 5 8 104個數比較個數比較3輪輪，n個數比較個數比較n-1輪輪4個數比較個數比較3次次3個數比較個數比較2次次2個數比較個數比較1次次 一

31、、冒泡排序一、冒泡排序10.310.3快快速速排排序序3.算法：算法：main()int a11,i,j,t; printf(“input 10 numbers:n”); for(i=1;i=10;i+) scanf(“%d”,&ai); printf(“n”); for(i=1;i=9;i+) for(j=1;jaj+1) t=aj;aj=aj+1;aj+1=t; printf(“the sorted numbers:n”); for(i=1;i27 i(low) j(high)j一次交換一次交換 27 38 65 97 76 13 49 49 4913jji三次交換三次交換 27

32、38 13 97 76 49 65 494997四次交換四次交換 27 38 13 49 76 97 65 49i=j完成一趟排序完成一趟排序 27 38 13 49 76 97 65 49iijijj 二、快速排序二、快速排序10.310.3快快速速排排序序1 1算法描述算法描述int Partition(Sqlist &L,int low,int high)int Partition(Sqlist &L,int low,int high) pivotkey=L.rlow.key; pivotkey=L.rlow.key;L.r0=L.rlow;L.r0=L.rlow; wh

33、ile(lowhigh) while(lowhigh) while(low=pivotkey) while(low=pivotkey) -high; -high; L.rlow L.rhigh; L.rlow L.rhigh; L.rlow =L.rhigh;L.rlow =L.rhigh; While(lowhigh&L.rlow.key=pivotkey) While(lowhigh&L.rlow.key=pivotkey) +low; +low; L.rlow L.rhigh; L.rlow L.rhigh; L.rhigh=L.rlow;L.rhigh=L.rlow;

34、L.rlow=L.r0;L.rlow=L.r0; return low; return low; 二、快速排序二、快速排序10.310.3快快速速排排序序遞歸的快速排序算法：遞歸的快速排序算法：void Qsort(Sqlist &L,int low,int high)void Qsort(Sqlist &L,int low,int high) if(lowhigh) if(lowhigh) pivotloc=Partition(L,low,high); / pivotloc=Partition(L,low,high); /確定樞軸位置確定樞軸位置 QSort(L,low,pi

35、votloc-1);QSort(L,low,pivotloc-1); Qsort(L,pivotloc+1,high); Qsort(L,pivotloc+1,high); 二、快速排序二、快速排序10.310.3快快速速排排序序 5. 5. 算法分析算法分析 (1)(1)穩定性穩定性 快速排序是快速排序是的排序方法。的排序方法。 (2)(2)時間復雜度時間復雜度 快速排序的時間復雜度為快速排序的時間復雜度為O(nlogn)O(nlogn)數量級。數量級。 (3)(3)空間復雜度空間復雜度 由于快速排序是一個遞歸過程，需一個棧的附加空間，由于快速排序是一個遞歸過程，需一個棧的附加空間，棧的深度

36、為棧的深度為O(logn)O(logn)。 二、快速排序二、快速排序10.310.3快快速速排排序序10.4 10.4 選擇排序選擇排序 一、簡單選擇排序一、簡單選擇排序 二、二、堆排序堆排序 基本思想基本思想 每一次都在數組中選取關鍵字最小的一個記錄，每一次都在數組中選取關鍵字最小的一個記錄，送到已經排好序的記錄序列的后面，直到完成整個排送到已經排好序的記錄序列的后面，直到完成整個排序工作。即每一趟在序工作。即每一趟在n-i+1n-i+1個記錄中選取關鍵字最小個記錄中選取關鍵字最小的記錄作為有序序列中第的記錄作為有序序列中第i i個記錄。個記錄。10.4 10.4 選擇排序選擇排序10.4

37、10.4 選選擇擇排排序序一、簡單選擇排序一、簡單選擇排序1.1.基本思想基本思想 通過通過n-in-i次關鍵字的比較，在次關鍵字的比較，在n-i+1n-i+1個記錄中選出關個記錄中選出關鍵字最小的記錄，并和第鍵字最小的記錄，并和第i i個記錄交換。個記錄交換。2.2.算法描述算法描述void SelectSort(Sqlist &L)void SelectSort(Sqlist &L) for(i=1;iL.length;+i) for(i=1;iL.length;+i) min=i;min=i; for(j=i+1;j=L.length;j+)for(j=i+1;j=L.l

38、ength;j+) if(L.rj.keyL.rmin.key) if(L.rj.keyL.rmin.key) min=j; min=j; if(min!=i) if(min!=i) t=L.rmin; t=L.rmin; L.rmin=L.ri; L.rmin=L.ri; L.ri=t; L.ri=t; 3. 3. 算法分析算法分析(1)(1)穩定性穩定性簡單選擇排序方法是簡單選擇排序方法是。(2)(2)時間復雜度時間復雜度為為O(nO(n2 2) )(3)(3)空間復雜度空間復雜度為為O(1)O(1)。 10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序 1. 1. 樹形選擇排序樹

39、形選擇排序 樹形選擇排序又稱樹形選擇排序又稱錦標賽排序錦標賽排序，是一種按照錦標賽，是一種按照錦標賽的思想進行選擇排序的方法。的思想進行選擇排序的方法。 出發點出發點是利用前一次比較的結果，減少是利用前一次比較的結果，減少“比較比較”的的次數次數。在。在n n個關鍵字中選出最小值，至少進行個關鍵字中選出最小值，至少進行n-1n-1次，次，在在n-1n-1個關鍵字中選擇次小值并非一定要進行個關鍵字中選擇次小值并非一定要進行n-2n-2次比較次比較，若能利用前若能利用前n-1n-1次比較所得信息，則可減少以后各趟選擇次比較所得信息，則可減少以后各趟選擇排序中所用的比較次數。排序中所用的比較次數。

40、每選擇一個次小關鍵字僅需進行每選擇一個次小關鍵字僅需進行 loglog2 2n n ( (樹的深度樹的深度-1)-1)次比較，時間復雜度為次比較，時間復雜度為O(nlogO(nlog2 2n)n)。但所需輔助存儲空間較。但所需輔助存儲空間較多。多。 n-1+(n-1)log2n10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序 2. 2. 堆排序堆排序(1)(1)堆的定義堆的定義 n n個元素的序列個元素的序列kk1 1,k,k2 2,k,kn n ，當且僅當滿足下述關系，當且僅當滿足下述關系時，稱之為堆。時，稱之為堆。 k ki ikk2i 2i k ki ikk2i2i k ki

41、ikk2i+12i+1 k ki ikk2i+12i+1 若將用一維數組存儲的序列看成是若將用一維數組存儲的序列看成是一個完全二叉樹一個完全二叉樹，則，則完全二叉樹中的任意非葉結點的關鍵字值大完全二叉樹中的任意非葉結點的關鍵字值大( (或小或小) )于它的左、于它的左、右孩子結點的值。這種數據結構即為堆。右孩子結點的值。這種數據結構即為堆。或或10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序 10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序22124030343650875087403036341222小頂堆小頂堆大頂堆大頂堆(2)(2)堆排序堆排序 在堆結構中輸出在堆結構

42、中輸出堆頂最小值堆頂最小值( (或最大值或最大值) )后，使得后，使得剩余剩余n-1n-1個元素的序列重又建成一個堆個元素的序列重又建成一個堆，則得到，則得到n n個元個元素中的素中的次小值次小值( (或次大值）或次大值）。如此反復執行，便能得到。如此反復執行，便能得到一個有序序列，這個過程稱為一個有序序列，這個過程稱為堆排序堆排序。 堆排序需解決堆排序需解決兩個問題兩個問題： a. a. 由一個無序序列建成一個堆。由一個無序序列建成一個堆。 b. b. 在輸出堆頂元素之后，調整剩余元素成為一個在輸出堆頂元素之后，調整剩余元素成為一個新的堆。新的堆。10.4 10.4 選選擇擇排排序序 二、堆

43、排序二、堆排序(3)(3)堆排序的算法堆排序的算法a. a. 建立包含建立包含k k1 1,k,k2 2,k,k3 3,k,kn n的堆。的堆。b. b. 輸出堆頂元素，采用輸出堆頂元素，采用堆頂元素堆頂元素R R1 1與最后一個元素與最后一個元素R Rn n交交換，最大換，最大( (或最小或最小) )元素得到正確的排序位置，此時前元素得到正確的排序位置，此時前n-1n-1個元素不再滿足堆的特性，需重建堆。個元素不再滿足堆的特性，需重建堆。 c. c. 在在b.b.之后，新的堆頂之后，新的堆頂( (根結點根結點) )的左、右子樹均為堆，的左、右子樹均為堆，則僅需則僅需自上至下進行調整自上至下進

44、行調整即可。即可。 這個自堆頂至葉子的調整過程為這個自堆頂至葉子的調整過程為“篩選篩選”。 將一個無序序列建堆的過程就是一個反復將一個無序序列建堆的過程就是一個反復“篩選篩選”的的過程。過程。例例3 310.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序例例3 3：對于一個無序序列對于一個無序序列4949，3838，6565，9797，7676，1313，2727，4949 進行堆排序。進行堆排序。 1)1)先建一個完全二叉樹，先建一個完全二叉樹，如圖所示：如圖所示： 2)2)進行反復的進行反復的“篩選篩選”。從最后一個非終端結點從最后一個非終端結點( (第第 n/2n/2 個元素個元素

45、) )開始開始，將此結點與其左、右孩子比較，選出，將此結點與其左、右孩子比較，選出大的或小的作為此結點；依次對其前的非終端結點重復進大的或小的作為此結點；依次對其前的非終端結點重復進行行“篩選篩選”操作。直到第操作。直到第1 1個元素個元素 ( (根結點根結點) )為最大或最小為最大或最小為止，堆建成。為止，堆建成。 10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序3)3)根結點就是排序的最大關鍵字或最小關鍵字，根結點就是排序的最大關鍵字或最小關鍵字，輸出根結輸出根結點，即將點，即將1313和和9797交換交換，再重復進行，再重復進行(2)(2)操作，直到整個序列操作，直到整個序列有

46、序。有序。10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序 產生的是一個遞減序列：產生的是一個遞減序列：9797，7676，6565，4949，4949，3838，2727，1313。 10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序作為小頂堆，產生的是一個遞減序列。作為小頂堆，產生的是一個遞減序列。作為大頂堆，產生的是一個遞增序列。作為大頂堆，產生的是一個遞增序列。(4)(4)算法描述算法描述typedef SqList HeapType;typedef SqList HeapType;void HeapAdjust(HeapType &H,int s,int m

47、)void HeapAdjust(HeapType &H,int s,int m)rc=H.rs;rc=H.rs; for(j=2 for(j=2* *s;j=m;js;j=m;j* *=2) =2) /沿沿keykey較小的孩子結點向下篩選較小的孩子結點向下篩選 if(jm&if(j0;-i) for(i=H.length/2;i0;-i) HeapAdjust(H,i,H.length); HeapAdjust(H,i,H.length); /建小頂堆建小頂堆 for(i=H.length;i1;-i) for(i=H.length;i1;-i) H.r1H.ri; H.r

48、1H.ri; /堆頂記錄和最后一個記錄相互交換堆頂記錄和最后一個記錄相互交換 HeapAdjust(H,1,i-1); HeapAdjust(H,1,i-1); /調整小頂堆，自上而下調整小頂堆，自上而下 (5)(5)算法分析算法分析a.a.堆排序是堆排序是的排序。的排序。b.b.時間復雜度為時間復雜度為O(nlogO(nlog2 2n)n)。c.c.空間復雜度為空間復雜度為O(1)O(1)。10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序 10.5 10.5 歸并排序歸并排序一、一、2-2-路歸并排序思想路歸并排序思想二、二、2-2-路歸并排序的方法路歸并排序的方法三、三、2-2-

49、路歸并步驟路歸并步驟四、算法描述四、算法描述 10.5 10.5 歸并排序歸并排序1 1歸并的含義將兩個或兩個以上的有序序列合并成一個有歸并的含義將兩個或兩個以上的有序序列合并成一個有序序列。序序列。2 2歸并排序就是利用歸并思想實現的排序，把多個有序表歸并排序就是利用歸并思想實現的排序，把多個有序表經過若干次歸并，最終合并成一個有序表。經過若干次歸并，最終合并成一個有序表。3. 3. 對兩個有序序列進行歸并，稱為對兩個有序序列進行歸并，稱為2-2-路歸并。路歸并。 10.5 10.5 歸歸并并排排序序一、一、2-2-路歸并排序思想路歸并排序思想 把一個有把一個有n n個元素的無序表的每一個元

50、素都看成一個元素的無序表的每一個元素都看成一個有序表，個有序表，將兩個有序子表（有序表）合并成一個有將兩個有序子表（有序表）合并成一個有序子表，一次合并完成后，有序子區間的數目減少一序子表，一次合并完成后，有序子區間的數目減少一半，而子表的長度增加一倍，當子表長度從半，而子表的長度增加一倍，當子表長度從1 1增加到增加到n n（元素個數）時，整個子表變為一個，則該子表中的（元素個數）時，整個子表變為一個，則該子表中的有序序列即為我們所需的排序結果。有序序列即為我們所需的排序結果。 (1)(1)將將n n個記錄看成是個記錄看成是n n個長度為個長度為1 1的有序子表；的有序子表；(2)(2) 將

51、兩兩相鄰的有序子表將兩兩相鄰的有序子表n n進行歸并，若進行歸并，若n n為奇數，為奇數，則留下的一個子表直接進入下一次歸并；則留下的一個子表直接進入下一次歸并；(3)(3)重復步驟重復步驟(2)(2)，直到歸并成一個長度為，直到歸并成一個長度為n n的有序表。的有序表。 10.5 10.5 歸歸并并排排序序一、一、2-2-路歸并排序思想路歸并排序思想 例例4 4 給定排序碼給定排序碼4646，5555，1313，4242，9494，0505，1717，7070，二路歸并排序過程如圖所示。二路歸并排序過程如圖所示。 10.5 10.5 歸歸并并排排序序二、二、2-2-路歸并排序方法路歸并排序方

52、法 假設兩個子表為假設兩個子表為R1R1和和R2R2，這兩個子表將被歸并為，這兩個子表將被歸并為T T。歸。歸并過程為：并過程為： 首先把兩個子表為首先把兩個子表為R1R1和和R2R2的第一個元素取出來進行比較；的第一個元素取出來進行比較；(1)(1) 將較小的元素放入將較小的元素放入T T；(2)(2) 取較小元素所在的子表的下一個元素與上一步較大的取較小元素所在的子表的下一個元素與上一步較大的元素比較；元素比較；(3)(3) 重復重復(1)(1)、(2)(2)，直到一個子表中的元素取完為止；，直到一個子表中的元素取完為止；(4)(4) 把還剩有元素的子表中的元素取出，依次放入把還剩有元素的

53、子表中的元素取出，依次放入T T。 10.5 10.5 歸歸并并排排序序三、三、2-2-路歸并排序的步驟路歸并排序的步驟1 12-2-路歸并算法路歸并算法 將有序的將有序的SRi.mSRi.m和和SRm+1.nSRm+1.n歸并為有序序列歸并為有序序列TRi.nTRi.n。void Merge(RcdType SR,RcdType &TR,int i,int void Merge(RcdType SR,RcdType &TR,int i,int m,int n)m,int n) for(j=m+1,k=i;i=m&j=n;+k) for(j=m+1,k=i;i=m&am

54、p;j=n;+k) if LQ(SRi.key,SRj.key) TRk=SRi+; if LQ(SRi.key,SRj.key) TRk=SRi+; else TRk=SRj+; else TRk=SRj+; if(i=m) TRk.n=SRi.m; if(i=m) TRk.n=SRi.m; if(j=n) TRk.n=SRj.n if(j=n) TRk.n=SRj.n 10.5 10.5 歸歸并并排排序序四、算法描述四、算法描述2.2.一趟歸并排序一趟歸并排序 上述算法是將相鄰兩個有序序列上述算法是將相鄰兩個有序序列2-2-路歸并。而一趟歸路歸并。而一趟歸并排序則調用并排序則調用merge

55、merge n/2hn/2h 次，將前后相鄰且長度為次，將前后相鄰且長度為h h的有的有序段進行兩兩歸并，得到前后相鄰、長度為序段進行兩兩歸并，得到前后相鄰、長度為2h2h的有序段。的有序段。3 3歸并排序歸并排序 整個歸并排序就是調用整個歸并排序就是調用“一趟歸并一趟歸并”過程若干次的過過程若干次的過程。第一趟歸并時，有序子表長度為程。第一趟歸并時，有序子表長度為1 1，每趟歸并后有序，每趟歸并后有序子表的長度為上一次長度的子表的長度為上一次長度的2 2倍，當有序子表的長度為倍，當有序子表的長度為n n時，時，2-2-路歸并排序結束。路歸并排序結束。 見圖見圖10.1310.13 10.5

56、10.5 歸歸并并排排序序四、算法描述四、算法描述遞歸算法：遞歸算法：void Msort(RcdType SR,RcdType &TR1,int s,int t)void Msort(RcdType SR,RcdType &TR1,int s,int t) if(s= =t) TR1s=SRs; if(s= =t) TR1s=SRs; else else m=(s+t)/2; m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); MSort(SR,TR2,m+1,t); Merge(TR2,

57、TR1,s,m,t); Merge(TR2,TR1,s,m,t); void MergeSort(SqList &L)void MergeSort(SqList &L) Msort(L.r,L.r,L.length); Msort(L.r,L.r,L.length); 10.5 10.5 歸歸并并排排序序四、算法描述四、算法描述 二路歸并排序的時間復雜度等于歸并趟數與每一趟時二路歸并排序的時間復雜度等于歸并趟數與每一趟時間復雜度的乘積。而間復雜度的乘積。而歸并趟數為歸并趟數為 loglog2 2n n ( (當當 loglog2 2n n 為奇數為奇數時，則為時，則為 logl

58、og2 2n n +1) +1)。因為每一趟歸并就是將兩兩有序子。因為每一趟歸并就是將兩兩有序子表合并成一個有序子表，而每一對有序子表歸并時，記錄表合并成一個有序子表，而每一對有序子表歸并時，記錄的比較次數均小于等于記錄的移動次數（即由一個數組復的比較次數均小于等于記錄的移動次數（即由一個數組復制到另一個數組中的記錄個數），而記錄的移動次數等于制到另一個數組中的記錄個數），而記錄的移動次數等于這一對有序表的長度之和，所以，這一對有序表的長度之和，所以，每一趟歸并的移動次數每一趟歸并的移動次數均等于數組中記錄的個數均等于數組中記錄的個數n n，即每一趟歸并的時間復雜度為，即每一趟歸并的時間復雜度

59、為O(n)O(n)。因此，。因此，二路歸并排序的時間復雜度為二路歸并排序的時間復雜度為O(nlogO(nlog2 2n)n)。 利用二路歸并排序時，需要利用二路歸并排序時，需要利用與待排序數組相同的利用與待排序數組相同的輔助數組作臨時單元輔助數組作臨時單元，故該排序方法的，故該排序方法的空間復雜度為空間復雜度為O(n)O(n)，比前面介紹的其它排序方法占用的空間大。比前面介紹的其它排序方法占用的空間大。 10.5 10.5 歸歸并并排排序序五、算法分析五、算法分析 1 1穩定性穩定性 歸并排序是歸并排序是排序方法。排序方法。 2 2時間復雜度時間復雜度 為為O(nlogO(nlog2 2n)n

60、)。 3 3空間復雜度空間復雜度 為為O(n)O(n)。 10.5 10.5 歸歸并并排排序序五、算法分析五、算法分析 10.6 10.6 基數排序基數排序一、多關鍵字的排序一、多關鍵字的排序二、鏈式基數排序二、鏈式基數排序 10.6 10.6 基數排序基數排序 1. 1.基數排序不用進行記錄關鍵字的比較和交換，基數排序不用進行記錄關鍵字的比較和交換， 而是而是利用關鍵字的結構利用關鍵字的結構，通過，通過“分類分類”和和“收集收集”的辦的辦法法實現排序。實現排序。 2.2.基數排序將基數排序將多關鍵字排序的思想多關鍵字排序的思想用于單邏輯關鍵字用于單邏輯關鍵字的排的排序中。序中。 10.6 10.6 基基數數排排序序一、多關鍵字的排序一、多關鍵字的排序1 1多關鍵字排序思想多關鍵字排序思想 以撲克牌排序為例，討論多關鍵字排序思想。以撲克牌排序為例，討論多關鍵字排序思想。 任何一張撲克牌都有花色和面值兩種屬性，以花色任何一