概述插入排序交換排序選擇排序歸并排序基數(shù)排序外部排序小結(jié)

1、概述插入排序交換排序選擇排序歸并排序基數(shù)排序外部排序小結(jié),第七章 排序,概述,排序：將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對(duì)象的有限集合。關(guān)鍵字(key): 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象，作為排序依據(jù)。該域即為關(guān)鍵字。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵字，要視具體的應(yīng)用需要而定。即使是同一個(gè)表，在解決不同問(wèn)題的場(chǎng)合也可能

2、取不同的域做關(guān)鍵字。,主關(guān)鍵字: 如果在數(shù)據(jù)表中各個(gè)對(duì)象的關(guān)鍵字互不相同，這種關(guān)鍵字即主關(guān)鍵字。按照主關(guān)鍵字進(jìn)行排序，排序的結(jié)果是唯一的。次關(guān)鍵字: 數(shù)據(jù)表中有些對(duì)象的關(guān)鍵字可能相同，這種關(guān)鍵字稱(chēng)為次關(guān)鍵字。按照次關(guān)鍵字進(jìn)行排序，排序的結(jié)果可能不唯一。排序算法的穩(wěn)定性: 如果在對(duì)象序列中有兩個(gè)對(duì)象r[i]和r[j]，它們的關(guān)鍵字 k[i] == k[j]，且在排序之前，對(duì)象r[i]排在r[j]前面。如果在排序之后，對(duì)象r[i]仍

3、在對(duì)象r[j]的前面，則稱(chēng)這個(gè)排序方法是穩(wěn)定的，否則稱(chēng)這個(gè)排序方法是不穩(wěn)定的。,內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過(guò)程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序的時(shí)間開(kāi)銷(xiāo): 排序的時(shí)間開(kāi)銷(xiāo)是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開(kāi)銷(xiāo)可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來(lái)衡量。各節(jié)給出算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平

4、均情況進(jìn)行估算。對(duì)于那些受對(duì)象關(guān)鍵字序列初始排列及對(duì)象個(gè)數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。,靜態(tài)排序: 排序的過(guò)程是對(duì)數(shù)據(jù)對(duì)象本身進(jìn)行物理地重排，經(jīng)過(guò)比較和判斷，將對(duì)象移到合適的位置。這時(shí)，數(shù)據(jù)對(duì)象一般都存放在一個(gè)順序的表中。動(dòng)態(tài)排序: 給每個(gè)對(duì)象增加一個(gè)鏈接指針，在排序的過(guò)程中不移動(dòng)對(duì)象或傳送數(shù)據(jù)，僅通過(guò)修改鏈接指針來(lái)改變對(duì)象之間的邏輯順序，從而達(dá)到排序的目的。算法執(zhí)行時(shí)所需的附加存儲(chǔ): 評(píng)價(jià)算法好壞的另

5、一標(biāo)準(zhǔn)。靜態(tài)排序過(guò)程中所用到的數(shù)據(jù)表類(lèi)定義，體現(xiàn)了抽象數(shù)據(jù)類(lèi)型的思想。,待排序數(shù)據(jù)表的類(lèi)定義#ifndef DATALIST_H#define DATALIST_H#include const int DefaultSize = 100;template class datalist {template class Element {private: Type key;//關(guān)鍵字 fie

6、ld otherdata;//其它數(shù)據(jù)成員public: Element ( ) : key(0), otherdata(NULL) { },Type getKey ( ) { return key; }//提取關(guān)鍵字 void setKey ( const Type x ) { key = x; } //修改 Element & operator =

7、//賦值 ( Element & x ) { this = x; } int operator == ( Type & x ) //判this == x { return ! ( this->key >x || x key ); } int operator != ( Type & x ) //判this !=

8、 x { return this->key key ; } int operator key > x ); } int operator >= ( Type & x ) //判this ? x { return ! (this->key key > x; },}template class datalist {publi

