數(shù)據(jù)結(jié)構(gòu)-內(nèi)部排序

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

2、章 內(nèi)部排序內(nèi)部排序 10.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ù)排序 10.7 10.7 各種排序方法的比較各種排序方法的比較 10.1 10.1 概概 述述一、排序的定義一、排序的定義二、二、一些排序的術(shù)語(yǔ)一些排序的術(shù)語(yǔ)一、一、排序的定義排序的定義 10.1 概概 述述 排序排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素一個(gè)數(shù)據(jù)元素( (或記錄或記錄) )的任

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

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

5、 Ri i在在R Rj j之前，之前，排序后排序后R Ri i仍在仍在R Rj j之前，稱(chēng)這種排序方法是之前，稱(chēng)這種排序方法是穩(wěn)定的穩(wěn)定的； 反之，若可能使排序后的序列中反之，若可能使排序后的序列中R Ri i在在R Rj j之后，稱(chēng)所用排之后，稱(chēng)所用排序方法是序方法是不穩(wěn)定的不穩(wěn)定的。 2. 2. 內(nèi)部排序和外部排序內(nèi)部排序和外部排序 內(nèi)部排序內(nèi)部排序如果在排序過(guò)程中，只使用計(jì)算機(jī)的如果在排序過(guò)程中，只使用計(jì)算機(jī)的內(nèi)存存放待排序所有記錄，稱(chēng)這種排序?yàn)閮?nèi)部排序。內(nèi)存存放待排序所有記錄，稱(chēng)這種排序?yàn)閮?nèi)部排序。( (或或?qū)?nèi)存中的記錄進(jìn)行的排序?qū)?nèi)存中的記錄進(jìn)行的排序) )。 外部排序外部排序如果

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

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

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

9、5排序的基本操作排序的基本操作 排序的基本操作主要有兩種：排序的基本操作主要有兩種： (1)(1)比較兩個(gè)關(guān)鍵字大小比較兩個(gè)關(guān)鍵字大小 (2)(2)根據(jù)比較的結(jié)果將記錄從一個(gè)位置移到另一個(gè)位置。根據(jù)比較的結(jié)果將記錄從一個(gè)位置移到另一個(gè)位置。 二、一些排序的術(shù)語(yǔ)二、一些排序的術(shù)語(yǔ) 10.110.1 概概 述述6 6排序記錄的存儲(chǔ)方式排序記錄的存儲(chǔ)方式 (1) (1) 采用順序表，采用順序表，相鄰的記錄，存儲(chǔ)位置也相鄰，記錄相鄰的記錄，存儲(chǔ)位置也相鄰，記錄的次序關(guān)系由其存儲(chǔ)位置決定，實(shí)現(xiàn)排序必須借助移動(dòng)記錄。的次序關(guān)系由其存儲(chǔ)位置決定，實(shí)現(xiàn)排序必須借助移動(dòng)記錄。 (2) (2) 采用靜態(tài)鏈表，采用

10、靜態(tài)鏈表，記錄之間的次序關(guān)系由指針指示，記錄之間的次序關(guān)系由指針指示，則實(shí)現(xiàn)排序不需要移動(dòng)記錄，僅需修改指針即可。這種方式則實(shí)現(xiàn)排序不需要移動(dòng)記錄，僅需修改指針即可。這種方式下實(shí)現(xiàn)的排序又稱(chēng)表排序。下實(shí)現(xiàn)的排序又稱(chēng)表排序。 (3)(3)待排序記錄本身存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元內(nèi)，待排序記錄本身存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元內(nèi)，同時(shí)另設(shè)一個(gè)指示各記錄存儲(chǔ)位置的地址向量，在排序同時(shí)另設(shè)一個(gè)指示各記錄存儲(chǔ)位置的地址向量，在排序過(guò)程過(guò)程中不移動(dòng)記錄本身，而移動(dòng)地址向量中這些記錄的中不移動(dòng)記錄本身，而移動(dòng)地址向量中這些記錄的“地址地址”，在排序結(jié)束之后再按照地址向量中的值調(diào)整記錄的存儲(chǔ)位置，在排序結(jié)束之

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

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

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

14、持有序性；中始終保持有序性；c.c.再?gòu)臒o(wú)序區(qū)中取一個(gè)記錄，重復(fù)再?gòu)臒o(wú)序區(qū)中取一個(gè)記錄，重復(fù)b.b.操作，直到終態(tài)。操作，直到終態(tài)。一、一、插入排序概述插入排序概述10.210.2插插入入排排序序 直接插入排序是一種最簡(jiǎn)單的排序方法。它的基本操直接插入排序是一種最簡(jiǎn)單的排序方法。它的基本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增個(gè)新的、記錄數(shù)增1 1的有序表。的有序表。 1 1排序思想排序思想 2 2算法算法 將序列中的第將序列中的第1 1個(gè)記錄看成是一個(gè)有序的子序列個(gè)記錄看成是一個(gè)有序的子序列; ;從第從第2 2個(gè)記

