大三上數(shù)據(jù)結(jié)構(gòu)第8章排序-1zt2010

1第8章排序28.1排序的基本概念排序就是將一組雜亂無(wú)章的數(shù)據(jù)按規(guī)定的次序重新排列起來(lái)。排序的目的之一就是方便數(shù)據(jù)的查找。31．排序排序（Sorting）就是整理文件中的記錄，將一組雜亂無(wú)章的的數(shù)據(jù)按關(guān)鍵字遞增（或遞減）的次序重新排列，使之成為一個(gè)有序序列的過(guò)程。例如，有10個(gè)記錄的無(wú)序文件，其排序前后記錄及其對(duì)應(yīng)的關(guān)鍵字如下：4排序后關(guān)鍵字最小的記錄R7排在序列的最前面，關(guān)鍵字最大的記錄R3排在序列最后面。排序后整個(gè)序列按記錄關(guān)鍵字從小到大順序排列組成為一個(gè)有序文件。52．關(guān)鍵字（Key）假設(shè)被排序的對(duì)象是由若干個(gè)記錄組成的文件，而記錄則由若干個(gè)數(shù)據(jù)項(xiàng)組成，其中可用來(lái)惟一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)，稱為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字（key）。在文件中能夠惟一區(qū)別一個(gè)記錄的關(guān)鍵字稱為主關(guān)鍵字；不同記錄，其關(guān)鍵字值可能相同的關(guān)鍵字稱為次關(guān)鍵字。關(guān)鍵字也稱為關(guān)鍵碼或排序碼。6表8.1是一個(gè)學(xué)生成績(jī)文件。記錄中的哪個(gè)數(shù)據(jù)項(xiàng)可以當(dāng)主關(guān)鍵字、次關(guān)鍵字？表8.1學(xué)生成績(jī)登記表7關(guān)鍵字可用來(lái)作為排序運(yùn)算的依據(jù)。選取記錄中的哪一項(xiàng)作為排序的關(guān)鍵字（或排序碼），應(yīng)根據(jù)問(wèn)題的要求而定。例如，若將成績(jī)登記表按學(xué)生證號(hào)排列，主關(guān)鍵字“學(xué)生證號(hào)”就是當(dāng)前的排序碼，見(jiàn)表8.1；若按學(xué)生的成績(jī)總分排名次，次關(guān)鍵字“總分”就是當(dāng)前的排序碼，見(jiàn)表8.2。表8.2學(xué)生成績(jī)統(tǒng)計(jì)表8

3．排序的穩(wěn)定性與不穩(wěn)定性假設(shè)n個(gè)待排序的序列中存在多個(gè)記錄具有相同的次關(guān)鍵字值Ki（Ki表示第i個(gè)記錄的關(guān)鍵字，i=1,2,…,n1,n），若Ki=Kj（j=1,2,…,n1,n,且ji），且排序前記錄Ri排在記錄Rj之前。若采用的排序方法，使排序后的記錄Ri仍然排在記錄Rj的前面，則稱此排序方法是穩(wěn)定排序，反之稱此排序方法是不穩(wěn)定排序。穩(wěn)定排序OR不穩(wěn)定排序？9

4．內(nèi)部排序與外部排序根據(jù)排序元素所在位置的不同,排序分:

內(nèi)排序和外排序。內(nèi)排序

在排序過(guò)程中，所有元素調(diào)到內(nèi)存中進(jìn)行的排序，稱為內(nèi)排序。外排序在數(shù)據(jù)量大的情況下，只能分塊排序，但塊與塊間不能保證有序。10外排序速度比內(nèi)排序速度要慢得多。內(nèi)排序適用于記錄個(gè)數(shù)不多的小文件，外排序則適用于記錄個(gè)數(shù)比較多，不能一次將全部記錄裝入內(nèi)存的大文件。內(nèi)排序方法很多，按所用的策略不同，可以分為5類：插入排序、選擇排序、交換排序、歸并排序和分配排序。內(nèi)排序是外排序的基礎(chǔ)，外排序算法的原理與內(nèi)排序算法的原理很多都是相同的，但具體實(shí)現(xiàn)的函數(shù)差別很大。115．排序方法的評(píng)價(jià)標(biāo)準(zhǔn)評(píng)價(jià)排序算法好與壞的標(biāo)準(zhǔn)主要有兩條：排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度