9、c: datalist ( int MaxSz = DefaultSize ) : //構(gòu)造函數(shù) MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } void swap ( Element & x, //對(duì)換 Element &

10、 y ) { Element temp = x; x = y; y = temp; }private: Element * Vector; //存儲(chǔ)向量 int MaxSize, CurrentSize; //最大與當(dāng)前個(gè)數(shù)},,插入排序 (Insert Sorting),直接插入排序的基本思想是：當(dāng)插入第i (i ? 1) 個(gè)對(duì)象時(shí)，前面的V[0], V[1], …, v[

11、i-1]已經(jīng)排好序。這時(shí)，用v[i]的關(guān)鍵字與v[i-1], v[i-2], …的關(guān)鍵字順序進(jìn)行比較，找到插入位置即將v[i]插入，原來(lái)位置上的對(duì)象向后順移。,插入排序的基本方法是：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。,直接插入排序 (Insert Sort),,,各趟排序結(jié)果,21,25,49,25*,16,08,0 1 2

12、 3 4 5,,0 1 2 3 4 5 temp,21,25,49,25*,16,08,25,i = 1,0 1 2 3 4 5 temp,,21,25,49,25*,16,08,49,i = 2,,,,,,,21,25,49,25*,16

13、,08,0 1 2 3 4 5,,0 1 2 3 4 5 temp,21,25,49,25*,16,08,i = 4,0 1 2 3 4 5 temp,,21,25,49,25*,16,08,i =

14、 5,,,,,i = 3,25*,,,,16,,,,,08,,,,,,,16,,49,16,16,,,21,25,49,25*,16,08,0 1 2 3 4 5,0 1 2 3 4 5 temp,21,25,49,25*,08,i = 4 時(shí)的排序過(guò)程,0 1

15、 2 3 4 5 temp,21,25,49,25*,完成,16,,08,16,,i = 4j = 3,i = 4j = 2,,25,,25*,16,,16,,21,25,49,25*,08,0 1 2 3 4 5,0 1 2 3 4

16、 5 temp,21,49,25*,08,0 1 2 3 4 5 temp,21,25,49,25*,16,08,16,,16,25,21,,,i = 4j = 1,i = 4j = 0,i = 4j = -1,,16,直接插入排序的算法template void InsertionSort ( datalist &am

17、p; list ) {//按關(guān)鍵字 Key 非遞減順序?qū)Ρ磉M(jìn)行排序 for ( int i = 1; i viod Insert ( datalist & list, int i ) { Element temp = list.Vector[i]; int j = i; //從后向前順序比較,算法分析,若設(shè)待排序的對(duì)象個(gè)數(shù)為curremtsize = n，則該算法的主

18、程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵字的初始排列有關(guān)。,while ( j > 0 && temp.getKey ( ) < list.Vector[j-1].getKey ( ) ) { list.Vector[j] = list.Vector[j-1]; j--; } list.Vector[j] = temp; },最好情況下

19、，排序前對(duì)象已經(jīng)按關(guān)鍵字大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象的關(guān)鍵字比較 1 次，移動(dòng) 2 次對(duì)象，總的關(guān)鍵字比較次數(shù)為 n-1，對(duì)象移動(dòng)次數(shù)為 2(n-1)。最壞情況下，第 i 趟時(shí)第 i 個(gè)對(duì)象必須與前面 i 個(gè)對(duì)象都做關(guān)鍵字比較，并且每做 1 次比較就要做 1 次數(shù)據(jù)移動(dòng)。則總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN分別為,若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均

20、情況。在平均情況下的關(guān)鍵字比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。,折半插入排序 (Binary Insertsort),折半插入排序基本思想是：設(shè)在順序表中有一 個(gè)對(duì)象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已經(jīng)排好序的對(duì)象。在插入 v[i] 時(shí)，利用折半搜索法尋找 v[i] 的插入位置。,折半