15、錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止。整個(gè)排序過(guò)程為進(jìn)行字非遞減有序序列為止。整個(gè)排序過(guò)程為進(jìn)行n-1n-1趟插入。趟插入。同時(shí)后移記錄。同時(shí)后移記錄。二、二、直接排序概述直接排序概述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; /設(shè)置哨兵設(shè)置哨兵 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 直接插入排序的過(guò)程。直接插入排序的過(guò)程。初始關(guān)鍵字：初始關(guān)鍵字： ( (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)穩(wěn)定性穩(wěn)定性 直接插入排序是直接插入排序是的排序方法。的排序方法。 (2)(2)算法效率算法效率 a.a.時(shí)間復(fù)雜度時(shí)間復(fù)雜度 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為。 b.b.空間復(fù)雜度空間復(fù)雜度 它只需要

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

20、數(shù)，利用折半查找的方法來(lái)進(jìn)行插入排序可以減少比較次數(shù)，從而提高整個(gè)算法的執(zhí)行效率。從而提高整個(gè)算法的執(zhí)行效率。 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)穩(wěn)定性穩(wěn)定性折半排序是折半排序是排序方法。排序方法。(2)(2)算法效率算法效率時(shí)間復(fù)雜度仍為時(shí)間

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

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

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

25、小組，等距離分成若干個(gè)小組，等距離者在同一個(gè)組中，初始距離為者在同一個(gè)組中，初始距離為d d1 1； (2)(2)在每個(gè)小組中進(jìn)行直接插入排序；在每個(gè)小組中進(jìn)行直接插入排序； (3)(3)修改距離，選一個(gè)小于上次距離修改距離，選一個(gè)小于上次距離d d1 1的距離的距離d d2 2； (4)(4)重復(fù)重復(fù)(1)(1)、(2)(2)和和(3)(3)，直到直到d=1d=1為止為止。四、希爾排序四、希爾排序(Shell)(Shell)10.210.2插插入入排排序序3. 3. 舉例舉例 例例2 2初始關(guān)鍵字：初始關(guān)鍵字： 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)/按增量序列按增量序列dlta0dlta0t-1 t-1 對(duì)順序表對(duì)順序表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，則將兩個(gè)記錄交換；依次類(lèi)推，則將兩個(gè)記錄交換；依次類(lèi)推，L.riL.ri與與Li+1Li+1比較，直比較，直至第至第n-1n-1個(gè)記錄和第個(gè)記錄和第n n個(gè)記錄的關(guān)鍵字進(jìn)行比

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

30、n-i+1n-i+1位置上。位置上。 n n個(gè)記錄的整個(gè)排序過(guò)程需進(jìn)行個(gè)記錄的整個(gè)排序過(guò)程需進(jì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結(jié)果：結(jié)果：a1 a2 a3 a4 0 5 8 104個(gè)數(shù)比較個(gè)數(shù)比較3輪輪，n個(gè)數(shù)比較個(gè)數(shù)比較n-1輪輪4個(gè)數(shù)比較個(gè)數(shù)比較3次次3個(gè)數(shù)比較個(gè)數(shù)比較2次次2個(gè)數(shù)比較個(gè)數(shù)比較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)穩(wěn)定性穩(wěn)定性 快速排序是快速排序是的排序方法。的排序方法。 (2)(2)時(shí)間復(fù)雜度時(shí)間復(fù)雜度 快速排序的時(shí)間復(fù)雜度為快速排序的時(shí)間復(fù)雜度為O(nlogn)O(nlogn)數(shù)量級(jí)。數(shù)量級(jí)。 (3)(3)空間復(fù)雜度空間復(fù)雜度 由于快速排序是一個(gè)遞歸過(guò)程，需一個(gè)棧的附加空間，由于快速排序是一個(gè)遞歸過(guò)程，需一個(gè)棧的附加空間，棧的深度

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