-內(nèi)排序：時(shí)間主要耗費(fèi)在數(shù)據(jù)比較與數(shù)據(jù)移動(dòng)上，其時(shí)間復(fù)雜度可用排序過(guò)程中數(shù)據(jù)的比較次數(shù)和數(shù)據(jù)的移動(dòng)次數(shù)來(lái)衡量。

-外排序：時(shí)間花在讀寫(xiě)外存上，用讀/寫(xiě)外存的次數(shù)來(lái)衡量其效率（時(shí)間復(fù)雜度）。

-一般情況下，排序算法的時(shí)間復(fù)雜度是按平均情況進(jìn)行估計(jì)的，但有時(shí)也按最好的情況和最壞的情況進(jìn)行估算。12空間復(fù)雜度是指執(zhí)行排序算法所需要的附加存儲(chǔ)空間。

-當(dāng)排序算法中使用的輔助存儲(chǔ)單元與排序?qū)ο蟮膫€(gè)數(shù)無(wú)關(guān)時(shí)，其空間復(fù)雜度為O(1)。

-空間復(fù)雜度為O(1)的排序算法亦稱為原地排序算法。原地排序算法就是利用原來(lái)存放記錄的數(shù)組空間來(lái)重新按關(guān)鍵字大小存儲(chǔ)記錄的。此外，排序算法的穩(wěn)定性和簡(jiǎn)單性也是衡量一個(gè)排序算法好與壞的重要指標(biāo)。136．排序算法的存儲(chǔ)實(shí)現(xiàn)排序算法通常采用以下3種存儲(chǔ)結(jié)構(gòu)：①采用順序表（即一維數(shù)組）作為存儲(chǔ)結(jié)構(gòu)：排序過(guò)程就是對(duì)記錄本身進(jìn)行物理重排的過(guò)程，即通過(guò)記錄關(guān)鍵字的比較和移動(dòng)，將記錄移動(dòng)到合適的位置上。②采用鏈表作為存儲(chǔ)結(jié)構(gòu)：排序過(guò)程中不需要移動(dòng)記錄，僅修改指針即可。③采用輔助表作為存儲(chǔ)結(jié)構(gòu)：有些排序方法難以在鏈表上實(shí)現(xiàn)，為了避免在排序過(guò)程中移動(dòng)記錄，可以為文件另外建立一個(gè)輔助表，例如，建立一個(gè)由記錄關(guān)鍵字和指向記錄的指針組成的索引表。這樣，在排序過(guò)程中只需對(duì)這個(gè)輔助表的表目進(jìn)行物理重排，即只移動(dòng)輔助表的表目而不移動(dòng)記錄本身。14為簡(jiǎn)單，書(shū)中算法采用順序表存儲(chǔ)待排序記錄：#defineMAX400/*MAX為記錄數(shù)組最大數(shù)*/typedefintdatatype;/*定義關(guān)鍵字類型*/typedefstructrecord/*定義記錄為結(jié)構(gòu)類型*/{intkey;/*記錄的關(guān)鍵字域*/datatypeother;/*記錄的其他域*/}rectype*s1,r[MAX]; /*r[MAX]數(shù)組存放原始數(shù)據(jù)，*s1存放排序后的數(shù)據(jù)*/158.2插入排序插入排序類似于玩紙牌時(shí)整理手中紙牌的過(guò)程。插入排序的基本方法是：每次將一個(gè)待排序的記錄按其關(guān)鍵字大小，插到前面已排好的序列中的適當(dāng)位置，直到全部記錄插入為止。常用的插入排序方法有：直接插入排序折半插入排序（略）表插入排序（略）希爾排序168.2.1直接插入排序1、直接插入排序的基本思想把數(shù)組R[n]中待排序的n個(gè)元素看成為一個(gè)有序表和一個(gè)無(wú)序表，開(kāi)始時(shí)有序表只有一個(gè)元素R[1]，而無(wú)序表中包含有n1個(gè)元素R[2]～R[n]。排序過(guò)程中，每次取出無(wú)序表中第一個(gè)元素，將它插到有序表的適當(dāng)位置上，使之成為新的有序表，這樣經(jīng)過(guò)n1次插入后，無(wú)序表變成為空表，而有序表包含有n個(gè)元素，至此排序完畢。{{R1}，{R2，R3，R4，…,Rn}}{{R1(1)，R2(1)}，{R3(1)，R4(1)…,Rn(1)}}