21、插入排序的算法template void BinaryInsertSort ( datalist & list ) { for ( int i = 1; i < list.CurrentSize; i++) BinaryInsert ( list, i );},template void BinaryInsert ( datalist & list, int i ) { int l

22、eft = 0, Right = i-1; Element temp = list.Vector[i]; while ( left = left; k-- ) list.Vector[k+1] = list.Vector[k];,算法分析,折半查找比順序查找快，所以折半插入排序就平均性能來(lái)說(shuō)比直接插入排序要快。它所需要的關(guān)鍵字比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o(wú)關(guān)，僅依賴(lài)于對(duì)象個(gè)數(shù)。在插入第 i 個(gè)對(duì)象時(shí)，需

23、要經(jīng)過(guò) ?log2i? +1 次關(guān)鍵字比較，才能確定它應(yīng)插入的位置。因此，將 n 個(gè)對(duì)象（為推導(dǎo)方便，設(shè)為 n=2k )用折半插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為：,list.Vector[left] = temp;},當(dāng) n 較大時(shí)，總關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時(shí)，直接插入排序比折半插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少。折半插入排序的對(duì)象移動(dòng)次數(shù)與直接

24、插入排序相同，依賴(lài)于對(duì)象的初始排列。折半插入排序是一個(gè)穩(wěn)定的排序方法。,鏈表插入排序,鏈表插入排序的基本思想是：在每個(gè)對(duì)象的結(jié)點(diǎn)中增加一個(gè)鏈接指針數(shù)據(jù)成員 link。對(duì)于存放于數(shù)組中的一組對(duì)象V[1], V[2], …, v[n]，若v[1], V[2], …, v[i-1]已經(jīng)通過(guò)指針link，按其關(guān)鍵字的大小，從小到大鏈接起來(lái)，現(xiàn)在要插入v[i], i = 2, 3, …, n，則必須在前面i-1個(gè)鏈接起來(lái)的對(duì)象當(dāng)中，循鏈順序檢

25、測(cè)比較，找到v[i]應(yīng)插入(或鏈入)的位置，把v[i]插入，并修改相應(yīng)的鏈接指針。這樣就可得到v[1], V[2], …, v[i]的一個(gè)通過(guò)鏈接指針排列好的鏈表。如此重復(fù)執(zhí)行，直到把v[n]也插入到鏈表中排好序?yàn)橹埂?,,?,25,49,25*,16,08,0 1 2 3 4 5 6,i = 2,i = 3,21,,,,,,,,初始,,,

26、,,,current pre i,,,,,,,,,,,,,,,,current pre i,,,,,,,,,,,,,,,,,pre current i,,,,,,,,,,i = 4,,,,,,,,,,,?,25,49,25*,16,08,0 1 2 3 4 5 6,i = 5,i =

27、6,21,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,pre current i,,,,,,,,,,結(jié)果,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,pre current i,鏈表插入排序示例,用于鏈表排序的靜態(tài)鏈表的類(lèi)定

28、義template class staticlinklist;template class Element {private: Type key;//結(jié)點(diǎn)的關(guān)鍵字 int link;//結(jié)點(diǎn)的鏈接指針public: Element ( ) : key(0), link (NULL) { } Type getKey ( ) { return key; } //提取關(guān)鍵字 vo

29、id setKey ( const Type x ) { key = x; } //修改 int getLink ( ) { return link; } //提取鏈指針 void setLink ( const int l ) { link = l; } //設(shè)置指針,} template class staticlinklist {public: dstaticlinkli

30、st ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) //構(gòu)造函數(shù) { Vector = new Element [MaxSz]; }private: Element * Vector;//存儲(chǔ)向量 int MaxSize, CurrentSize; //向量中最大元素個(gè)數(shù)和當(dāng)前

