概述插入排序交換排序選擇排序歸并排序基數排序外部排序小結

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

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

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

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

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

6、ld otherdata;//其它數據成員public: Element ( ) : key(0), otherdata(NULL) { },Type getKey ( ) { return key; }//提取關鍵字 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 ) : //構造函數 MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } void swap ( Element & x, //對換 Element &

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

11、i-1]已經排好序。這時，用v[i]的關鍵字與v[i-1], v[i-2], …的關鍵字順序進行比較，找到插入位置即將v[i]插入，原來位置上的對象向后順移。,插入排序的基本方法是：每步將一個待排序的對象，按其關鍵字大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止。,直接插入排序 (Insert Sort),,,各趟排序結果,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 時的排序過程,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 ) {//按關鍵字 Key 非遞減順序對表進行排序 for ( int i = 1; i viod Insert ( datalist & list, int i ) { Element temp = list.Vector[i]; int j = i; //從后向前順序比較,算法分析,若設待排序的對象個數為curremtsize = n，則該算法的主

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

19、，排序前對象已經按關鍵字大小從小到大有序，每趟只需與前面的有序對象序列的最后一個對象的關鍵字比較 1 次，移動 2 次對象，總的關鍵字比較次數為 n-1，對象移動次數為 2(n-1)。最壞情況下，第 i 趟時第 i 個對象必須與前面 i 個對象都做關鍵字比較，并且每做 1 次比較就要做 1 次數據移動。則總的關鍵字比較次數KCN和對象移動次數RMN分別為,若待排序對象序列中出現(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均

20、情況。在平均情況下的關鍵字比較次數和對象移動次數約為 n2/4。因此，直接插入排序的時間復雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。,折半插入排序 (Binary Insertsort),折半插入排序基本思想是：設在順序表中有一 個對象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已經排好序的對象。在插入 v[i] 時，利用折半搜索法尋找 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];,算法分析,折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。它所需要的關鍵字比較次數與待排序對象序列的初始排列無關，僅依賴于對象個數。在插入第 i 個對象時，需

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

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

25、測比較，找到v[i]應插入(或鏈入)的位置，把v[i]插入，并修改相應的鏈接指針。這樣就可得到v[1], V[2], …, v[i]的一個通過鏈接指針排列好的鏈表。如此重復執(zhí)行，直到把v[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,,,,,,,,,,結果,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,pre current i,鏈表插入排序示例,用于鏈表排序的靜態(tài)鏈表的類定

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

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

30、st ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) //構造函數 { Vector = new Element [MaxSz]; }private: Element * Vector;//存儲向量 int MaxSize, CurrentSize; //向量中最大元素個數和當前

31、元素個數},鏈表插入排序的算法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; //前驅指針 while ( list.Vector[current].getKey ( ) <= list.Vector[i].getKey ( ) ) {

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

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

35、ector[current].Key == vector[i].Key時，current還要向前走一步，pre跟到current原來的位置，此時， vector[pre].Key == vector[i].Key。將vector[i]插在vector[pre]的后面，所以，鏈表插入排序方法是穩(wěn)定的。,交換排序 ( Exchange Sort ),冒泡排序的基本方法是：設待排序對象序列中的對象個數為 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]。,交換排序的基本思想是兩兩比較待排序對象的關鍵字，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之，直到所有對象都排好序為止。,冒泡排序 (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; //交換標志置為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; //交換標志置為1,有交換 }

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

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

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

44、tList 和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 將兩個子序列 LeftList 和 RightList 合并為一個序列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 中遞歸地進行快速排序 if ( left < right) { int pivotpos = Partition ( list, left, right ); //劃分 QuickSort ( list, left, pivotpos-1); //在左子區(qū)間遞歸進行快速排序

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

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] ); //小于基準對象的交換到區(qū)間的左側去 Swap ( list.Vector[low], list.Vector[pivotpos] ); return pivotpos;},,,,,,算法quicksort是一個遞歸的算法，其遞歸樹如圖所示。算法partition利用序列第一個對象作為基準，將整個序列劃分為左右兩個子序列。算法中執(zhí)行了一個循環(huán)

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

52、列進行排序所需的時間，而且每次對一個對象正確定位后，正好把序列劃分為長度相等的兩個子序列，此時，總的計算時間為：,T(n) ? cn + 2 t(n/2 ) // c是一個常數 ? 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 )可以證明，函數quicksort的平均計算時間也是o(nlog2n)。實驗結果表明：就平均計算時間而言，快速排序是我們所討論的所有內排序方法中最好的一個。,最大遞歸調用層次數與遞歸樹的深度一致，理想情況為 ?log2(n+1)? 。因此，要求存儲開銷為 o(log2n)。在最壞的情況，即待排序對象序列已經按其關鍵字從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，

54、必須經過 n-1 趟才能把所有對象定位，而且第 i 趟需要經過 n-i 次關鍵字比較才能找到第 i 個對象的安放位置，總的關鍵字比較次數將達到,其排序速度退化到簡單排序的水平，比直接插入排序還慢。占用附加存儲(即棧)將達到o(n)。若能更合理地選擇基準對象，使得每次劃分所得的兩個子序列中的對象個數盡可能地接近，可以加速排序速度，但是由于對象的初始排列次序是隨機的，這個要求很難辦到。有一種改進辦法：取每個待排序對象序列的第一個對象、最

55、后一個對象和位置接近正中的3個對象，取其關鍵字居中者作為基準對象。,用第一個對象作為基準對象,快速排序退化的例子,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,用居中關鍵字對象作為基準對象,快速排序是一種不穩(wěn)定的排序方法。對于 n 較大的平均情況而言，快速排序是“快速”的，但是

57、當 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 個待排序對象中選出關鍵字最小的對象, 作為有序對象序列的第 i 個對象。待到第 n-2 趟作完，待排序對象只剩下1個，就不用再選了。,選擇排序,直接選擇排序是一種簡單的排序方法，它的基本步驟是： 在一組對象v[i]～v[n-1]中選擇具有最小關鍵字的對象；,直接選擇排序 (Select Sort),若它不是這組對象中的第一個對象，則將它與這組對象中的第一個對象對調

59、； 在這組對象中剔除這個具有最小關鍵字的對象，在剩下的對象v[i+1]～v[n-1]中重復執(zhí)行第?、?步，直到剩余對象只有一個為止。,直接選擇排序的算法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; //當前具最小關鍵字的對象 if ( k != i ) //對換到第 i 個位置 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,結果,i = 3,08,16,25,21,最小者 25*無交換,最小者 25無交換,25,21,16,08,各趟排序后的結果,,,,,0 1 2 3 4 5,49,16,08,25*,49,21,08,25*,25,21,i =1時選擇排序的過程,,,,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 指示當前序列中最小者,算法分析,直接選擇排序的關鍵字比較次數KCN與對象的初始排列無關。第 i 趟選擇具有最小關鍵字對象所需的比較次數總是 n-i-1 次，此處假定整個待排序對象序列有 n 個對象。因此，總的關鍵字比較次數為,對象的移動次數與對象序列的初始排列有關。當這組對象的初始狀態(tài)是按其關鍵字從小到大有序的時

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

67、方法稱為兩路歸并 (2-way merging)。其基本思想是：設兩個有序表A和B的對象個數(表長)分別為 al 和 bl，變量 i 和 j 分別是表A和表B的當前檢測指針。設表C是歸并后的新有序表，變量 k 是它的當前存放指針。,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,當 i 和 j 都在兩個表的表長內變化時，根據A[i]與B[j]的關鍵字的大小

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