…...{{R1(n-1)，R2(n-1)

，…},{Rn(n-1)}}17圖8.1直接插入排序過(guò)程示例【例8.1】假設(shè)數(shù)組R有8個(gè)待排序的記錄，它們的關(guān)鍵字分別為：18Step1

從有序數(shù)列{R1}和無(wú)序數(shù)列{R2,R3,…,Rn}開(kāi)始進(jìn)行排序;Step2

處理第i個(gè)元素時(shí)(i=2,3,…,n),數(shù)列

{R1,R2,…,Ri-1}是已有序的,而數(shù)列{Ri,Ri+1,…,Rn}是無(wú)序的。用Ri與Ri-1、Ri-2,…,R1進(jìn)行比較,找出合適的位置將Ri插入。（從后往前比較）Step3

重復(fù)Step2，共進(jìn)行n-1的插入處理，數(shù)列全部有序。（從小到大排序）插入排序算法步驟19voidinsert_sort(r)/*直接插入排序*/rectyper[];{inti,j,n=NUM;/*NUM為實(shí)際輸入的記錄數(shù)*/for(i=1;i<=n;i++)/*i<=NUM條件很重要*/

{r[0]=r[i];/*r[0]是監(jiān)視哨,也是待插入數(shù)據(jù)*/j=i-1;/*j+1最終存放插入位置*/while(r[0].key<r[j].key)/*查找r[i]合適插入的位置,

從后向前依次比較，找到插入位置*/

r[j+1]=r[j--];

/*將大于r[i].key記錄后移等價(jià)于r[j+1]=r[j];j--;*/r[j+1]=r[0]; /*將R[i]插到有序表合適位置上*/}}/*INSERTSORT*//*直接插入排序—對(duì)數(shù)組R按遞增順序進(jìn)行插入排序算法*/20算法中記錄r[0]有兩個(gè)作用：一是在進(jìn)入查找循環(huán)之前，它保存了r[i]的值，使得不致因記錄的后移而丟失r[i]的內(nèi)容；二是在while循環(huán)中“監(jiān)視”下標(biāo)變量j是否越界，一旦越界（即j＜0），r[0]將自動(dòng)控制while循環(huán)的結(jié)束，從而避免了在while循環(huán)中每一次都要檢測(cè)j是否越界（即省略了循環(huán)條件j≥1）。因此，r[0]也稱為“監(jiān)視哨”。采用這種程序設(shè)計(jì)技巧，使得循環(huán)條件的測(cè)試時(shí)間大約減少一半，而對(duì)于記錄數(shù)較大的文件，節(jié)省的時(shí)間更加相當(dāng)可觀，希望能夠掌握這種程序設(shè)計(jì)技巧。

21沒(méi)有監(jiān)視哨的算法Voidinsert_sort(item)