31、元素個(gè)數(shù)},鏈表插入排序的算法template int LinkInsertSort ( staticlinklis & list ) { list.Vector[0].setKey ( MaxNum ); list.Vector[0].setLink ( 1 ); list.Vector[1].setLink ( 0 ); //形成循環(huán)鏈表 for ( int i = 2; i &

32、lt;= list.CurrentSize; i++ ) { int int current = list.Vector[0].getLink ( ); int pre = 0; //前驅(qū)指針 while ( list.Vector[current].getKey ( ) <= list.Vector[i].getKey ( ) ) {

33、 //找插入位置 pre = current; //pre跟上, current向前走 current = list.Vector[current].getLink ( ); },算法分析,使用鏈表插入排序，每插入一個(gè)對(duì)象，最大關(guān)鍵字比較次數(shù)等于鏈表中已排好序的對(duì)象個(gè)數(shù)，最小關(guān)鍵字比較次數(shù)為1。故總的關(guān)鍵字比較次數(shù)最小為 n-1，最大為,list.Vector[i].set

34、Link ( current ); list.Vector[pre].setLink ( i ); //在pre與current之間鏈入 }},用鏈表插入排序時(shí)，對(duì)象移動(dòng)次數(shù)為0。但為 了實(shí)現(xiàn)鏈表插入，在每個(gè)對(duì)象中增加了一個(gè)鏈域 link，并使用了vector[0]作為鏈表的表頭結(jié)點(diǎn)，總共用了 n 個(gè)附加域和一個(gè)附加對(duì)象。算法從 i = 2 開(kāi)始，從前向后插入。并且在v

35、ector[current].Key == vector[i].Key時(shí)，current還要向前走一步，pre跟到current原來(lái)的位置，此時(shí)， vector[pre].Key == vector[i].Key。將vector[i]插在vector[pre]的后面，所以，鏈表插入排序方法是穩(wěn)定的。,交換排序 ( Exchange Sort ),冒泡排序的基本方法是：設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為 n。最多作 n-1 趟，i = 1,

36、2, ?, n-2 。在第 i 趟中順次兩兩比較v[n-j-1].Key和v[n-j].Key，j = n-1, n-2, ?, i。如果發(fā)生逆序，則交換v[n -j-1]和v[n-j]。,交換排序的基本思想是兩兩比較待排序?qū)ο蟮年P(guān)鍵字，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對(duì)象都排好序?yàn)橹埂?冒泡排序 (Bubble Sort),,,21,25,49,25*,16,08,0 1

37、 2 3 4 5,,21,25*,i = 1,,49,,25,16,25,16,08,49,Exchang=1,08,,,,,,25*,,,,,49,21,Exchang=1,i = 2,i = 3,08,16,Exchang=1,25*,,25,21,,,25*,0 1 2 3 4

38、 5,i = 4,49,16,Exchang=0,08,25,21,冒泡排序的算法template void BubbleSort (datalist & list ) { int pass = 1; int exchange = 1; while ( pass < list.CurrentSize && exchange ){ BubbleEx

39、change ( list, pass, exchange ); pass++; }},template void BubbleExchange ( datalist & list , const int i, int & exchange ) { exchange = 0; //交換標(biāo)志置為0,假定未交換 for ( int j = list.Cu

40、rrentSize-1; j >= i; j-- ) if ( list.Vector[j-1].getKey ( ) > list.Vector[j].getKey ( ) ) { //逆序 Swap ( list.Vector[j-1], list.Vector[j] );//交換 exchange = 1; //交換標(biāo)志置為1,有交換 }

41、},第 i 趟對(duì)待排序?qū)ο笮蛄衯[i-1], v[i], ?, v[n-1]進(jìn)行排序，結(jié)果將該序列中關(guān)鍵字最小的對(duì)象交換到序列的第一個(gè)位置(i-1)，其它對(duì)象也都向排序的最終位置移動(dòng)。當(dāng)然在個(gè)別情形下，對(duì)象有可能在排序中途向相反的方向移動(dòng)。這樣最多做n-1趟冒泡就能把所有對(duì)象排好序。,算法分析,在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法只執(zhí)行一趟冒泡，做 n-1 次關(guān)鍵字比較，不移動(dòng)對(duì)象。這是最好的情形。,,最壞的情形是算

