數(shù)據(jù)結(jié)構(gòu)PPT(第10章排序)

1、安安徽徽理理工工大大學(xué)學(xué)第第10章章 內(nèi)部排序內(nèi)部排序v 理解和熟悉各種內(nèi)部排序的基本思想和過(guò)程；理解和熟悉各種內(nèi)部排序的基本思想和過(guò)程；v 掌握內(nèi)部排序算法的時(shí)間復(fù)雜度的分析方法和結(jié)論；掌握內(nèi)部排序算法的時(shí)間復(fù)雜度的分析方法和結(jié)論；v 要求能根據(jù)各種內(nèi)部排序方法的優(yōu)缺點(diǎn)及不同場(chǎng)合選擇要求能根據(jù)各種內(nèi)部排序方法的優(yōu)缺點(diǎn)及不同場(chǎng)合選擇合適的排序方法。合適的排序方法。學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn)安安徽徽理理工工大大學(xué)學(xué)10.1 概概 述述排序：排序：設(shè)含有設(shè)含有n個(gè)記錄的文件個(gè)記錄的文件R1,R2,.,Rn，其相應(yīng)的關(guān)鍵字為，其相應(yīng)的關(guān)鍵字為 K1，K2，.，Kn ，將記錄按關(guān)鍵字值非遞減（或非遞增）順，將記

2、錄按關(guān)鍵字值非遞減（或非遞增）順序排列的過(guò)程，稱(chēng)為排序。序排列的過(guò)程，稱(chēng)為排序。 對(duì)所有的對(duì)所有的Ki=Kj （ij），若排序前），若排序前Ri領(lǐng)先于領(lǐng)先于Rj，排序后，排序后Ri仍仍領(lǐng)先于領(lǐng)先于Rj，則稱(chēng)該排序方法是，則稱(chēng)該排序方法是穩(wěn)定的穩(wěn)定的，反之稱(chēng)為，反之稱(chēng)為不穩(wěn)定的不穩(wěn)定的。內(nèi)部排序：內(nèi)部排序：待排序文件的全部記錄存放在內(nèi)存進(jìn)行的排序，稱(chēng)待排序文件的全部記錄存放在內(nèi)存進(jìn)行的排序，稱(chēng)為內(nèi)部排序。為內(nèi)部排序。外部排序：外部排序：排序過(guò)程中需要進(jìn)行內(nèi)外存數(shù)據(jù)交換的排序，稱(chēng)為排序過(guò)程中需要進(jìn)行內(nèi)外存數(shù)據(jù)交換的排序，稱(chēng)為外部排序。外部排序。安安徽徽理理工工大大學(xué)學(xué)10.1 概概 述述在排序過(guò)程

3、中，通常進(jìn)行兩種基本操作：在排序過(guò)程中，通常進(jìn)行兩種基本操作：（1）比較兩個(gè)關(guān)鍵字大?。唬┍容^兩個(gè)關(guān)鍵字大??；（2）將記錄從一個(gè)位置移到另一個(gè)位置。）將記錄從一個(gè)位置移到另一個(gè)位置。約定：約定：v 待排序的一組記錄存放在地址連續(xù)的一組存儲(chǔ)單元中，它類(lèi)待排序的一組記錄存放在地址連續(xù)的一組存儲(chǔ)單元中，它類(lèi)似于線性表的順序存儲(chǔ)結(jié)構(gòu)。似于線性表的順序存儲(chǔ)結(jié)構(gòu)。v 待排的記錄的數(shù)據(jù)類(lèi)型定義如下：待排的記錄的數(shù)據(jù)類(lèi)型定義如下：typedef struct int key; InfoType otherinfo; RedType;typedef struct RedType rMAXSIZE + 1 ; i

4、nt length; SqList;安安徽徽理理工工大大學(xué)學(xué)10.2 插入排序插入排序10.2.1 直接插入排序直接插入排序基本思想：將一個(gè)記錄插入到已排好序的有序表中，得到一個(gè)新基本思想：將一個(gè)記錄插入到已排好序的有序表中，得到一個(gè)新的、記錄數(shù)增的、記錄數(shù)增1的有序表。的有序表。例如：已知待排序的一組記錄為例如：已知待排序的一組記錄為49、38、65、97、40、13、27。假設(shè)在排序過(guò)程中，前假設(shè)在排序過(guò)程中，前4個(gè)記錄已按關(guān)鍵字遞增的次序重新排列，個(gè)記錄已按關(guān)鍵字遞增的次序重新排列，構(gòu)成一個(gè)含構(gòu)成一個(gè)含4個(gè)記錄的有序序列個(gè)記錄的有序序列38，49，65，97 ，現(xiàn)要將關(guān)鍵，現(xiàn)要將關(guān)鍵字為