rectype*item,n;{inti，j，t;for（i=1；i<n;i++)/*n-1次循環(huán)*/{t=item[i];/*要插入的元素*/j=i-1;/*有序部分起始位置*/

while(j>=0&&t<item[j])/*尋找插入位置*/{item[j+1]=item[j];/*當(dāng)前元素后移*/j--;}item[j+1]=t;/*插入該元素*/}}22【算法分析】直接插入排序算法時(shí)間復(fù)雜度可分最好、最壞和平均三種情況來(lái)考慮。（1）直接插入排序算法是由兩重循環(huán)組成的，對(duì)于由n個(gè)記錄組成的序列，外循環(huán)表示要進(jìn)行插入排序的趟數(shù)，內(nèi)循環(huán)表示完成一趟排序所要進(jìn)行的記錄關(guān)鍵字之間的比較和記錄的后移。23當(dāng)參加排序的記錄關(guān)鍵字已按升序排列時(shí)，這是最好的情況。在這種情況下，每趟排序過(guò)程中，while語(yǔ)句的循環(huán)次數(shù)為0，僅需進(jìn)行一次關(guān)鍵字的比較，且無(wú)須后移記錄。但是，在進(jìn)入while循環(huán)之前，將r[i]保存到監(jiān)視哨r[0]中需移動(dòng)一次記錄，在該循環(huán)結(jié)束之后，將監(jiān)視哨r[i]插到r[j+1]中也需移動(dòng)一次記錄。因此，每趟排序過(guò)程中，關(guān)鍵字比較次數(shù)為1，記錄的移動(dòng)次數(shù)為2。整個(gè)排序過(guò)程中，關(guān)鍵字總的比較次數(shù)最小值Cmin和記錄總的移動(dòng)次數(shù)最小值Mmin為：24（2）當(dāng)參加排序的記錄關(guān)鍵字按逆序排列時(shí)，這是最壞的情況。在這種情況下，第i趟排序過(guò)程中，while語(yǔ)句的循環(huán)次數(shù)為i，有序區(qū)中所有i-1個(gè)記錄均向后移動(dòng)一個(gè)位置，再加上while循環(huán)前后的兩次移動(dòng)，因此，在每趟排序過(guò)程中，關(guān)鍵字的比較次數(shù)為i，記錄的移動(dòng)次數(shù)為i-1+2。那么整個(gè)排序過(guò)程中，關(guān)鍵字總的比較次數(shù)的最大值Cmax和記錄移動(dòng)次數(shù)最大值Mmax為：25（3）在平均情況下，參加排序的原始記錄關(guān)鍵字是隨機(jī)排列的。我們可取上述最小值和最大值的平均值，作為直接插入排序所需的平均比較次數(shù)和平均移動(dòng)次數(shù)。因?yàn)榈趇趟排序過(guò)程中，關(guān)鍵字的平均比較次數(shù)為(1+i)/2，記錄的平均移動(dòng)次數(shù)為(i+3)/2，因此，對(duì)于n個(gè)記錄進(jìn)行直接插入排序時(shí)，總共需要進(jìn)行n-1趟排序才能完成排序運(yùn)算，其關(guān)鍵字的平均比較次數(shù)Cavg和記錄的平均移動(dòng)次數(shù)Mavg為：26直接插入排序算法的時(shí)間復(fù)雜度為O(n2)。直接插入排序所需的輔助空間是一個(gè)監(jiān)視哨，其作用是暫時(shí)存放待插入的元素，故空間復(fù)雜度為O(1)。直接插入排序是穩(wěn)定的排序方法。直接插入排序的算法簡(jiǎn)單，容易實(shí)現(xiàn)。當(dāng)記錄數(shù)n很大時(shí)，不適合進(jìn)行直接插入排序。278.2.2希爾排序希爾排序基本思想：不斷把待排序的記錄分成若干個(gè)小組，然后對(duì)同一組內(nèi)的記錄進(jìn)行排序。在分組時(shí)，始終保證當(dāng)前組內(nèi)的記錄個(gè)數(shù)超過(guò)前面分組排序時(shí)組內(nèi)的記錄個(gè)數(shù)。28希爾排序的過(guò)程如下：①以d1（0＜d1＜n1）為步長(zhǎng)（增量），把數(shù)組R中的n個(gè)元素分為d1個(gè)小組，將所有下標(biāo)距離為d1的記錄放在同一組中。②對(duì)每個(gè)組內(nèi)的記錄分別進(jìn)行直接插入排序。這樣一次分組排序過(guò)程稱為一次排序。③以d2（d1＞d2）為步長(zhǎng)（增量），重復(fù)上述步驟，直到di=1，把所有n個(gè)元素放在一個(gè)組內(nèi)，進(jìn)行直接插入排序?yàn)橹?。該次排序結(jié)束時(shí)，整個(gè)序列的排序工作完成。29希爾排序?qū)嶋H上是對(duì)直接插入排序的一種改進(jìn)。