42、法執(zhí)行了n-1趟冒泡，第 i 趟 (1? i? n) 做了 n- i 次關(guān)鍵字比較，執(zhí)行了n-i 次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：冒泡排序需要一個(gè)附加對(duì)象以實(shí)現(xiàn)對(duì)象值的對(duì)換。冒泡排序是一個(gè)穩(wěn)定的排序方法。,快速排序 (Quick Sort),快速排序方法的基本思想是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對(duì)象 (例如取第一個(gè)對(duì)象) 作為基準(zhǔn)，按照該對(duì)象的關(guān)鍵字大小，將整個(gè)對(duì)象序列劃分為左右兩個(gè)子

43、序列： 左側(cè)子序列中所有對(duì)象的關(guān)鍵字都小于或等于基準(zhǔn)對(duì)象的關(guān)鍵字 右側(cè)子序列中所有對(duì)象的關(guān)鍵字都大于基準(zhǔn)對(duì)象的關(guān)鍵字基準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置)。,,然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止。算法描述,QuickSort ( List ) { if ( List的長(zhǎng)度大于1) {將序列List劃分為兩個(gè)子序列 Lef

44、tList 和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個(gè)子序列 LeftList 和 RightList 合并為一個(gè)序列List; }},,,,,21,25,49,25*,16,08,0 1 2 3

45、4 5,,21,25*,i = 1,,49,,25,16,25,16,08,49,pivot,08,25*,49,21,i = 2,i = 3,08,16,25*,25,21,pivot,pivot,pivot,,,,,,21,25,49,25*,16,08,0 1 2 3 4 5,25*,i = 1劃分,25,16

46、,25,16,08,49,pivotpos,08,25*,49,08,16,25*,25,21,,,,pivotpos,21,比較4次交換25,16,i,,i,pivotpos,21,比較1次交換49,08,49,low pivotpos,交換21,08,快速排序的算法template void QuickSort ( datalist &list, const int left,

47、 const int right ) {//在待排序區(qū)間 left?right 中遞歸地進(jìn)行快速排序 if ( left < right) { int pivotpos = Partition ( list, left, right ); //劃分 QuickSort ( list, left, pivotpos-1); //在左子區(qū)間遞歸進(jìn)行快速排序

48、 QuickSort ( list, pivotpos+1, right ); //在左子區(qū)間遞歸進(jìn)行快速排序 }},template int Partition ( datalist &list, const int low, const int high ) { int pivotpos = low; //基準(zhǔn)位置

49、 Element pivot = list.Vector[low]; for ( int i = low+1; i <= high; i++ ) if ( list.Vector[i].getKey ( ) < pivot.getKey( ) && ++pivotpos != i ) Swap ( list.Vector[pivotp

50、os], list.Vector[i] ); //小于基準(zhǔn)對(duì)象的交換到區(qū)間的左側(cè)去 Swap ( list.Vector[low], list.Vector[pivotpos] ); return pivotpos;},,,,,,算法quicksort是一個(gè)遞歸的算法，其遞歸樹(shù)如圖所示。算法partition利用序列第一個(gè)對(duì)象作為基準(zhǔn)，將整個(gè)序列劃分為左右兩個(gè)子序列。算法中執(zhí)行了一個(gè)循環(huán)

51、，只要是關(guān)鍵字小于基準(zhǔn)對(duì)象關(guān)鍵字的對(duì)象都移到序列左側(cè)，最后基準(zhǔn)對(duì)象安放到位，函數(shù)返回其位置。,,21,,25*,25,49,08,16,,算法分析,從快速排序算法的遞歸樹(shù)可知，快速排序的趟數(shù)取決于遞歸樹(shù)的深度。如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序，這是最理想的情況。在n個(gè)元素的序列中，對(duì)一個(gè)對(duì)象定位所需時(shí)間為 O(n)。若設(shè) t(n) 是對(duì) n 個(gè)元素的序

52、列進(jìn)行排序所需的時(shí)間，而且每次對(duì)一個(gè)對(duì)象正確定位后，正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列，此時(shí)，總的計(jì)算時(shí)間為：,T(n) ? cn + 2 t(n/2 ) // c是一個(gè)常數(shù) ? Cn + 2 ( cn/2 + 2t(n/4) ) = 2cn + 4t(n/4) ? 2cn + 4 ( cn/4 +2t(n/8) ) = 3cn + 8t(n/8) ……… ? Cn log2n + nt(1) =

53、 o(n log2n )可以證明，函數(shù)quicksort的平均計(jì)算時(shí)間也是o(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè)。,最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)的深度一致，理想情況為 ?log2(n+1)? 。因此，要求存儲(chǔ)開(kāi)銷(xiāo)為 o(log2n)。在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下，其遞歸樹(shù)成為單支樹(shù)，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。這樣，