37、10.4 選選擇擇排排序序一、簡(jiǎn)單選擇排序一、簡(jiǎn)單選擇排序1.1.基本思想基本思想 通過(guò)通過(guò)n-in-i次關(guān)鍵字的比較，在次關(guān)鍵字的比較，在n-i+1n-i+1個(gè)記錄中選出關(guān)個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第鍵字最小的記錄，并和第i i個(gè)記錄交換。個(gè)記錄交換。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)穩(wěn)定性穩(wěn)定性簡(jiǎn)單選擇排序方法是簡(jiǎn)單選擇排序方法是。(2)(2)時(shí)間復(fù)雜度時(shí)間復(fù)雜度為為O(nO(n2 2) )(3)(3)空間復(fù)雜度空間復(fù)雜度為為O(1)O(1)。 10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序 1. 1. 樹(shù)形選擇排序樹(shù)

39、形選擇排序 樹(shù)形選擇排序又稱(chēng)樹(shù)形選擇排序又稱(chēng)錦標(biāo)賽排序錦標(biāo)賽排序，是一種按照錦標(biāo)賽，是一種按照錦標(biāo)賽的思想進(jìn)行選擇排序的方法。的思想進(jìn)行選擇排序的方法。 出發(fā)點(diǎn)出發(fā)點(diǎn)是利用前一次比較的結(jié)果，減少是利用前一次比較的結(jié)果，減少“比較比較”的的次數(shù)次數(shù)。在。在n n個(gè)關(guān)鍵字中選出最小值，至少進(jìn)行個(gè)關(guān)鍵字中選出最小值，至少進(jìn)行n-1n-1次，次，在在n-1n-1個(gè)關(guān)鍵字中選擇次小值并非一定要進(jìn)行個(gè)關(guān)鍵字中選擇次小值并非一定要進(jìn)行n-2n-2次比較次比較，若能利用前若能利用前n-1n-1次比較所得信息，則可減少以后各趟選擇次比較所得信息，則可減少以后各趟選擇排序中所用的比較次數(shù)。排序中所用的比較次數(shù)。

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

41、i ikk2i+12i+1 k ki ikk2i+12i+1 若將用一維數(shù)組存儲(chǔ)的序列看成是若將用一維數(shù)組存儲(chǔ)的序列看成是一個(gè)完全二叉樹(shù)一個(gè)完全二叉樹(shù)，則，則完全二叉樹(shù)中的任意非葉結(jié)點(diǎn)的關(guān)鍵字值大完全二叉樹(shù)中的任意非葉結(jié)點(diǎn)的關(guān)鍵字值大( (或小或小) )于它的左、于它的左、右孩子結(jié)點(diǎn)的值。這種數(shù)據(jù)結(jié)構(gòu)即為堆。右孩子結(jié)點(diǎn)的值。這種數(shù)據(jù)結(jié)構(gòu)即為堆?；蚧?0.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序 10.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序22124030343650875087403036341222小頂堆小頂堆大頂堆大頂堆(2)(2)堆排序堆排序 在堆結(jié)構(gòu)中輸出在堆