-在希爾排序中，開(kāi)始增量比較大，分組較多，每個(gè)組內(nèi)記錄個(gè)數(shù)較少，因而記錄的比較次數(shù)和移動(dòng)次數(shù)都比較少，在小組內(nèi)用直接插入排序的時(shí)間效率很高。盡管增量逐漸變小，分組較少，每個(gè)組內(nèi)記錄個(gè)數(shù)逐漸增多，但同時(shí)記錄越來(lái)越接近有序，因而記錄的比較次數(shù)和移動(dòng)次數(shù)越來(lái)越少，從而使直接插入排序的時(shí)間效率越來(lái)越高。30在希爾排序中，增量序列的選取到目前為止尚未得到一個(gè)最佳值，但最后一次排序時(shí)的增量值必須為1。一般選取增量序列的規(guī)則是：取di+1為di/3～di/2之間的數(shù)。最簡(jiǎn)單的方法是取di+1=di/2。注意：在一次分組排序過(guò)程中，可用直接插入排序算法對(duì)組內(nèi)記錄進(jìn)行排序，也可采用其他合適的排序算法進(jìn)行組內(nèi)的排序。31【例8.2】假設(shè)數(shù)組R有12個(gè)待排序的記錄，它們的關(guān)鍵字分別為：(65,34,25,87,12,38,56,46,14,77,92,23)

用希爾排序方法進(jìn)行排序，請(qǐng)給出排序過(guò)程?！窘狻肯柵判虻倪^(guò)程如圖8.2所示。在圖中，同一連線上關(guān)鍵字表明它們所屬的記錄是放在同一個(gè)組中的。由于數(shù)組待排序的記錄數(shù)n=12，若按di+1=di/2選取增量序列，那么所得到的增量序列為：d1=n/2=12/2=6，d2=d1/2=6/2=3，d3=d2/2=3/2=1。32圖8.2希爾排序過(guò)程示意圖33Step1

將n個(gè)元素?cái)?shù)列分為n個(gè)部分，元素比較間距為d。step2

在第i步，兩元素比較的間距取

di+1=di/2

若Ri+1>Ri,則交換它們的位置。Step3

重復(fù)上述步驟，直到dK=1。算法步驟34/*希爾排序——取增量為di+1=di/2的希爾排序-1*/voidshell_sort(r)rectyper[];{inti,n,jump,change,temp,m;/*change為交換標(biāo)志，jump為增量步長(zhǎng)*/jump=NUM;n=NUM;/*NUM為順序表的實(shí)際長(zhǎng)度*/

while(jump>0){jump=jump/2;/*取步長(zhǎng)di+1=di/2*/

do{change=0;/*change=0表示未交換*/

for(i=1;i<=n-jump;i++){m=i+jump;

35

/*希爾排序——取增量為di+1=di/2的希爾排序-2*/if(r[i].key>r[m].key) {temp=r[m].key;r[m].key=r[i].key;r[i].key=temp;change=1;/*change=1表示有交換*/

}/*if*/}/*for*//*本趟排序完成*/}while(change==1);

/*當(dāng)change=0時(shí)終止本趟排序*/

}/*while*//*當(dāng)jump=1且change=0時(shí)終止*/}/*SHELLSORT*/36【算法分析】希爾排序比直接插入排序速度快。希爾排序算法的時(shí)間復(fù)雜度在O(nlog2n)～O(n2)之間，大致為O(n1.5)。希爾排序算法的空間復(fù)雜度為O(1)。由于希爾排序是按增量分組進(jìn)行排序的，所以希爾排序是一種不穩(wěn)定的排序方法。37第8章排序8.3交換排序

