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

1、概述插入排序交換排序選擇排序歸并排序基數(shù)排序外排序小結(jié),第九章 排序,概述,排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對(duì)象的有限集合。關(guān)鍵碼(key): 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來區(qū)分對(duì)象，作為排序依據(jù)。該域即為關(guān)鍵碼。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵碼，要視具體的應(yīng)用需要而定。即使是同一個(gè)表，在解決不同問題的場(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)鍵碼稱為次關(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]的前面，則稱這個(gè)排序方法是穩(wěn)定的，否則稱這個(gè)排序方法是不穩(wěn)定的。,內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對(duì)象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對(duì)象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序的時(shí)間開銷: 排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來衡量。各節(jié)給出算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均

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

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

6、d 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 x ); } int operator >= ( Type & x ) //判this ? x { return

8、 ! ( this x; },}template class datalist {public: datalist ( int MaxSz = DefaultSize ) : //構(gòu)造函數(shù) MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } void swap ( Element &

9、amp; x, //對(duì)換 Element & y ) { Element temp = x; x = y; y = temp; }private: Element * Vector; //存儲(chǔ)向量 int MaxSize, CurrentSize; //最大與當(dāng)前個(gè)數(shù)},,插入排序 (Insert Sorting),直

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

11、趟排序結(jié)果,21,25,49,25*,16,08,0 1 2 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

12、,,21,25,49,25*,16,08,49,i = 2,,,,,,,21,25,49,25*,16,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

13、 4 5 temp,,21,25,49,25*,16,08,i = 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

14、 temp,21,25,49,25*,08,i = 4 時(shí)的排序過程,0 1 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

15、 5,0 1 2 3 4 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,直接插入

16、排序的算法template void InsertionSort ( datalist & 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;

17、 //從后向前順序比較,算法分析,若設(shè)待排序的對(duì)象個(gè)數(shù)為curremtsize = n，則該算法的主程序執(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

18、[j-1]; j--; } list.Vector[j] = temp; },最好情況下，排序前對(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ì)象

19、移動(dòng)次數(shù)RMN分別為,若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(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

20、[i-1] 是已經(jīng)排好序的對(duì)象。在插入 v[i] 時(shí)，利用折半搜索法尋找 v[i] 的插入位置。,折半插入排序的算法template void BinaryInsertSort ( datalist & list ) { for ( int i = 1; i < list.CurrentSize; i++) BinaryInsert ( list, i );},template void Bina

21、ryInsert ( datalist & list, int i ) { int left = 0, Right = i-1; Element temp = list.Vector[i]; while ( left = left; k-- ) list.Vector[k+1] = list.Vector[k];,算法分析,對(duì)分查找比順序查找快，所以對(duì)分插入排序就平均性能來說比直接插入排序要快。

22、它所需要的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對(duì)象個(gè)數(shù)。在插入第 i 個(gè)對(duì)象時(shí)，需要經(jīng)過 ?log2i? +1 次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。因此，將 n 個(gè)對(duì)象（為推導(dǎo)方便，設(shè)為 n=2k )用對(duì)分插入排序所進(jìn)行的關(guān)鍵碼比較次數(shù)為：,list.Vector[left] = temp;},當(dāng) n 較大時(shí)，總關(guān)鍵碼比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差。在對(duì)象的初始排列已經(jīng)按關(guān)鍵碼排

23、好序或接近有序時(shí)，直接插入排序比對(duì)分插入排序執(zhí)行的關(guān)鍵碼比較次數(shù)要少。對(duì)分插入排序的對(duì)象移動(dòng)次數(shù)與直接插入排序相同，依賴于對(duì)象的初始排列。對(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)通過指針link，按其關(guān)鍵碼的大小，從小到大鏈接起來，

24、現(xiàn)在要插入v[i], i = 2, 3, …, n，則必須在前面i-1個(gè)鏈接起來的對(duì)象當(dāng)中，循鏈順序檢測(cè)比較，找到v[i]應(yīng)插入(或鏈入)的位置，把v[i]插入，并修改相應(yīng)的鏈接指針。這樣就可得到v[1], V[2], …, v[i]的一個(gè)通過鏈接指針排列好的鏈表。如此重復(fù)執(zhí)行，直到把v[n]也插入到鏈表中排好序?yàn)橹埂?,,?,25,49,25*,16,08,0 1 2 3

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

26、 3 4 5 6,i = 5,i = 6,21,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,pre current i,,,,,,,,,,結(jié)果,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,pre current

27、 i,鏈表插入排序示例,用于鏈表排序的靜態(tài)鏈表的類定義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) { }

28、 Type getKey ( ) { return key; } //提取關(guān)鍵碼 void setKey ( const Type x ) { key = x; } //修改 int getLink ( ) { return link; } //提取鏈指針 void setLink ( const int l ) { link = l; } //設(shè)置指針,} template

29、 class staticlinklist {public: dstaticlinklist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) //構(gòu)造函數(shù) { Vector = new Element [MaxSz]; }private: Element * Vector;//存儲(chǔ)向量

30、 int MaxSize, CurrentSize; //向量中最大元素個(gè)數(shù)和當(dāng)前元素個(gè)數(shù)},鏈表插入排序的算法template int LinkInsertSort ( staticlinklis & list ) { list.Vector[0].setKey ( MaxNum ); list.Vector[0].setLink ( 1 ); list.Vector[1