5、字為40的記錄插入該序列中，則按從后向前的順序?qū)υ撔蛄羞M(jìn)行的記錄插入該序列中，則按從后向前的順序?qū)υ撔蛄羞M(jìn)行查找，由于查找，由于38 40 49，則，則76應(yīng)插入到應(yīng)插入到65和和97之間，從而得到之間，從而得到新的有序序列新的有序序列 38，40，49，65，97 ，稱(chēng)該過(guò)程為，稱(chēng)該過(guò)程為一趟直接插一趟直接插入排序入排序。安安徽徽理理工工大大學(xué)學(xué)q 直接插入排序方法直接插入排序方法方法：方法：將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，從第將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞

6、減有序序列為止。有序序列為止。Status InsertSort ( SqList &L ) for( i=2; i=L.length; +i ) if( LT( L.ri.key, L.ri-1.key ) ) L.r0 = L.ri; /復(fù)制為哨兵復(fù)制為哨兵 L.ri = L.ri-1; for( j=i-2; LT( L.r0.key, L.rj.key ); -j ) L.rj+1 = L.rj; /記錄后移記錄后移 L.rj+1 = L.r0; /插入到正確位置插入到正確位置 /InsertSort安安徽徽理理工工大大學(xué)學(xué)L.r0 初始關(guān)鍵字初始關(guān)鍵字： （49） 38 65

7、 97 76 13 27 49*i=2： （38）（）（38 49） 65 97 76 13 27 49*i=3： （65）（）（38 49 65） 97 76 13 27 49*i=4： （97）（）（38 49 65 97） 76 13 27 49*i=5： （76）（）（38 49 65 76 97）13 27 49*i=6： （13）（）（13 38 49 65 76 97） 27 49*i=7： （27）（）（13 27 38 49 65 76 97）49*i=8： （49）（）（13 27 48 49 49* 65 76 97）q 直接插入排序示例直接插入排序示例安安徽徽理理工工大

8、大學(xué)學(xué) 對(duì)于排序的效率分析，主要從對(duì)于排序的效率分析，主要從比較次數(shù)比較次數(shù)和和移動(dòng)次數(shù)移動(dòng)次數(shù)兩兩方面著手。方面著手。 直接插入排序的效率與待排文件的關(guān)鍵字排列有關(guān)，直接插入排序的效率與待排文件的關(guān)鍵字排列有關(guān)，最好情況為最好情況為O(n)，最壞情況為，最壞情況為O(n2)。 直接插入排序的平均時(shí)間復(fù)雜度為直接插入排序的平均時(shí)間復(fù)雜度為O(n2)。 直接插入排序是穩(wěn)定的。直接插入排序是穩(wěn)定的。q 直接插入排序效率分析直接插入排序效率分析安安徽徽理理工工大大學(xué)學(xué)基本思想基本思想 ：設(shè)在順序表中有一：設(shè)在順序表中有一 個(gè)對(duì)象序列個(gè)對(duì)象序列 V0, V1, , Vn-1。其中。其中, V0, V1

9、, , Vi-1 是已經(jīng)排好序的對(duì)象是已經(jīng)排好序的對(duì)象。在插入。在插入Vi 時(shí)時(shí), 利用折半搜索法尋找利用折半搜索法尋找Vi 的插入位置。的插入位置。10.2.2 折半插入排序折半插入排序安安徽徽理理工工大大學(xué)學(xué)void BInsertSort(SqList &L) for (i=2;i=L.length;+i) L.r0=L.ri; low = 1; high=i-1; while (low =high+1;-j) L.rj+1=L.rj; L.rhigh+1=L.r0; 和直接插入排序相和直接插入排序相比，折半插入排序僅比，折半插入排序僅減少了比較次數(shù)，而減少了比較次數(shù)，而記錄的移

10、動(dòng)次不變。記錄的移動(dòng)次不變。其時(shí)間復(fù)雜度仍為其時(shí)間復(fù)雜度仍為O(n2)。q 折半插入排序算法折半插入排序算法安安徽徽理理工工大大學(xué)學(xué) 基本思想：希爾排序先將整個(gè)待排元素序列分割成若干個(gè)子序基本思想：希爾排序先將整個(gè)待排元素序列分割成若干個(gè)子序列（列（由相隔某個(gè)由相隔某個(gè)“增量增量”的元素組成的的元素組成的）分別進(jìn)行直接插入排）分別進(jìn)行直接插入排序，待整個(gè)序列中的元素基本有序時(shí)，再對(duì)全體元素進(jìn)行一次序，待整個(gè)序列中的元素基本有序時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排