54、必須經(jīng)過(guò) n-1 趟才能把所有對(duì)象定位，而且第 i 趟需要經(jīng)過(guò) n-i 次關(guān)鍵字比較才能找到第 i 個(gè)對(duì)象的安放位置，總的關(guān)鍵字比較次數(shù)將達(dá)到,其排序速度退化到簡(jiǎn)單排序的水平，比直接插入排序還慢。占用附加存儲(chǔ)(即棧)將達(dá)到o(n)。若能更合理地選擇基準(zhǔn)對(duì)象，使得每次劃分所得的兩個(gè)子序列中的對(duì)象個(gè)數(shù)盡可能地接近，可以加速排序速度，但是由于對(duì)象的初始排列次序是隨機(jī)的，這個(gè)要求很難辦到。有一種改進(jìn)辦法：取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最

55、后一個(gè)對(duì)象和位置接近正中的3個(gè)對(duì)象，取其關(guān)鍵字居中者作為基準(zhǔn)對(duì)象。,用第一個(gè)對(duì)象作為基準(zhǔn)對(duì)象,快速排序退化的例子,08 16 21 25 25* 49,08,0 1 2 3 4 5 pivot,初始,16 21 25 25* 49,08,16,21 25 25*

56、 49,21,08 16,25,25 25* 49,08 16 21,25* 49,25*,08 16 21 25,,49,08 16 21 25 25*,i = 1,i = 2,i = 3,i = 4,i = 5,用居中關(guān)鍵字對(duì)象作為基準(zhǔn)對(duì)象,快速排序是一種不穩(wěn)定的排序方法。對(duì)于 n 較大的平均情況而言，快速排序是“快速”的，但是

57、當(dāng) n 很小時(shí)，這種排序方法往往比其它簡(jiǎn)單排序方法還要慢。,,08 16 21 25 25* 49,0 1 2 3 4 5 pivot,21,初始,08 16,21,25 25* 49,08,25*,08,16,21,25,25*,49,i = 1,i = 2,選擇排序的基本思想是：每一趟

58、 (例如第 i 趟，i = 0, 1, …, n-2) 在后面 n-i 個(gè)待排序?qū)ο笾羞x出關(guān)鍵字最小的對(duì)象, 作為有序?qū)ο笮蛄械牡?i 個(gè)對(duì)象。待到第 n-2 趟作完，待排序?qū)ο笾皇Ｏ?個(gè)，就不用再選了。,選擇排序,直接選擇排序是一種簡(jiǎn)單的排序方法，它的基本步驟是： 在一組對(duì)象v[i]～v[n-1]中選擇具有最小關(guān)鍵字的對(duì)象；,直接選擇排序 (Select Sort),若它不是這組對(duì)象中的第一個(gè)對(duì)象，則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào)