42、結(jié)構(gòu)中輸出堆頂最小值堆頂最小值( (或最大值或最大值) )后，使得后，使得剩余剩余n-1n-1個(gè)元素的序列重又建成一個(gè)堆個(gè)元素的序列重又建成一個(gè)堆，則得到，則得到n n個(gè)元個(gè)元素中的素中的次小值次小值( (或次大值）或次大值）。如此反復(fù)執(zhí)行，便能得到。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過(guò)程稱(chēng)為一個(gè)有序序列，這個(gè)過(guò)程稱(chēng)為堆排序堆排序。 堆排序需解決堆排序需解決兩個(gè)問(wèn)題兩個(gè)問(wèn)題： a. a. 由一個(gè)無(wú)序序列建成一個(gè)堆。由一個(gè)無(wú)序序列建成一個(gè)堆。 b. b. 在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆。新的堆。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與最后一個(gè)元素與最后一個(gè)元素R Rn n交交換，最大換，最大( (或最小或最小) )元素得到正確的排序位置，此時(shí)前元素得到正確的排序位置，此時(shí)前n-1n-1個(gè)元素不再滿(mǎn)足堆的特性，需重建堆。個(gè)元素不再滿(mǎn)足堆的特性，需重建堆。 c. c. 在在b.b.之后，新的堆頂之后，新的堆頂( (根結(jié)點(diǎn)根結(jié)點(diǎn)) )的左、右子樹(shù)均為堆，的左、右子樹(shù)均為堆，則僅需則僅需自上至下進(jìn)行調(diào)整自

44、上至下進(jìn)行調(diào)整即可。即可。 這個(gè)自堆頂至葉子的調(diào)整過(guò)程為這個(gè)自堆頂至葉子的調(diào)整過(guò)程為“篩選篩選”。 將一個(gè)無(wú)序序列建堆的過(guò)程就是一個(gè)反復(fù)將一個(gè)無(wú)序序列建堆的過(guò)程就是一個(gè)反復(fù)“篩選篩選”的的過(guò)程。過(guò)程。例例3 310.4 10.4 選選擇擇排排序序 二、堆排序二、堆排序例例3 3：對(duì)于一個(gè)無(wú)序序列對(duì)于一個(gè)無(wú)序序列4949，3838，6565，9797，7676，1313，2727，4949 進(jìn)行堆排序。進(jìn)行堆排序。 1)1)先建一個(gè)完全二叉樹(shù)，先建一個(gè)完全二叉樹(shù)，如圖所示：如圖所示： 2)2)進(jìn)行反復(fù)的進(jìn)行反復(fù)的“篩選篩選”。從最后一個(gè)非終端結(jié)點(diǎn)從最后一個(gè)非終端結(jié)點(diǎn)( (第第 n/2n/2 個(gè)元

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

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

47、nt m)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較小的孩子結(jié)點(diǎn)向下篩選較小的孩子結(jié)點(diǎn)向下篩選 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;

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

49、2-2-路歸并步驟路歸并步驟四、算法描述四、算法描述 10.5 10.5 歸并排序歸并排序1 1歸并的含義將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有歸并的含義將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列。序序列。2 2歸并排序就是利用歸并思想實(shí)現(xiàn)的排序，把多個(gè)有序表歸并排序就是利用歸并思想實(shí)現(xiàn)的排序，把多個(gè)有序表經(jīng)過(guò)若干次歸并，最終合并成一個(gè)有序表。經(jīng)過(guò)若干次歸并，最終合并成一個(gè)有序表。3. 3. 對(duì)兩個(gè)有序序列進(jìn)行歸并，稱(chēng)為對(duì)兩個(gè)有序序列進(jìn)行歸并，稱(chēng)為2-2-路歸并。路歸并。 10.5 10.5 歸歸并并排排序序一、一、2-2-路歸并排序思想路歸并排序思想 把一個(gè)有把一個(gè)有n n個(gè)元素的無(wú)序表的

50、每一個(gè)元素都看成一個(gè)元素的無(wú)序表的每一個(gè)元素都看成一個(gè)有序表，個(gè)有序表，將兩個(gè)有序子表（有序表）合并成一個(gè)有將兩個(gè)有序子表（有序表）合并成一個(gè)有序子表，一次合并完成后，有序子區(qū)間的數(shù)目減少一序子表，一次合并完成后，有序子區(qū)間的數(shù)目減少一半，而子表的長(zhǎng)度增加一倍，當(dāng)子表長(zhǎng)度從半，而子表的長(zhǎng)度增加一倍，當(dāng)子表長(zhǎng)度從1 1增加到增加到n n（元素個(gè)數(shù)）時(shí)，整個(gè)子表變?yōu)橐粋€(gè)，則該子表中的（元素個(gè)數(shù)）時(shí)，整個(gè)子表變?yōu)橐粋€(gè)，則該子表中的有序序列即為我們所需的排序結(jié)果。有序序列即為我們所需的排序結(jié)果。 (1)(1)將將n n個(gè)記錄看成是個(gè)記錄看成是n n個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為1 1的有序子表；的有序子表；(2)(

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

52、并排序方法 假設(shè)兩個(gè)子表為假設(shè)兩個(gè)子表為R1R1和和R2R2，這兩個(gè)子表將被歸并為，這兩個(gè)子表將被歸并為T(mén) T。歸。歸并過(guò)程為：并過(guò)程為： 首先把兩個(gè)子表為首先把兩個(gè)子表為R1R1和和R2R2的第一個(gè)元素取出來(lái)進(jìn)行比較；的第一個(gè)元素取出來(lái)進(jìn)行比較；(1)(1) 將較小的元素放入將較小的元素放入T T；(2)(2) 取較小元素所在的子表的下一個(gè)元素與上一步較大的取較小元素所在的子表的下一個(gè)元素與上一步較大的元素比較；元素比較；(3)(3) 重復(fù)重復(fù)(1)(1)、(2)(2)，直到一個(gè)子表中的元素取完為止；，直到一個(gè)子表中的元素取完為止；(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=

54、m&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.一趟歸并排序一趟歸并排序 上述算法是將相鄰兩個(gè)有序序列上述算法是將相鄰兩個(gè)有序序列2-2-路歸并。而一趟歸路歸并。而一趟歸并排序則調(diào)用并排序則調(diào)用m

55、ergemerge n/2hn/2h 次，將前后相鄰且長(zhǎng)度為次，將前后相鄰且長(zhǎng)度為h h的有的有序段進(jìn)行兩兩歸并，得到前后相鄰、長(zhǎng)度為序段進(jìn)行兩兩歸并，得到前后相鄰、長(zhǎng)度為2h2h的有序段。的有序段。3 3歸并排序歸并排序 整個(gè)歸并排序就是調(diào)用整個(gè)歸并排序就是調(diào)用“一趟歸并一趟歸并”過(guò)程若干次的過(guò)過(guò)程若干次的過(guò)程。第一趟歸并時(shí)，有序子表長(zhǎng)度為程。第一趟歸并時(shí)，有序子表長(zhǎng)度為1 1，每趟歸并后有序，每趟歸并后有序子表的長(zhǎng)度為上一次長(zhǎng)度的子表的長(zhǎng)度為上一次長(zhǎng)度的2 2倍，當(dāng)有序子表的長(zhǎng)度為倍，當(dāng)有序子表的長(zhǎng)度為n n時(shí)，時(shí)，2-2-路歸并排序結(jié)束。路歸并排序結(jié)束。 見(jiàn)圖見(jiàn)圖10.1310.13 1

56、0.5 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(

57、TR2,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 歸歸并并排排序序四、算法描述四、算法描述 二路歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)二路歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)間復(fù)雜度的乘積。而間復(fù)雜度的乘積。而歸并趟數(shù)為歸并趟數(shù)為 loglog2 2n n ( (當(dāng)當(dāng) loglog2 2n n 為奇數(shù)為奇數(shù)時(shí)，則為時(shí)，則為

58、loglog2 2n n +1) +1)。因?yàn)槊恳惶藲w并就是將兩兩有序子。因?yàn)槊恳惶藲w并就是將兩兩有序子表合并成一個(gè)有序子表，而每一對(duì)有序子表歸并時(shí)，記錄表合并成一個(gè)有序子表，而每一對(duì)有序子表歸并時(shí)，記錄的比較次數(shù)均小于等于記錄的移動(dòng)次數(shù)（即由一個(gè)數(shù)組復(fù)的比較次數(shù)均小于等于記錄的移動(dòng)次數(shù)（即由一個(gè)數(shù)組復(fù)制到另一個(gè)數(shù)組中的記錄個(gè)數(shù)），而記錄的移動(dòng)次數(shù)等于制到另一個(gè)數(shù)組中的記錄個(gè)數(shù)），而記錄的移動(dòng)次數(shù)等于這一對(duì)有序表的長(zhǎng)度之和，所以，這一對(duì)有序表的長(zhǎng)度之和，所以，每一趟歸并的移動(dòng)次數(shù)每一趟歸并的移動(dòng)次數(shù)均等于數(shù)組中記錄的個(gè)數(shù)均等于數(shù)組中記錄的個(gè)數(shù)n n，即每一趟歸并的時(shí)間復(fù)雜度為，即每一趟歸并的時(shí)

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