11、序在時(shí)間效率（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率上比前一種方法有較大提高。上比前一種方法有較大提高。 1. 若待排序文件若待排序文件基本有序基本有序，即文件中具有特性：，即文件中具有特性： ri.keyMaxrj （其中（其中1ji）的記錄數(shù)較少，）的記錄數(shù)較少， 則文件中則文件中大多數(shù)記錄都不需要進(jìn)行插入。大多數(shù)記錄都不需要進(jìn)行插入。 2. 基本有序時(shí)，直接插入排序效率可以提高，接近于基本有序時(shí)，直接插入排序效率可以提高，接近于O(n) 。10.2.3 希爾排序希爾排序安安徽徽理理工工大大學(xué)學(xué)例如，例如，n=8，數(shù)組，數(shù)組R的八個(gè)元素分別為：的八個(gè)元素分別為：17，3，30

12、，25，14，17*，20，9。下面給出希爾排序算法的執(zhí)行過(guò)程。下面給出希爾排序算法的執(zhí)行過(guò)程。初始狀態(tài)：初始狀態(tài)：d=4 17 3 30 25 14 17* 20 9第一趟結(jié)果：第一趟結(jié)果：d=2 14 3 20 9 17 17* 30 25第二趟結(jié)果：第二趟結(jié)果：d=1 14 3 17 9 20 17* 30 35第三趟結(jié)果：第三趟結(jié)果： 3 9 14 17 17* 20 30 35q 希爾排序示例希爾排序示例安安徽徽理理工工大大學(xué)學(xué)void ShellInsert(SqList &L, int dk) for (i=dk+1;i0 & LT(L.r0.key,L.rj.k

13、ey); j-=dk) L.rj+gap=L.rj;L.rj+gap=L.r0; void ShellSort(SqList &L, int dlta ,int t) for (int k=0;kt;+k) ShellInsert(L,dltak); q 希爾排序算法希爾排序算法安安徽徽理理工工大大學(xué)學(xué)v 對(duì)希爾排序的分析提出了許多困難的數(shù)學(xué)問(wèn)題，特別是如何對(duì)希爾排序的分析提出了許多困難的數(shù)學(xué)問(wèn)題，特別是如何選擇增量序列才能產(chǎn)生最好的排序效果，至今沒(méi)有得到解決。選擇增量序列才能產(chǎn)生最好的排序效果，至今沒(méi)有得到解決。 為什么希爾排序的時(shí)間性能優(yōu)于直接插入排序呢？當(dāng)文件為什么希爾排序的時(shí)間

14、性能優(yōu)于直接插入排序呢？當(dāng)文件初基本有序時(shí)直接插入排序所需的比較和移動(dòng)次數(shù)均較少。另初基本有序時(shí)直接插入排序所需的比較和移動(dòng)次數(shù)均較少。另一面，當(dāng)一面，當(dāng)n值較小時(shí)，值較小時(shí)，n和和n2的差別也較小，即直接插入排序的的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度O(n2)差別不大。在希爾差別不大。在希爾排序時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直排序時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來(lái)增量接插入較快，后來(lái)增量di逐漸縮小，分組數(shù)逐漸減少，而各組逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于文

15、件較近于有序狀態(tài)，所以新的的記錄數(shù)目逐漸增多，但由于文件較近于有序狀態(tài)，所以新的一趟排序過(guò)程也較快。因此，希爾排序在效率上較直接接入排一趟排序過(guò)程也較快。因此，希爾排序在效率上較直接接入排序有較大的改進(jìn)。它的時(shí)間復(fù)雜度為序有較大的改進(jìn)。它的時(shí)間復(fù)雜度為O(n1.3)。q 希爾排序性能分析希爾排序性能分析安安徽徽理理工工大大學(xué)學(xué)1. 子文件（子序列）的構(gòu)成不是簡(jiǎn)單地子文件（子序列）的構(gòu)成不是簡(jiǎn)單地“逐段分割逐段分割”，而是將，而是將相隔某個(gè)相隔某個(gè)“增量增量”的記錄組成一個(gè)子文件。的記錄組成一個(gè)子文件。2. 增量序列應(yīng)是遞減，且最后一個(gè)必須為增量序列應(yīng)是遞減，且最后一個(gè)必須為1。3. 希爾排序法