59、； 在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵字的對(duì)象，在剩下的對(duì)象v[i+1]～v[n-1]中重復(fù)執(zhí)行第?、?步，直到剩余對(duì)象只有一個(gè)為止。,直接選擇排序的算法template void SelectSort ( datalist & list ) { for ( int i = 0; i < list.CurrentSize-1; i++ ) SelectExchange ( list, i );},te

60、mplate void SelectExchange ( datalist & list, const int i ) { int k = i; for ( int j = i+1; j < list.CurrentSize; j++) if ( list.Vector[j].getKey ( ) < list.Ve

61、ctor[k].getKey ( ) ) k = j; //當(dāng)前具最小關(guān)鍵字的對(duì)象 if ( k != i ) //對(duì)換到第 i 個(gè)位置 Swap ( list.Vector[i], list.Vector[k] );},,,,,,21,25,49,25*,16,08,0 1 2 3 4

62、 5,21,25*,i = 0,49,25,16,25,16,08,49,08,25*,49,21,i = 1,i = 2,08,16,25*,25,21,初始,最小者 08交換21,08,最小者 16交換25,16,最小者 21交換49,21,,,,,49,25*,0 1 2 3 4 5,25*,i = 4,25,16

63、,08,49,25*,49,21,結(jié)果,i = 3,08,16,25,21,最小者 25*無(wú)交換,最小者 25無(wú)交換,25,21,16,08,各趟排序后的結(jié)果,,,,,0 1 2 3 4 5,49,16,08,25*,49,21,08,25*,25,21,i =1時(shí)選擇排序的過(guò)程,,,,i k j,49,25

64、,08,25*,16,21,,,i k j,,49 ? 25,25* ? 25,16,,,,25,i k j,16 < 25,,49,25,08,25*,16,21,0 1 2 3 4 5,i

65、 k j,,,,21 ? 16,k 指示當(dāng)前序列中最小者,算法分析,直接選擇排序的關(guān)鍵字比較次數(shù)KCN與對(duì)象的初始排列無(wú)關(guān)。第 i 趟選擇具有最小關(guān)鍵字對(duì)象所需的比較次數(shù)總是 n-i-1 次，此處假定整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象。因此，總的關(guān)鍵字比較次數(shù)為,對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其關(guān)鍵字從小到大有序的時(shí)

66、候，對(duì)象的移動(dòng)次數(shù)RMN = 0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為RMN = (n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。,歸并排序 (Merge Sort),歸并，是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。對(duì)象序列 initList 中有兩個(gè)有序表V[l] …V[m]和V[m+1] …V[n]。它們可歸并成一個(gè)有序表，存于另一對(duì)象序列 mergedList 的V[l] …V[n]中。這種歸并

67、方法稱(chēng)為兩路歸并 (2-way merging)。其基本思想是：設(shè)兩個(gè)有序表A和B的對(duì)象個(gè)數(shù)(表長(zhǎng))分別為 al 和 bl，變量 i 和 j 分別是表A和表B的當(dāng)前檢測(cè)指針。設(shè)表C是歸并后的新有序表，變量 k 是它的當(dāng)前存放指針。,08 21 25 25* 49 62 72 93,16 37 54,l m m+1

68、 n,initList,,,i j,08 16 21 25 25* 37 49 54 62 72 93,l n,,k,mergeList,當(dāng) i 和 j 都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí)，根據(jù)A[i]與B[j]的關(guān)鍵字的大小

69、，依次把關(guān)鍵字小的對(duì)象排放到新表C[k]中；當(dāng) i 與 j 中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一 個(gè)表中的剩余部分照抄到新表C[k]中。,迭代的歸并排序算法,迭代的歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序的。其基本思想是：假設(shè)初始對(duì)象序列有 n 個(gè)對(duì)象，首先把它看成是 n 個(gè)長(zhǎng)度為 1 的有序子序列 (歸并項(xiàng))，先做兩兩歸并，得到 ?n / 2? 個(gè)長(zhǎng)度為 2 的歸并項(xiàng) (如果 n 為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1)；再做兩兩歸并，