60、2n)n)。 3 3空間復(fù)雜度空間復(fù)雜度 為為O(n)O(n)。 10.5 10.5 歸歸并并排排序序五、算法分析五、算法分析 10.6 10.6 基數(shù)排序基數(shù)排序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序二、鏈?zhǔn)交鶖?shù)排序二、鏈?zhǔn)交鶖?shù)排序 10.6 10.6 基數(shù)排序基數(shù)排序 1. 1.基數(shù)排序不用進(jìn)行記錄關(guān)鍵字的比較和交換，基數(shù)排序不用進(jìn)行記錄關(guān)鍵字的比較和交換， 而是而是利用關(guān)鍵字的結(jié)構(gòu)利用關(guān)鍵字的結(jié)構(gòu)，通過(guò)，通過(guò)“分類(lèi)分類(lèi)”和和“收集收集”的辦的辦法法實(shí)現(xiàn)排序。實(shí)現(xiàn)排序。 2.2.基數(shù)排序?qū)⒒鶖?shù)排序?qū)⒍嚓P(guān)鍵字排序的思想多關(guān)鍵字排序的思想用于單邏輯關(guān)鍵字用于單邏輯關(guān)鍵字的排的排序中。序中。 10.6 10.6 基基數(shù)數(shù)排排序序一、多關(guān)鍵字的排序一、多關(guān)鍵字的排序1 1多關(guān)鍵字排序思想多關(guān)鍵字排序思想 以撲克牌排序?yàn)槔懻摱嚓P(guān)鍵字排序思想。以撲克牌排序?yàn)槔?，討論多關(guān)鍵字排序思想。 任何一張撲克牌都有花色和面值兩種屬性，以花