16、是不穩(wěn)定的（由于希爾排序?qū)γ總€(gè)子序列單獨(dú)比希爾排序法是不穩(wěn)定的（由于希爾排序?qū)γ總€(gè)子序列單獨(dú)比較，在比較時(shí)進(jìn)行元素移動(dòng)，有可能改變相同關(guān)鍵字元素的原較，在比較時(shí)進(jìn)行元素移動(dòng)，有可能改變相同關(guān)鍵字元素的原始順序，因此希爾排序是不穩(wěn)定的）。始順序，因此希爾排序是不穩(wěn)定的）。q 希爾排序特點(diǎn)希爾排序特點(diǎn)安安徽徽理理工工大大學(xué)學(xué)10.3 快速排序快速排序1. 起泡排序起泡排序基本思想：基本思想：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二個(gè)進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄和第三個(gè)記

17、錄的關(guān)鍵字。依次類(lèi)推，直至第記錄和第三個(gè)記錄的關(guān)鍵字。依次類(lèi)推，直至第n-1個(gè)記錄和第個(gè)記錄和第n個(gè)記錄的關(guān)鍵字進(jìn)行過(guò)比較為止。上述過(guò)程稱(chēng)作個(gè)記錄的關(guān)鍵字進(jìn)行過(guò)比較為止。上述過(guò)程稱(chēng)作第一趟起泡第一趟起泡排序排序，其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個(gè)記錄的，其結(jié)果使得關(guān)鍵字最大的記錄被安置到最后一個(gè)記錄的位置上。然后進(jìn)行第二趟起泡排序，對(duì)前位置上。然后進(jìn)行第二趟起泡排序，對(duì)前n-1個(gè)記錄進(jìn)行同樣操個(gè)記錄進(jìn)行同樣操作，其結(jié)果使得關(guān)鍵字次大的記錄被安置到第作，其結(jié)果使得關(guān)鍵字次大的記錄被安置到第n-1個(gè)記錄的位置個(gè)記錄的位置上。第上。第i趟起泡排序是從趟起泡排序是從L.r1到到L.rn-i+1

18、依次比較相鄰兩個(gè)記依次比較相鄰兩個(gè)記錄的關(guān)鍵字，并在逆序時(shí)交換到第錄的關(guān)鍵字，并在逆序時(shí)交換到第n-i+1的位置上。判別起泡排的位置上。判別起泡排序結(jié)束條件是：序結(jié)束條件是：在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作。在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作。安安徽徽理理工工大大學(xué)學(xué)初始關(guān)鍵字：初始關(guān)鍵字： 49 38 65 97 76 13 27 49第一趟排序后：第一趟排序后：38 49 65 76 13 27 49 97第二趟排序后：第二趟排序后：38 49 65 13 27 49 76第三趟排序后：第三趟排序后：38 49 13 27 49 65第四趟排序后：第四趟排序后：38 13 2

19、7 49 49第五趟排序后：第五趟排序后：13 27 38 49第六趟排序后：第六趟排序后：13 27 38q 起泡排序示例起泡排序示例安安徽徽理理工工大大學(xué)學(xué)void BubbleSort(SqList &L) int i, j, tag; j = L.length-1; do tag=1; for(i=1; i=j; i+) if( L.ri+1.key L.ri.key ) L.r0= L.ri+1; L.ri+1= L.ri; L.ri= L.r0; tag=0; if( !tag ) j-; while( !tag &j ); return; q 起泡排序算法起泡排序

20、算法安安徽徽理理工工大大學(xué)學(xué) 在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，做只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵字比較，不移動(dòng)對(duì)象。這是最次關(guān)鍵字比較，不移動(dòng)對(duì)象。這是最好的情形。好的情形。 最壞的情形是算法執(zhí)行了最壞的情形是算法執(zhí)行了n-1趟起泡，第趟起泡，第 i 趟趟 (1 in) 做了做了 n- i 次關(guān)鍵字比較，執(zhí)行了次關(guān)鍵字比較，執(zhí)行了n-i 次對(duì)象交換?？偟臅r(shí)間復(fù)雜度為次對(duì)象交換?？偟臅r(shí)間復(fù)雜度為O(n2)。 起泡排序是一個(gè)穩(wěn)定的排序方法。起泡排序是一個(gè)穩(wěn)定的排序方法。q 起泡排序算法分析起泡排序算法分析安安

21、徽徽理理工工大大學(xué)學(xué)v 基本思想：基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。v 一趟快速排序：一趟快速排序：首先選取一個(gè)記錄（通常選取第一個(gè)記錄）首先選取一個(gè)記錄（通常選取第一個(gè)記錄）作為界點(diǎn)，然后將所有關(guān)鍵字較它小的記錄都安置在它的位置作為界點(diǎn)，然后將所有關(guān)鍵字較它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較它大的記錄都安置在它的位