31、].setLink ( 0 ); //形成循環(huán)鏈表 for ( int i = 2; i <= list.CurrentSize; i++ ) { int int current = list.Vector[0].getLink ( ); int pre = 0; //前驅(qū)指針 while ( list.Vector[current].getKey ( ) &l

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

33、小關(guān)鍵碼比較次數(shù)為1。故總的關(guān)鍵碼比較次數(shù)最小為 n-1，最大為,list.Vector[i].setLink ( current ); list.Vector[pre].setLink ( i ); //在pre與current之間鏈入 }},用鏈表插入排序時(shí)，對(duì)象移動(dòng)次數(shù)為0。但為 了實(shí)現(xiàn)鏈表插入，在每個(gè)對(duì)象中增加了一個(gè)鏈域 link，并使用了vector[0]作為鏈

34、表的表頭結(jié)點(diǎn)，總共用了 n 個(gè)附加域和一個(gè)附加對(duì)象。算法從 i = 2 開始，從前向后插入。并且在vector[current].Key == vector[i].Key時(shí)，current還要向前走一步，pre跟到current原來的位置，此時(shí)， vector[pre].Key == vector[i].Key。將vector[i]插在vector[pre]的后面，所以，鏈表插入排序方法是穩(wěn)定的。,希爾排序 (Shell Sort),

35、希爾排序方法又稱為縮小增量排序。該方法的基本思想是：設(shè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象，首先取一個(gè)整數(shù) gap < n 作為間隔，將全部對(duì)象分為 gap 個(gè)子序列，所有距離為 gap 的對(duì)象放在同一個(gè)子序列中，在每一個(gè)子序列中分別施行直接插入排序。然后縮小間隔 gap，例如取 gap = ?gap/2?，重復(fù)上述的子序列劃分和排序工作。直到最后取 gap == 1，將所有對(duì)象放在同一個(gè)序列中排序?yàn)橹埂?,,21,25,49,25*,1

36、6,08,0 1 2 3 4 5,,21,25*,i = 1,,08,49,Gap = 3,,25,16,49,25,16,08,49,25*,08,21,25,21,25*,16,,,21,25,49,25*,16,08,0 1 2 3 4 5,,21,i

37、= 2,,08,49,Gap = 2,,25,16,49,16,25*,08,21,25,49,25*,08,16,21,25*,25,,,21,25,49,25*,16,08,0 1 2 3 4 5,,21,i = 3,08,Gap = 1,25,16,49,25*,開始時(shí) gap 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，gap

38、 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。,希爾排序的算法template void Shellsort ( datalist & list ) { int gap = list.CurrentSize / 2; // gap 是子序列間隔 while ( gap ) { //循環(huán),直到gap為零

39、ShellInsert ( list, gap ); //一趟直接插入排序gep = gep == 2 ? 1 : ( int ) ( gap/2.2 ); //修改 }},template voidshellInsert ( datalist & list; const int gep ) { //一趟希爾排序,按間隔gap劃分子序列 for ( int i = gap; i tem

40、p = list.Vector[i];int j = i;while ( j >= gap && temp.getKey ( ) < list.Vector[j-gap].getKey ( ) ) { list.Vector[j] = list.Vector[j-gap]; j -= ga

41、p; } list.Vector[j] = temp; }},Gap的取法有多種。最初 shell 提出取 gap = ?n/2?，gap = ?gap/2?，直到gap = 1。后來knuth 提出取gap = ?gap/3? +1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。,,算法分析,對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。但想要弄清關(guān)鍵碼比較次

42、數(shù)和對(duì)象移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。,Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng) n 很大時(shí)，關(guān)鍵碼平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在 n1.25 到 1.6n1.25 的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。,,交換排序 ( Exchange Sort ),起泡排序的基本方法是：設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為 n。最多作 n-1 趟，i = 1, 2, ?, n-

43、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

44、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

45、 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 ){ BubbleExchange (

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

47、e-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,有交換 }},第 i 趟對(duì)

48、待排序?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ì)象。這是最好的情形。,,最壞的情形是算法執(zhí)行了n-1趟

49、起泡，第 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è)子序列： 左側(cè)子

50、序列中所有對(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è)子序列 LeftList 和

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

52、 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,25,16,0

53、8,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, const i

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

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

56、ent pivot = list.Vector[low]; for ( int i = low+1; i <= high; i++ ) if ( list.Vector[i].getKey ( ) < pivot.getKey( ) && ++pivotpos != i ) Swap ( list.Vector[pivotpos], lis

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

58、于基準(zhǔn)對(duì)象關(guān)鍵碼的對(duì)象都移到序列左側(cè)，最后基準(zhǔn)對(duì)象安放到位，函數(shù)返回其位置。,,21,,25*,25,49,08,16,,算法分析,從快速排序算法的遞歸樹可知，快速排序的趟數(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è)元素的序列進(jìn)行排序所需的

59、時(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) = o(n log

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

61、劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。這樣，必須經(jīng)過 n-1 趟才能把所有對(duì)象定位，而且第 i 趟需要經(jīng)過 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è)要求很難辦到。有一

62、種改進(jìn)辦法：取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最后一個(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,0

63、8,16,21 25 25* 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

64、 較大的平均情況而言，快速排序是“快速”的，但是當(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

65、= 1,i = 2,選擇排序的基本思想是：每一趟 (例如第 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ì)象中

66、的第一個(gè)對(duì)象，則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào)； 在這組對(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++ ) SelectEx

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

68、 list.Vector[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

69、 3 4 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