8.3.1冒泡排序

8.3.2快速排序 388.3交換排序利用交換記錄位置進(jìn)行排序方法稱為交換排序。交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，若發(fā)現(xiàn)兩個(gè)記錄關(guān)鍵字的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。交換排序的特點(diǎn)是：通過(guò)記錄的交換將關(guān)鍵字較大的記錄向文件的尾部移動(dòng)，而將關(guān)鍵字較小的記錄向文件的前部移動(dòng)。常用的兩種交換排序：冒泡排序和快速排序。398.3.1冒泡排序冒泡排序的基本思想是：將待排序的記錄排列成一個(gè)垂直的序列，而不是一個(gè)水平的序列。把記錄想象成水箱里的氣泡，其關(guān)鍵字相當(dāng)于氣泡的重量。對(duì)所有待排序的記錄掃描一趟以后，通過(guò)兩個(gè)相鄰記錄之間的比較和交換，使得氣泡下沉或上升到其重量應(yīng)該到的最終位置上。40冒泡排序的具體過(guò)程是：把第n個(gè)記錄的關(guān)鍵字與第n1個(gè)記錄的關(guān)鍵字進(jìn)行比較，如果r[n].key＜r[n1].key，則交換兩個(gè)記錄r[n]和r[n1]的位置，否則不交換；然后再把第n1個(gè)記錄的關(guān)鍵字與第n2個(gè)記錄的關(guān)鍵字進(jìn)行比較；其余類推，直到第2個(gè)記錄與第1個(gè)記錄的關(guān)鍵字比較完為止，這個(gè)過(guò)程就稱為一趟冒泡排序。然后對(duì)剩下的n1個(gè)記錄進(jìn)行第二趟冒泡排序，使關(guān)鍵字次小的記錄上浮到數(shù)組第二個(gè)單元r[2]中；重復(fù)進(jìn)行n1趟后，輕者上浮而重者下沉，則整個(gè)冒泡排序結(jié)束。41【例8.3】假設(shè)n=8，數(shù)組R中8個(gè)記錄的關(guān)鍵字分別為：（53,36,48,36,60,17,18,41）用冒泡法進(jìn)行排序，請(qǐng)給出排序的過(guò)程。【解】第一趟冒泡排序過(guò)程如圖8.3所示，冒泡排序全部過(guò)程則如圖8.4所示。在圖8.4中，第一列為初始的關(guān)鍵字序列，從第二列起依次為各趟冒泡排序的結(jié)果，黑方括號(hào)括起來(lái)的記錄為當(dāng)前的無(wú)序區(qū)。42圖8.3第一趟冒泡排序過(guò)程示例43圖8.4從下往上的冒泡排序全過(guò)程示意圖44/*冒泡排序算法——從下往上掃描的冒泡排序*/bubble_sort(r) rectyper[];{inti,j,noswap=0,n=NUM;/*noswap為交換標(biāo)志*/rectypetemp;

for(i=1;i<n;i++)/*進(jìn)行n-1趟冒泡排序*/{noswap=1;/*noswap=1表示沒(méi)有記錄交換*/

for(j=n;j>=i;j--)/*從下往上掃描*/if(r[j].key<r[j-1].key)/*交換記錄*/{temp.key=r[j-1].key;r[j-1].key=r[j].key;r[j].key=temp.key;noswap=0;}/*if*/

if(noswap)break;}/*for*/

}/*BUBBLESORT*/45算法說(shuō)明從冒泡排序?qū)嵗梢钥闯觯簩?duì)n個(gè)記錄進(jìn)行冒泡排序時(shí)，至多進(jìn)行n1趟排序。如果本趟冒泡排序過(guò)程沒(méi)有交換任何記錄，則說(shuō)明全部記錄已經(jīng)有序，排序就此結(jié)束。為此，在算法中設(shè)置一個(gè)標(biāo)志變量noswap，用于判斷本趟冒泡排序過(guò)程是否有記錄交換。在每趟冒泡排序之前，置noswap=1；本趟排序過(guò)程中若交換記錄，則置noswap=0；每趟冒泡排序之后，若noswap=1，則表明全部記錄已經(jīng)有序，算法可以就此終止。