22、置之后。由之前，將所有關(guān)鍵字較它大的記錄都安置在它的位置之后。由此以該此以該“界點(diǎn)界點(diǎn)”記錄最后所落的位置記錄最后所落的位置i為分界線，將整個(gè)序列分為分界線，將整個(gè)序列分割成兩個(gè)子序列。割成兩個(gè)子序列。 然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止。對(duì)象都排在相應(yīng)位置上為止。2. 快速排序快速排序安安徽徽理理工工大大學(xué)學(xué)v 附設(shè)兩個(gè)指針附設(shè)兩個(gè)指針low和和high，其初值分別指向數(shù)組的單元，其初值分別指向數(shù)組的單元1和單和單元元n。選擇第一個(gè)記錄為界點(diǎn)，其關(guān)鍵字為。選擇第一個(gè)記錄為界點(diǎn)，其關(guān)鍵字為pivotkey

23、。將。將pivotkey復(fù)制到復(fù)制到r0中，從中，從high所指的位置起向前搜索找到第一所指的位置起向前搜索找到第一個(gè)關(guān)鍵字小于個(gè)關(guān)鍵字小于pivotkey的記錄復(fù)制到的記錄復(fù)制到low所指位置中，然后從所指位置中，然后從low所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于pivotkey的記的記錄復(fù)制到錄復(fù)制到high所指位置中，重復(fù)這兩步直到所指位置中，重復(fù)這兩步直到lowhigh為止。為止。v快速排序是對(duì)冒泡排序的一種改進(jìn)方法，算法中元素的比較快速排序是對(duì)冒泡排序的一種改進(jìn)方法，算法中元素的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的元素一次就能夠和交換

24、是從兩端向中間進(jìn)行的，關(guān)鍵字較大的元素一次就能夠交換到后面單元，關(guān)鍵字較小的記錄一次就能夠交換到前面單交換到后面單元，關(guān)鍵字較小的記錄一次就能夠交換到前面單元，記錄每次移動(dòng)的距離較遠(yuǎn)，因而總的比較和移動(dòng)次數(shù)較少。元，記錄每次移動(dòng)的距離較遠(yuǎn)，因而總的比較和移動(dòng)次數(shù)較少。q 具體做法具體做法安安徽徽理理工工大大學(xué)學(xué) 0 1 2 3 4 5 6 7 82738659776132749*第一次交換第一次交換lowhigh49 0 1 2 3 4 5 6 7 82738659776136549*第二次交換第二次交換lowhigh49q 具體實(shí)現(xiàn)過(guò)程具體實(shí)現(xiàn)過(guò)程 0 1 2 3 4 5 6 7 84938

25、659776132749*初始關(guān)鍵字初始關(guān)鍵字pivotkeylowhigh49安安徽徽理理工工大大學(xué)學(xué) 0 1 2 3 4 5 6 7 82738139776136549*第三次交換第三次交換lowhigh49 0 1 2 3 4 5 6 7 82738139776976549*第四次交換第四次交換lowhigh49 0 1 2 3 4 5 6 7 82738134976976549*第一趟完成第一趟完成low high49q 具體實(shí)現(xiàn)過(guò)程具體實(shí)現(xiàn)過(guò)程 0 1 2 3 4 5 6 7 82738659776136549*第二次交換第二次交換lowhigh49安安徽徽理理工工大大學(xué)學(xué)q 快速排

26、序全過(guò)程快速排序全過(guò)程 初始狀態(tài)初始狀態(tài) 49 38 65 97 76 13 27 49 一趟快速排序后一趟快速排序后 27 38 13 49 76 97 65 49 分別進(jìn)行快速排序分別進(jìn)行快速排序 13 27 38 結(jié)束結(jié)束結(jié)束結(jié)束 49 65 76 97 49 65 結(jié)束結(jié)束結(jié)束結(jié)束 有序序列有序序列 13 27 38 49 49 65 76 97 整個(gè)快速排序過(guò)程可整個(gè)快速排序過(guò)程可遞歸進(jìn)行遞歸進(jìn)行安安徽徽理理工工大大學(xué)學(xué) int Partition(SqList &L, int low, int high) L.r0 = L.rlow; pivotkey = L.rlow.k

27、ey; while (low high) while (low= pivotkey) -high; L.rlow = L.rhigh; while (lowhigh & L.rlow.key = pivotkey) +low; L.rhigh = L.rlow; L.rlow=L.r0; return low; q 一趟快速排序算法實(shí)現(xiàn)一趟快速排序算法實(shí)現(xiàn)安安徽徽理理工工大大學(xué)學(xué)void QSort(SqList &L, int low, int high) if (low high) pivotloc = Partition(L,low,high); QSort(L,low,

28、 pivotloc-1); QSort(L,pivotloc+1, high); void QuickSort(SqList &L) QSort(L,1,L.length); q 遞歸形式的快速排序算法遞歸形式的快速排序算法安安徽徽理理工工大大學(xué)學(xué) 從時(shí)間上看，快速排序平均計(jì)算時(shí)間是從時(shí)間上看，快速排序平均計(jì)算時(shí)間是O(nlog2n)。實(shí)。實(shí)驗(yàn)結(jié)果表明驗(yàn)結(jié)果表明: 就平均計(jì)算時(shí)間而言就平均計(jì)算時(shí)間而言, 快速排序是所有內(nèi)排序快速排序是所有內(nèi)排序方法中最好的一個(gè)。在最壞的情況方法中最好的一個(gè)。在最壞的情況, 即待排序?qū)ο笮蛄幸鸭创判驅(qū)ο笮蛄幸呀?jīng)按其排序碼從小到大排好序的情況下，其時(shí)間復(fù)

29、雜度為經(jīng)按其排序碼從小到大排好序的情況下，其時(shí)間復(fù)雜度為O(n2)。 從空間上看，快速排序是遞歸的，最大遞歸調(diào)用層次從空間上看，快速排序是遞歸的，最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的高度一致，理想情況為數(shù)與遞歸樹(shù)的高度一致，理想情況為 log2(n+1) 。因此，。因此，要求存儲(chǔ)開(kāi)銷(xiāo)為要求存儲(chǔ)開(kāi)銷(xiāo)為 O(log2n)。 快速排序是一種不穩(wěn)定的排序方法?？焖倥判蚴且环N不穩(wěn)定的排序方法。q 算法分析算法分析安安徽徽理理工工大大學(xué)學(xué)10.4 選擇排序選擇排序選擇排序的基本思想是：選擇排序的基本思想是： 每一趟每一趟 (例如第例如第 i 趟，趟，i = 1, , n-1) 在后面的在后面的 n-i+1 個(gè)待排

30、序?qū)ο笾羞x出關(guān)鍵字最小的對(duì)象，作為有序?qū)ο笮騻€(gè)待排序?qū)ο笾羞x出關(guān)鍵字最小的對(duì)象，作為有序?qū)ο笮蛄械牡诹械牡?i 個(gè)對(duì)象。待到第個(gè)對(duì)象。待到第 n-1 趟作完，待排序?qū)ο笾皇Ｏ绿俗魍?，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。個(gè)，就不用再選了。安安徽徽理理工工大大學(xué)學(xué)1.1.簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序v 基本步驟為：基本步驟為：i從從1開(kāi)始，直到開(kāi)始，直到n-1，進(jìn)行，進(jìn)行n-1趟排序，第趟排序，第i 趟的趟的排序過(guò)程為：排序過(guò)程為： 在一組對(duì)象在一組對(duì)象rirn（i=1,2,n-1）中選擇具有）中選擇具有最小關(guān)鍵字的對(duì)象，并和第最小關(guān)鍵字的對(duì)象，并和第 i 個(gè)對(duì)象進(jìn)行交換。個(gè)對(duì)象進(jìn)行交換。void S