46【算法分析】冒泡排序的執(zhí)行時(shí)間與待排序記錄的原始狀態(tài)有很大關(guān)系。若原始記錄的初始狀態(tài)是遞減有序（即按“逆序”排列）的，這時(shí)需要進(jìn)行n-1趟排序，每趟冒泡排序要進(jìn)行n-i次關(guān)鍵字的比較（1≤i≤n-1），且每次比較都必須交換兩個(gè)記錄的位置，記錄移動(dòng)次數(shù)為3次。這是最壞的情況，此時(shí)關(guān)鍵字的比較次數(shù)Cmax和記錄的移動(dòng)次數(shù)Mmax均達(dá)到最大值為：因此，在最壞的情況下，冒泡排序的時(shí)間復(fù)雜度為O(n2)。47若原始記錄的初始狀態(tài)是遞增有序（即按“正序”排列）的，這時(shí)只需進(jìn)行一趟冒泡排序過(guò)程就能結(jié)束排序。在排序過(guò)程中，記錄關(guān)鍵字總的比較次數(shù)為n-1次，記錄總的移動(dòng)次數(shù)為0次。這是最好的情況，此時(shí)Cmin=n-1，Mmin=0，冒泡排序的時(shí)間復(fù)雜度為O(n)。在平均情況下，冒泡排序的比較次數(shù)和移動(dòng)次數(shù)大約是最壞情況的一半。因此，冒泡排序算法的平均時(shí)間復(fù)雜度為O(n2)，冒泡排序算法的空間復(fù)雜度為O(1)。顯然，冒泡排序算法是一種穩(wěn)定的排序方法。在一般情況下，冒泡排序比直接插入排序和直接選擇排序需要移動(dòng)記錄的次數(shù)多，所以它是這三種簡(jiǎn)單排序方法中速度最慢的一個(gè)。但是，當(dāng)原始的記錄序列為有序時(shí)，則冒泡排序又是三者中速度最快的一種排序方法。488.3.2快速排序快速排序是一種交換排序，是對(duì)冒泡排序的改進(jìn)，是目前所有排序方法中速度最快的一種。在冒泡排序中，記錄的比較和交換是在相鄰兩個(gè)單元中進(jìn)行的，記錄每次的交換只能上移或者下移一個(gè)相鄰位置，因而總的比較次數(shù)和移動(dòng)次數(shù)比較多；而在快速排序中，記錄的比較和移動(dòng)從兩端向中間進(jìn)行，關(guān)鍵字大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離比較遠(yuǎn)，因而總的比較次數(shù)和移動(dòng)次數(shù)比較少。49快速排序的基本思想是：在待排序的n個(gè)記錄中任意選擇一個(gè)記錄作為標(biāo)準(zhǔn)記錄（通常選第一個(gè)記錄作為標(biāo)準(zhǔn)記錄），以該記錄的關(guān)鍵字為基準(zhǔn)，將當(dāng)前的無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序子區(qū)，使左邊無(wú)序子區(qū)中各記錄的關(guān)鍵字均小于基準(zhǔn)記錄的關(guān)鍵字，使右邊無(wú)序子區(qū)中各記錄的關(guān)鍵字均大于或等于基準(zhǔn)記錄的關(guān)鍵字，而標(biāo)準(zhǔn)記錄則位于兩個(gè)無(wú)序區(qū)的中間位置上（也就是該記錄最終排序的位置上），分別對(duì)左右兩個(gè)無(wú)序區(qū)繼續(xù)進(jìn)行上述的劃分過(guò)程，直到無(wú)序區(qū)中所有的記錄都排好序?yàn)橹?。在快速排序中，將待排序區(qū)間按照標(biāo)準(zhǔn)記錄關(guān)鍵字分為左右兩個(gè)無(wú)序區(qū)的過(guò)程稱為一趟快速排序（或一次劃分）。50