31、electSort( SqList &L ) for( i =1; i L.length; +i ) j = SelectMinKey( L, i ); if ( i != j ) L.ri L.rj; /SelectSort安安徽徽理理工工大大學(xué)學(xué)q 算法分析算法分析 直接選擇排序的排序碼比較次數(shù)與對(duì)象的初始排列無(wú)關(guān)。設(shè)直接選擇排序的排序碼比較次數(shù)與對(duì)象的初始排列無(wú)關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏姓麄€(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象個(gè)對(duì)象, 則第則第 i 趟選擇具有最小排序碼趟選擇具有最小排序碼對(duì)象所需的比較次數(shù)總是對(duì)象所需的比較次數(shù)總是 n-i-1 次?？偟呐判虼a比較次數(shù)為次。總的排序碼比較

32、次數(shù)為n(n-1)/2。 對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其排序碼從小到大有序的時(shí)候初始狀態(tài)是按其排序碼從小到大有序的時(shí)候, 對(duì)象的移動(dòng)次數(shù)為對(duì)象的移動(dòng)次數(shù)為0，達(dá)到最少。達(dá)到最少。 最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為 3(n-1)。 直接選擇排序是一種不穩(wěn)定的排序方法。直接選擇排序是一種不穩(wěn)定的排序方法。安安徽徽理理工工大大學(xué)學(xué)2.2.堆排序堆排序堆的定義：堆的定義：n個(gè)元素的序列個(gè)元素的序列 k1，k2，kn ，當(dāng)且僅當(dāng)滿(mǎn)足，當(dāng)且僅當(dāng)滿(mǎn)足以下關(guān)系

33、時(shí)：以下關(guān)系時(shí)： ki = k2i ki = k2i+1 其中其中i=1，2， n/2 ，則稱(chēng)此則稱(chēng)此n個(gè)元素的關(guān)鍵字個(gè)元素的關(guān)鍵字k1，k2，kn為一個(gè)堆。為一個(gè)堆。 解釋?zhuān)航忉專(zhuān)喝绻対M(mǎn)足以上條件的元素序列如果讓滿(mǎn)足以上條件的元素序列 k1，k2，kn 順順次排成一棵完全二叉樹(shù)，則此樹(shù)的特點(diǎn)是：次排成一棵完全二叉樹(shù)，則此樹(shù)的特點(diǎn)是： 樹(shù)中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹(shù)的根樹(shù)中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹(shù)的根結(jié)點(diǎn)（即堆頂）必最大（或最?。?。結(jié)點(diǎn)（即堆頂）必最大（或最?。?。 或或安安徽徽理理工工大大學(xué)學(xué)q 大根堆和小根堆大根堆和小根堆（a）小根堆）小根堆 （b）大

34、根堆）大根堆09651723 45 78 87533187537845 65 09 311723（09,17,65,23,45,78,87,53,31） （87,78,53,45,65,09,31,17,23）安安徽徽理理工工大大學(xué)學(xué) 以初始關(guān)鍵字序列，建立堆；以初始關(guān)鍵字序列，建立堆； 輸出堆頂元素；輸出堆頂元素； 調(diào)整余下的元素，使其成為一個(gè)新堆；調(diào)整余下的元素，使其成為一個(gè)新堆； 重復(fù)、重復(fù)、 n 次，得到次，得到 一個(gè)有序序列。一個(gè)有序序列。關(guān)鍵要解決和，即：關(guān)鍵要解決和，即：如何由一個(gè)無(wú)序序列如何由一個(gè)無(wú)序序列建成一個(gè)堆？建成一個(gè)堆？如何在輸出堆頂元素如何在輸出堆頂元素之后調(diào)整剩余元

35、素成之后調(diào)整剩余元素成為一個(gè)新的堆？為一個(gè)新的堆？q 堆排序基本思想堆排序基本思想安安徽徽理理工工大大學(xué)學(xué)v 調(diào)整方法調(diào)整方法（以小根堆為例）（以小根堆為例）13273849 76 65 499797273849 76 65 491327973849 76 65 491327493849 76 65 9713 將堆頂元素和堆的最后一個(gè)元素位置交換；將堆頂元素和堆的最后一個(gè)元素位置交換； 然后以當(dāng)前堆頂元素和其左、右子樹(shù)的根結(jié)然后以當(dāng)前堆頂元素和其左、右子樹(shù)的根結(jié)點(diǎn)進(jìn)行比較（此時(shí)，左、右子樹(shù)均為堆），并點(diǎn)進(jìn)行比較（此時(shí)，左、右子樹(shù)均為堆），并與值較小的結(jié)點(diǎn)進(jìn)行交換；與值較小的結(jié)點(diǎn)進(jìn)行交換； 重復(fù)

36、，繼續(xù)調(diào)整被交換過(guò)的子樹(shù)，直到葉重復(fù)，繼續(xù)調(diào)整被交換過(guò)的子樹(shù)，直到葉結(jié)點(diǎn)或沒(méi)進(jìn)行交換為止。稱(chēng)這個(gè)調(diào)整過(guò)程為結(jié)點(diǎn)或沒(méi)進(jìn)行交換為止。稱(chēng)這個(gè)調(diào)整過(guò)程為篩篩選選。 安安徽徽理理工工大大學(xué)學(xué)void HeapAdjust(HeapType &H，int s，int m)/*已知已知H.rs.m中記錄的關(guān)鍵字除中記錄的關(guān)鍵字除H.rs.key之外均滿(mǎn)足堆定義之外均滿(mǎn)足堆定義，本函數(shù)調(diào)整，本函數(shù)調(diào)整H.rs的關(guān)鍵字，使的關(guān)鍵字，使H.rs.m成為一個(gè)小根堆。成為一個(gè)小根堆。*/ rc=H.rs; for ( j=2*s；j=m；j*=2) if (j0; -i) HeapAdjust(H，i，H.l

37、ength); for (i=H.length；i1； -i) temp=H.r1; H.r1=H.ri; H.ri=temp; HeapAdjust(H，1，i-1); v 堆排序算法堆排序算法安安徽徽理理工工大大學(xué)學(xué) 在整個(gè)堆排序中，共需要進(jìn)行在整個(gè)堆排序中，共需要進(jìn)行 n/2+n-1 次篩選運(yùn)算，每次篩次篩選運(yùn)算，每次篩選運(yùn)算進(jìn)行雙親和孩子或兄弟結(jié)點(diǎn)的關(guān)鍵字的比較和移動(dòng)次數(shù)選運(yùn)算進(jìn)行雙親和孩子或兄弟結(jié)點(diǎn)的關(guān)鍵字的比較和移動(dòng)次數(shù)都不會(huì)超過(guò)完全二叉樹(shù)的深度，所以，每次篩選運(yùn)算的時(shí)間復(fù)都不會(huì)超過(guò)完全二叉樹(shù)的深度，所以，每次篩選運(yùn)算的時(shí)間復(fù)雜度為雜度為O(log2n)，故整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜

38、度為，故整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為O(nlog2n)。 堆排序不適合記錄較少的文件，是一種不穩(wěn)定的排序方法。堆排序不適合記錄較少的文件，是一種不穩(wěn)定的排序方法。 該算法的附加存儲(chǔ)主要是在第二個(gè)該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來(lái)執(zhí)行對(duì)象交循環(huán)中用來(lái)執(zhí)行對(duì)象交換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為O(1)。v 算法分析算法分析安安徽徽理理工工大大學(xué)學(xué)歸并：歸并：是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并的基本操作是將兩個(gè)位置相鄰的有序記錄子序列歸并的基本操作是將兩個(gè)

39、位置相鄰的有序記錄子序列R i . m 和和R m+1 . n 歸并成一個(gè)有序記錄序列歸并成一個(gè)有序記錄序列R i . n 。 2-路歸并排序：路歸并排序： 基本思想：將兩個(gè)有序子區(qū)間（有序表）合并成一個(gè)有序基本思想：將兩個(gè)有序子區(qū)間（有序表）合并成一個(gè)有序子區(qū)間，一次合并完成后，有序子區(qū)間的數(shù)目減少一半，而區(qū)子區(qū)間，一次合并完成后，有序子區(qū)間的數(shù)目減少一半，而區(qū)間的長(zhǎng)度增加一倍，當(dāng)區(qū)間長(zhǎng)度從間的長(zhǎng)度增加一倍，當(dāng)區(qū)間長(zhǎng)度從1增加到增加到n（元素個(gè)數(shù)）時(shí)，（元素個(gè)數(shù)）時(shí)，整個(gè)區(qū)間變?yōu)橐粋€(gè)，則該區(qū)間中的有序序列即為我們所需的排整個(gè)區(qū)間變?yōu)橐粋€(gè)，則該區(qū)間中的有序序列即為我們所需的排序結(jié)果。序結(jié)果。

40、10.4 歸并排序歸并排序安安徽徽理理工工大大學(xué)學(xué)例如，已知關(guān)鍵字例如，已知關(guān)鍵字46，55，13，42，94，05，17，70，給出，給出二路歸并排序過(guò)程。二路歸并排序過(guò)程。 初始狀態(tài)：初始狀態(tài)：46 55 13 42 94 05 17 70 一趟歸并：一趟歸并：46 55 13 42 05 94 17 70 二趟歸并：二趟歸并：13 42 46 55 05 17 94 70 三趟歸并：三趟歸并：05 13 17 42 46 55 70 94v 歸并過(guò)程歸并過(guò)程安安徽徽理理工工大大學(xué)學(xué) 二路歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)間復(fù)二路歸并排序的時(shí)間復(fù)雜度等于歸并趟數(shù)與每一趟時(shí)間復(fù)雜度的乘積。而歸并趟數(shù)為雜度的乘積。而歸并趟數(shù)為 log2n ，每一趟歸并的時(shí)間復(fù)雜度，每一趟歸并的時(shí)間復(fù)雜度為為O(n)。因此，二路歸并排序的時(shí)間復(fù)雜度為。因此，二路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。 利用二路歸并排序時(shí)，需要利用與待排序數(shù)組相同的輔助利用二路歸并排序時(shí)，需要利用與待排序數(shù)組相同的輔助數(shù)組作臨時(shí)單元，故該排序方法的空間復(fù)雜度為數(shù)組作臨時(shí)單元，故該排序方法的空間復(fù)雜度為O(n)，比前面，比前面介紹的其它排序方法占用的空間大。介紹的其它排序方