【例8.4】假設(shè)n=8，數(shù)組R中8個(gè)記錄的關(guān)鍵字分別為：（49,38,65,97,76,13,27,49）試給出其第一趟快速排序的劃分過(guò)程和結(jié)果。

【解】若選取第一個(gè)記錄作為標(biāo)準(zhǔn)記錄temp，則快速排序第一次劃分過(guò)程如圖8.5所示。在圖8.5中，方括號(hào)內(nèi)為待排序的無(wú)序區(qū)。帶方框和陰影的數(shù)據(jù)是標(biāo)準(zhǔn)記錄temp的關(guān)鍵字49，在劃分過(guò)程中它并沒(méi)有真正進(jìn)行交換，而是在劃分結(jié)束時(shí)才將其放到正確的位置上。

51圖8.5快速排序的一次劃分過(guò)程示例關(guān)鍵字temp=4952顯然，經(jīng)過(guò)一次劃分后，標(biāo)準(zhǔn)記錄將整個(gè)無(wú)序區(qū)分成左右兩個(gè)無(wú)序區(qū)，用同樣的方法對(duì)左右兩個(gè)無(wú)序區(qū)繼續(xù)進(jìn)行劃分，直到各個(gè)子區(qū)間的長(zhǎng)度為1時(shí)終止。圖8.6是在快速排序執(zhí)行過(guò)程中，每一次劃分后關(guān)鍵字的排列情況，圖中加陰影的記錄為本次快速排序的基準(zhǔn)記錄。53圖8.6快速排序執(zhí)行過(guò)程示例54一趟快速排序的具體做法是：①將標(biāo)準(zhǔn)記錄r[s]保存到臨時(shí)變量temp中，temp=r[s]。②令j從n起向左掃描，將r[j].key與temp.key進(jìn)行比較，直到找到第一個(gè)滿足temp.key＞r[j].key條件的記錄時(shí)停止，然后將r[j]移到r[i]的位置上。③令i從i+1起向右掃描，將r[i].key與temp.key進(jìn)行比較，直到找到第一個(gè)滿足temp.key<r[i].key記錄時(shí)停止，然后將r[i]移到r[j]的位置上。④反復(fù)交替執(zhí)行步驟②和步驟③，直到指針i和j指向同一個(gè)位置（即i=j）時(shí)為止，此時(shí)i就是標(biāo)準(zhǔn)記錄temp最終存放的位置，因此將temp存放到r[i]單元就完成了一次劃分過(guò)程。至此，一趟快速排序過(guò)程完成，數(shù)組被分成r[s..i1]和r[i+1..t]兩個(gè)部分。5556/*快速排序算法——對(duì)R[hs]到R[ht]進(jìn)行快速排序*/voidquick_sort(r,hs,ht)/*對(duì)R[hs]到R[ht]進(jìn)行快速排序*/

rectyper[];inths,ht;{inti;if(hs<ht)/*只有一個(gè)或無(wú)記錄時(shí)無(wú)須排序*/{i=partition(r,hs,ht);/*R[hs]到R[ht]一次劃分*/

quick_sort(r,hs,i-1);/*遞歸處理左區(qū)間*/