《軟件技術(shù)基礎(chǔ)》課件第9章

9.1排序的基本概念9.2插入排序9.3交換排序9.4直接選擇排序9.5歸并排序9.6各種內(nèi)部排序方法的比較和選擇習(xí)題9第9章排序9.1排序的基本概念排序的定義如下：假設(shè)序列包含n個(gè)記錄{R1,R2,…,Rn}，其對(duì)應(yīng)的關(guān)鍵字值序列為{k1,k2,…,kn}，根據(jù)1,2,…,n的一種排列p1,p2,…,pn，將這n個(gè)記錄重排為有序序列{Rp1,Rp2,…,Rpn}，滿(mǎn)足kp1≤kp2≤…≤kpn(或kp1≥kp2≥…≥kpn)。上述定義中，如果ki是主關(guān)鍵字，則排序結(jié)果是唯一的；如果ki是次關(guān)鍵字，則兩個(gè)關(guān)鍵字值可能相等，此時(shí)排序結(jié)果就不是唯一的。假設(shè)記錄Ri和Rj的關(guān)鍵字ki=kj，如果在原始序列中Ri排在Rj之前，而排序后的序列中Ri仍然排在Rj之前，則稱(chēng)此排序是穩(wěn)定的；反之，如果排序后變成Ri排在Rj之后，則稱(chēng)此排序是不穩(wěn)定的。根據(jù)排序過(guò)程中需要涉及的存儲(chǔ)器不同，可將排序分為內(nèi)部排序和外部排序。內(nèi)部排序是指整個(gè)排序過(guò)程都在內(nèi)存中進(jìn)行的排序；外部排序是指待排序記錄的數(shù)量很大，在排序過(guò)程中，除使用內(nèi)存外，還需對(duì)外存進(jìn)行訪問(wèn)。顯然，內(nèi)部排序適用于記錄個(gè)數(shù)較少的序列，外部排序則適用于記錄個(gè)數(shù)太多、需同時(shí)使用內(nèi)存和外存的長(zhǎng)序列。

本章只介紹內(nèi)部排序。根據(jù)不同算法所用的策略，內(nèi)部排序方法可分為插入排序、選擇排序、交換排序、歸并排序及基數(shù)排序等幾大類(lèi)。每一種方法各有優(yōu)缺點(diǎn)，適合于不同的應(yīng)用場(chǎng)合。因此，要想簡(jiǎn)單地評(píng)價(jià)哪種方法最好且能夠普遍適用是很困難的。判斷排序算法好壞的標(biāo)準(zhǔn)主要有兩條：(1)算法執(zhí)行所需要的時(shí)間；(2)算法執(zhí)行所需要的附加空間。另外要考慮的一個(gè)因素是算法本身的復(fù)雜程度。排序算法所需的附加空間量一般都不大，所以排序算法的時(shí)間復(fù)雜度是衡量算法好壞的最重要的標(biāo)志。排序所需的時(shí)間主要是指算法執(zhí)行中關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)。因此，后面的章節(jié)將會(huì)詳細(xì)討論排序算法中的比較次數(shù)和移動(dòng)次數(shù)。

待排序的記錄可有下列三種存儲(chǔ)結(jié)構(gòu)：

(1)以一組連續(xù)的地址單元(如一維數(shù)組)作為存儲(chǔ)結(jié)構(gòu)，待排序記錄的次序由其物理位置決定。在排序過(guò)程中，必須移動(dòng)記錄來(lái)進(jìn)行物理位置上的重排，即通過(guò)比較和判定把記錄移到合適的位置。

(2)以鏈表作為存儲(chǔ)結(jié)構(gòu)，記錄之間的次序由指針決定。因此，在排序過(guò)程中僅需修改指針。

(3)待排序記錄存儲(chǔ)在一組連續(xù)的地址單元內(nèi)，此時(shí)若要避免排序過(guò)程中記錄的移動(dòng)，可以為該序列建立一個(gè)輔助表(如索引表)，在排序過(guò)程中只需對(duì)這個(gè)輔助的表目進(jìn)行物理重排，而不移動(dòng)記錄本身。

為方便起見(jiàn)，本章假設(shè)記錄序列的存儲(chǔ)結(jié)構(gòu)為一維數(shù)組，關(guān)鍵字為整數(shù)。待排序記錄的數(shù)據(jù)類(lèi)型說(shuō)明如下：

typedefstruct //定義記錄為結(jié)構(gòu)類(lèi)型

{intkey; //關(guān)鍵字域

datatypeother; //其他數(shù)據(jù)域

}rectype;

rectypeR[n+1];//n為記錄總數(shù)，R[0]閑置或作為哨兵單元

9.2.1直接插入排序

直接插入排序(StraightInsertionSort)是一種最簡(jiǎn)單的排序方法。其基本思路是把關(guān)鍵字ki依次與有序區(qū)的關(guān)鍵字ki-1,ki-2,

…,k1進(jìn)行比較，找到應(yīng)該插入的位置，然后將ki插入。給定待排序的記錄序列為R[1]～R[n]，則初始有序區(qū)為{R[1]}，直接插入排序可以從i=2開(kāi)始，如算法9.1所示。9.2插入排序算法9.1中的基本操作是關(guān)鍵字比較和記錄移動(dòng)。記錄R[1]作為最初的有序區(qū)，從i=2開(kāi)始不斷將待插入記錄R[i]的關(guān)鍵字依次與有序區(qū)中記錄R[j](j=i

1,i

2,…,1)的關(guān)鍵字進(jìn)行比較。若R[j]的關(guān)鍵字大于R[i]的關(guān)鍵字，則將R[j]后移一個(gè)位置；若R[j]的關(guān)鍵字小于或等于R[i]的關(guān)鍵字，則查找過(guò)程結(jié)束，j+1即為R[i]的插入位置。數(shù)組單元R[0]預(yù)先對(duì)記錄R[i]進(jìn)行備份，使得在后移關(guān)鍵字比R[i]大的記錄時(shí)不致丟失R[i]中的內(nèi)容；R[0]在while循環(huán)中還可以作為“監(jiān)視哨”，以防下標(biāo)變量j越界。由于避免了每次while循環(huán)都要檢測(cè)j是否越界，測(cè)試循環(huán)條件的時(shí)間可以減少約一半。

根據(jù)算法9.1對(duì)待排序的一組記錄進(jìn)行排序，記錄的關(guān)鍵字分別為49,31,63,85,75,15,26,49

，直接插入排序過(guò)程如圖9.1所示。

直接插入排序的算法9.1非常簡(jiǎn)潔，容易實(shí)現(xiàn)，下面來(lái)分析它的效率。

從時(shí)間上看，整個(gè)排序過(guò)程只有兩種運(yùn)算，即比較關(guān)鍵字和移動(dòng)記錄。算法中的外循環(huán)表示要進(jìn)行n

1趟插入排序，內(nèi)循環(huán)的次數(shù)則取決于待排序關(guān)鍵字與有序區(qū)中i個(gè)關(guān)鍵字的關(guān)系。

圖9.1直接插入排序示例可以按兩種情況來(lái)考慮。當(dāng)一組記錄為正序時(shí)(這里按遞增有序)，每趟排序的關(guān)鍵字比較次數(shù)為1，記錄移動(dòng)次數(shù)是2次，即總的比較次數(shù)Cmin=n

1，總的移動(dòng)次數(shù)Mmin=2(n

1)；當(dāng)文件逆序時(shí)，要插入的第i個(gè)記錄均要與前i

1個(gè)記錄及“監(jiān)視哨”的關(guān)鍵字進(jìn)行比較，即每趟要進(jìn)行i次比較；從記錄移動(dòng)的次數(shù)來(lái)說(shuō)，每趟排序中除了上面提到的兩次移動(dòng)外，還需將關(guān)鍵字大于R[i]的記錄后移一個(gè)位置。這時(shí)關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)均取最大值，總的比較次數(shù)和記錄的移動(dòng)次數(shù)為：綜上可知，記錄關(guān)鍵字的分布對(duì)算法執(zhí)行過(guò)程中的時(shí)間消耗是有影響的。若在隨機(jī)情況下，即關(guān)鍵字各種排列出現(xiàn)的概率相同，則可取上述兩種情況的平均值作為比較和記錄移動(dòng)的平均次數(shù)，約為n2/4。由此，直接插入排序的時(shí)間復(fù)雜度為O(n2)。

從空間上看，直接插入排序只需要一個(gè)記錄的輔助空間R[0]，空間復(fù)雜度即為O(1)。

直接插入排序是穩(wěn)定的排序方法。

9.2.2希爾排序

希爾排序(Shell’sSort)又稱(chēng)為“縮小增量排序”(DiminishingIncrementSort)，是一種改進(jìn)的插入排序方法。該方法是D.L.Shell于1959年提出的，故用他的名字命名。我們知道，直接插入排序算法的平均時(shí)間復(fù)雜度為O(n2)。但是，由于其算法簡(jiǎn)單，當(dāng)n較小時(shí)效率較高；另外，當(dāng)一組記錄有序時(shí)，其算法復(fù)雜度可以達(dá)到最優(yōu)，即O(n)。希爾排序正是基于這兩點(diǎn)來(lái)對(duì)直接插入排序進(jìn)行改進(jìn)的。

希爾排序的基本思想是：設(shè)置t個(gè)整數(shù)增量(d1>d2>…>dt－1>dt)，其中d1<n，dt=1；首先以d1為增量，將所有距離為d1倍數(shù)的記錄放在同一組中，可以得到d1個(gè)組，在各組內(nèi)進(jìn)行直接插入排序；然后取第二個(gè)增量d2，重復(fù)上述的分組和排序，直至增量dt=1。

設(shè)置增量序列時(shí)，要使得增量值沒(méi)有除1之外的公因子，而且最后一個(gè)增量值必須為1。下面先看一個(gè)具體例子。設(shè)待排序文件共有10個(gè)記錄，其關(guān)鍵字分別為49,31,63,85,75,15,26,49

,53,03，增量序列取值依次為5,3,1。排序過(guò)程如圖9.2所示。

圖9.2希爾排序示例由圖9.2可見(jiàn)，希爾排序的每一趟就是直接插入排序。增量越大，則得到的子序列越短，此時(shí)直接插入排序效率很高；而當(dāng)增量逐漸減小時(shí)，序列已逐漸有序，因此直接插入排序仍然很有效。當(dāng)增量為1時(shí)，此時(shí)所有的記錄已經(jīng)基本有序，并放在同一組中進(jìn)行直接插入排序。由此，希爾排序的速度較直接插入排序有很大的提高。

要注意的是，希爾排序中的子序列不是逐段選取的，而是根據(jù)增量值跳躍性的抽取。這樣可以實(shí)現(xiàn)排序記錄在較大范圍內(nèi)進(jìn)行移動(dòng)，從而提高了排序速度。但是由此導(dǎo)致了希爾排序是不穩(wěn)定的。

希爾排序的具體算法描述如算法9.2所示。

算法9.2中沒(méi)有設(shè)置“監(jiān)視哨”，單元R[0]僅作為暫存單元，在內(nèi)循環(huán)中增加了一個(gè)循環(huán)判定條件“j>0”，以防下標(biāo)越界。若要設(shè)置監(jiān)視哨，需要利用數(shù)組R的前t個(gè)單元作為監(jiān)視哨，待排序記錄則要從第t個(gè)單元開(kāi)始存儲(chǔ)。讀者可以自行完成。

希爾排序的時(shí)間復(fù)雜度取決于增量序列的選取，但是如何選取增量序列才能產(chǎn)生最好的排序效果，這一問(wèn)題至今沒(méi)有得到解決。希爾本人最初提出取d1=

n/2

，di+1=

di/2

，dt=1，t=

lb?n

，后來(lái)又有人提出其他選擇增量序列的方法，如di+1=

(di

1)/3

，dt=1，t=

log3n

1

以及di+1=

(di

1)/2

，dt=1，t=

lb?n

1

。大量實(shí)驗(yàn)表明，希爾排序所需的比較和移動(dòng)次數(shù)約為n1.3。

9.3.1起泡排序

起泡排序(BubbleSort)是最為人們所熟知的交換排序方法。它的過(guò)程非常簡(jiǎn)單：對(duì)縱向排列的關(guān)鍵字序列，按照自下而上的掃描方向?qū)蓛上噜彽年P(guān)鍵字進(jìn)行比較，若為逆序(即kj

1>kj)，則將兩個(gè)記錄交換位置；重復(fù)上述掃描排序過(guò)程，直至沒(méi)有記錄需要交換為止。

9.3交換排序第一趟掃描后，關(guān)鍵字最小的記錄將上升到第一個(gè)記錄的位置上；第二趟對(duì)后面的n

1個(gè)記錄重復(fù)同樣操作，把次小關(guān)鍵字的記錄安排在第二個(gè)記錄的位置上；重復(fù)上述過(guò)程，分析可知，在第n

1趟后，全部記錄都按關(guān)鍵字由小到大的順序排列完畢。在每一趟排序過(guò)程中，關(guān)鍵字最小的記錄通過(guò)比較和交換，會(huì)像氣泡一樣上浮至頂，而關(guān)鍵字較大的記錄則逐漸下沉，“起泡排序”的名稱(chēng)由此而來(lái)。起泡排序的過(guò)程如圖9.3所示。

圖9.3從下向上掃描的起泡排序示例(實(shí)際只掃描了5趟)對(duì)任一組記錄進(jìn)行起泡排序時(shí)，至多需要進(jìn)行n

1趟排序。但是，如果在排序過(guò)程中的某一趟掃描后，例如圖9.3中的第四趟排序后，待排序記錄已按關(guān)鍵字有序，因此起泡排序便可在此趟排序后終止。為了實(shí)現(xiàn)這一點(diǎn)，可以在起泡排序算法(算法9.3)中引入一個(gè)布爾量swap，在每趟排序開(kāi)始前，先將其置為FALSE，若排序過(guò)程中發(fā)生了交換，則將其置為T(mén)RUE。在一趟排序之后，如果swap仍為FALSE，則表示本趟未曾交換過(guò)記錄，此時(shí)可以終止算法。

下面分析起泡排序的性能。若記錄已按關(guān)鍵字有序排列，則只需進(jìn)行一趟掃描，而且比較次數(shù)和記錄移動(dòng)次數(shù)均為最小值：比較次數(shù)為n

1，記錄移動(dòng)次數(shù)為0。若記錄逆序排列，即按關(guān)鍵字遞減排列，則一共需進(jìn)行n

1趟掃描，比較次數(shù)和記錄移動(dòng)次數(shù)均達(dá)到最大值，分別為：

由此可知起泡排序的時(shí)間復(fù)雜度為O(n2)。

為提高起泡排序算法的效率，必須減少算法9.3中的比較和交換次數(shù)。除了設(shè)置交換標(biāo)志外，我們還可做如下的兩種改進(jìn)：

(1)在算法9.3中，一次掃描可以把最輕的氣泡上升至頂，而最重的氣泡僅能“下沉”一個(gè)位置。由此分析可知，對(duì)于關(guān)鍵字序列2,3,7,8,9,1，僅需一趟掃描就可以完成排序；但是對(duì)于關(guān)鍵字序列9,1,2,3,7,8，卻需要從下到上掃描五趟才能完成排序。這兩個(gè)序列都是僅有一個(gè)元素需要重排，但是產(chǎn)生了完全不同的結(jié)果。究其原因，正是掃描的方向?qū)е铝藘煞N情況下的不對(duì)稱(chēng)性。如果改變掃描方向?yàn)閺纳系较拢瑒t序列9,1,2,3,7,8也僅需一趟掃描?；谏鲜龇治?，我們可在排序過(guò)程中交替改變掃描方向，形成雙向起泡算法。該算法的實(shí)現(xiàn)留做習(xí)題。

(2)在每趟掃描中，記住最后一次交換發(fā)生的位置k，因?yàn)樵撐恢弥暗挠涗浂家延行颍碦[1..k

1]是有序區(qū)，R[k..n]是無(wú)序區(qū)，所以下一趟沿該方向掃描時(shí)可提前終止于位置k+1，而不必進(jìn)行到預(yù)定的下界i+1，從而減少排序的趟數(shù)。例如，第一趟排序后的序列為1，2，3，9，8，7，最后一次交換的位置為k=4，那么下一趟掃描的下界可設(shè)為5，而不是3。改進(jìn)的算法見(jiàn)本章習(xí)題第四大題的第14小題。

9.3.2快速排序

快速排序是對(duì)起泡排序的一種改進(jìn)，其基本思想是：通過(guò)一趟排序?qū)⒂涗浶蛄蟹殖蓛蓚€(gè)子序列，然后分別對(duì)這兩個(gè)子序列進(jìn)行排序以達(dá)到整個(gè)序列有序。

假設(shè)待排序記錄為R[s]～R[t]，任取其中一個(gè)記錄R[p]作為比較的“基準(zhǔn)”(pivot)，一般取p=s。用此基準(zhǔn)將當(dāng)前序列劃分為左、右兩個(gè)子序列：R[s]～R[i

1]和R[i+1]～R[t]，使得左邊子序列的關(guān)鍵字均小于或等于基準(zhǔn)的關(guān)鍵字，右邊子序列的關(guān)鍵字均大于或等于基準(zhǔn)的關(guān)鍵字，即：

R[s]～R[i

1].key≤R[i].key≤R[i+1]～R[t].key(s≤i≤t)

此時(shí)基準(zhǔn)所處的位置為R[i]，也即該記錄的最終排序位置。這是一趟快速排序的過(guò)程。

可以看出，快速排序中的比較都是與基準(zhǔn)進(jìn)行的，發(fā)生交換時(shí)記錄移動(dòng)的距離較大；而在起泡排序中，比較和交換是在相鄰兩記錄之間進(jìn)行的，每次交換記錄只能前移或后移一個(gè)位置，因此快速排序的效率得到提高。

快速排序是一種縮小規(guī)模算法。當(dāng)R[s]～R[i

1]和R[i+1]～R[t]均非空時(shí)，還應(yīng)分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有記錄均已排好序?yàn)橹埂?/p>

下面給出對(duì)序列R[s]～R[t]進(jìn)行劃分的具體做法：基準(zhǔn)設(shè)置為序列中的第一個(gè)記錄R[s]，并將它保存在pivot中；設(shè)置兩個(gè)指針low和high，它們的初值分別取為low=s和high=t。首先，令high自t起向左掃描，當(dāng)找到第一個(gè)關(guān)鍵字小于pivot.key的記錄R[high]時(shí)，將記錄R[high]移至R[low](即空出數(shù)組單元R[high])；然后，令low=low+1并自左向右掃描，當(dāng)找到第一個(gè)關(guān)鍵字大于pivot.key的記錄R[low]時(shí)，將記錄R[low]移至R[high](即空出數(shù)組單元R[low])；接著令high=high

1并從右向左掃描，如此交替改變掃描方向，從兩端各自往中間靠攏，直至low=high。此時(shí)low便是基準(zhǔn)的最終位置，最后將pivot放在此位置上就完成了一次劃分。

算法9.5中，數(shù)組R的下界s和上界t確定了待排序記錄的范圍。對(duì)整個(gè)序列進(jìn)行排序時(shí)，則調(diào)用QuickSort(R,1,n)。

圖9.4給出了一次劃分的過(guò)程及整個(gè)快速排序的過(guò)程。

圖9.4快速排序示例下面分析快速排序算法的性能。可以證明，對(duì)n個(gè)記錄進(jìn)行快速排序的平均時(shí)間復(fù)雜度為O(n?lb?n)。在時(shí)間復(fù)雜度量級(jí)相同的算法中，快速排序也被公認(rèn)是最好的。假設(shè)對(duì)長(zhǎng)度為n的序列進(jìn)行快速排序所需的比較次數(shù)為C(n)，則

C(n)=Cp(n)+C(m)+C(n-m-1)

其中Cp(n)是進(jìn)行一次劃分所需的比較次數(shù)，m為一個(gè)子序列的長(zhǎng)度。顯然，Cp(n)與序列長(zhǎng)度n有關(guān)，設(shè)Cp(n)=cn，c為常數(shù)，C(m)和C(n-m-1)分別是左、右兩個(gè)子序列進(jìn)行排序所需的比較次數(shù)。根據(jù)算法9.5，遞歸地對(duì)左、右兩個(gè)子序列進(jìn)行排序即可得到總的比較次數(shù)。在最好情況下，快速排序的每次劃分后基準(zhǔn)的左、右兩個(gè)子序列的長(zhǎng)度大致相等，也即所取的基準(zhǔn)正好是待劃分序列的“中值”。這樣總的劃分結(jié)果類(lèi)似于一棵左、右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)基本相等的二叉樹(shù)。假設(shè)序列長(zhǎng)度n=2k，那么總的比較次數(shù)為

C(n)≤Cp(n)+C(n/2)+C(n/2)=cn+2C(n/2)

≤cn+2[cn/2+2C(n/22)]=2cn+4C(n/22)

≤2cn+4[cn/4+2C(n/23)]=3cn+8C(n/23)

≤……

≤ckn+2kC(n/2k)=c(lb?n)O(n)+nC(1)

=O(n?lb?n)

式中C(1)是一常數(shù)。

當(dāng)待排序記錄已按關(guān)鍵字有序或基本有序時(shí)，快速排序的效率反而降低。在最壞情況下，每次劃分后基準(zhǔn)左、右兩個(gè)子序列中有一個(gè)長(zhǎng)度為0，這樣總的劃分結(jié)果類(lèi)似于一棵單支的二叉樹(shù)。以有序序列為例，在第一趟快速排序中，經(jīng)過(guò)n

1次比較之后，第一個(gè)記錄仍定位在它原來(lái)的位置上，并得到一個(gè)包括n

1個(gè)記錄的子序列；第二次遞歸調(diào)用中，需經(jīng)過(guò)n

2次比較，第二個(gè)記錄仍定位在它原來(lái)的位置上，得到的子序列長(zhǎng)度n

2；依次類(lèi)推，最后得到總比較次數(shù)為

這種情況下，快速排序的時(shí)間復(fù)雜度為O(n2)，蛻化為起泡排序。要改善此時(shí)的性能,通常采用“三者取中”的方法。也就是在進(jìn)行一趟快速排序之前,對(duì)R[s].key、R[t].key和R[

(s+t)/2

].key進(jìn)行比較，將三者中的“中值”記錄與R[s]交換。實(shí)驗(yàn)證明，這種方法可以大大改善快速排序在最壞情況下的性能。

綜上所述，快速排序的最壞時(shí)間復(fù)雜度為O(n2)，最好時(shí)間復(fù)雜度為O(n?lb?n)。注意到，快速排序的記錄移動(dòng)次數(shù)不大于比較的次數(shù)。可以證明：平均情況下快速排序的時(shí)間復(fù)雜度也是O(n?lb?n)。從時(shí)間上看，它是目前基于比較的內(nèi)部排序方法中平均性能最好的，因而稱(chēng)為快速排序。

從空間上看，快速排序算法雖然只需要一個(gè)臨時(shí)單元存放基準(zhǔn)記錄，但是其遞歸特性需要一個(gè)棧空間來(lái)實(shí)現(xiàn)。?？臻g的大小取決于每次劃分后序列的長(zhǎng)度。最好情況下，棧的最大深度為

lb?n

+1，所需?？臻g為O(lb?n)；最壞情況下，棧的最大深度為n，所需?？臻g為O(n)。

快速排序是不穩(wěn)定的。

選擇排序(SelectSort)的基本思想是：每一趟從待排序記錄中選出關(guān)鍵字最小的記錄，依次放在已排序記錄的最后，直至全部記錄有序。直接選擇排序是其中最為簡(jiǎn)單的一種方法。

9.4直接選擇排序直接選擇排序的具體做法是：第一趟排序?qū)⒋判蛴涗汻[1]～R[n]作為無(wú)序區(qū)，從中選出關(guān)鍵字最小的記錄并與無(wú)序區(qū)中第1個(gè)記錄R[1]交換，此時(shí)得到有序區(qū)為R[1]，無(wú)序區(qū)縮小為R[2]～R[n]；第二趟排序則在無(wú)序區(qū)R[2]～R[n]中選關(guān)鍵字最小的記錄，將它與R[2]交換；第i趟排序時(shí)，在當(dāng)前的無(wú)序區(qū)R[i]～R[n]中選出關(guān)鍵字最小的記錄R[k]，并與無(wú)序區(qū)中第1個(gè)記錄R[i]交換，得到新的有序區(qū)R[1]～R[i]。注意到，每趟排序從無(wú)序區(qū)中選擇的記錄其關(guān)鍵字是有序區(qū)中的最大值。根據(jù)上述過(guò)程類(lèi)推，進(jìn)行n

1趟排序后，無(wú)序區(qū)中只剩一個(gè)記錄，此時(shí)整個(gè)序列就是遞增有序的。其排序過(guò)程如圖9.5所示，相應(yīng)過(guò)程的c語(yǔ)言描述詳見(jiàn)算法9.6。

圖9.5直接選擇排序示例分析算法9.6可知，直接選擇排序需n

1趟排序，每一趟的比較次數(shù)與關(guān)鍵字的排列狀態(tài)無(wú)關(guān)。第一趟找出最小關(guān)鍵字需要進(jìn)行n

1次比較，第二趟找出次小關(guān)鍵字需要進(jìn)行n

2次比較，由此類(lèi)推，總的比較次數(shù)為

每趟比較后要判斷是否進(jìn)行兩個(gè)記錄的交換，如要交換，則進(jìn)行三次記錄的移動(dòng)。因此直接選擇排序在最好情況下，記錄移動(dòng)次數(shù)的最小值為0，而在最壞情況下的最大值為3(n

1)。

綜上所述，直接選擇排序的時(shí)間復(fù)雜度為O(n2)。這種排序方法是不穩(wěn)定的。

歸并排序(MergeSort)的思路與前面介紹過(guò)的排序方法都不一樣?！皻w并”的含義是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序的基本思路是：假設(shè)初始表含有n個(gè)記錄，則可看成是n個(gè)有序的子表，每個(gè)子表的長(zhǎng)度為1，然后兩兩歸并，得到

n/2

個(gè)長(zhǎng)度為2或1的有序子表；再兩兩歸并，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序子表為止。這種方法稱(chēng)為“二路歸并排序”。

9.5歸并排序

1．二路歸并

假設(shè)R[low]～R[mid]和R[mid+1]～R[high]表示同一數(shù)組中相鄰的兩個(gè)有序表，現(xiàn)在要將它們合并為一個(gè)有序表R1[low]～R1[high]，需要設(shè)置三個(gè)指示器i、j和k，其初值分別為這三個(gè)記錄區(qū)的起始位置。具體實(shí)現(xiàn)如算法9.7所示。

在算法9.7中，從兩個(gè)有序表R[low]～R[mid]和R[mid+1]～R[high]的左端開(kāi)始，依次比較R[i]和R[j]的關(guān)鍵字，并將關(guān)鍵字較小的記錄復(fù)制到R1[k]中；然后，指向被復(fù)制記錄的指示器和指向復(fù)制位置的指示器k右移，重復(fù)這一過(guò)程，直至其中一個(gè)有序表中的全部記錄復(fù)制完畢；最后將另一個(gè)有序表的剩余記錄直接復(fù)制到數(shù)組R1[low]～R1[high]中。

2．一趟歸并

假設(shè)在待排序序列中，每個(gè)有序表的長(zhǎng)度均為length(最后一個(gè)有序表的長(zhǎng)度可能小于length)，那么在歸并前R[1]～R[n]中共有

n/length

個(gè)有序的子文件：R[1]～R[length]，R[length+1]～R[2

length]，…，R[(

n/length

1)

length+1]～R[n]。一趟歸并所解決的問(wèn)題是，調(diào)用二路歸并算法將相鄰的一對(duì)有序表進(jìn)行歸并。具體算法見(jiàn)算法9.8。

在算法9.8中要考慮三種情況：有序表的個(gè)數(shù)為偶數(shù)且長(zhǎng)度均為length，有序表的個(gè)數(shù)為偶數(shù)但最后一個(gè)有序表的長(zhǎng)度小于length，有序表的個(gè)數(shù)為奇數(shù)。

3．二路歸并排序

二路歸并排序如算法9.9所示，實(shí)際上就是對(duì)“一趟歸并”的重復(fù)調(diào)用過(guò)程。有序表的初始長(zhǎng)度為1，每趟歸并后有序表長(zhǎng)度增大一倍；若干趟歸并后，當(dāng)有序表的長(zhǎng)度大于或等于n時(shí)，排序結(jié)束。

要注意的是，算法9.9中每次循環(huán)調(diào)用函數(shù)MergePass兩次。若第一次調(diào)用后，條件length<n成立，則第二次調(diào)用MergePass仍實(shí)現(xiàn)排序功能，否則排序已完成，此時(shí)第二次調(diào)用MergePass的作用僅僅是把排序結(jié)果從R1復(fù)制到R中。

圖9.6所示為歸并排序的示例。對(duì)于一組待排序的記錄，其關(guān)鍵字分別為49,31,63,85,75,15,26,49

。根據(jù)算法9.9，首先將這8個(gè)記錄看做是長(zhǎng)度為1的8個(gè)有序表，然后兩兩歸并，直至有序表的長(zhǎng)度不小于8。圖9.6二路歸關(guān)排序示例分析算法9.9以及圖9.6可知，第i趟歸并后，有序表長(zhǎng)度為2i。因此，對(duì)于長(zhǎng)度為n的無(wú)序表，必須執(zhí)行

lb?n

趟歸并。由于每趟歸并的時(shí)間復(fù)雜度是O(n)，二路歸并排序算法的時(shí)間復(fù)雜度為O(n?lb?n)，算法中輔助空間即數(shù)組R1的最大長(zhǎng)度為n，因此空間復(fù)雜度是O(n)。

與快速排序算法相比，二路歸并排序的最大特點(diǎn)是它是穩(wěn)定的。

實(shí)際應(yīng)用中并不提倡從長(zhǎng)度為1的序列開(kāi)始進(jìn)行二路歸并。可以先利用直接插入排序得到較長(zhǎng)的有序表，然后再進(jìn)行兩兩歸并。二者的混合排序仍然是穩(wěn)定的。

內(nèi)部排序方法還有堆排序、分配排序、基數(shù)排序等多種，本章不做一一介紹。各種排序方法中沒(méi)有哪一種是絕對(duì)最優(yōu)的，不同排序方法各有其優(yōu)缺點(diǎn)，因此，在不同的場(chǎng)合根據(jù)需要選擇適當(dāng)?shù)呐判蚍椒ㄊ鞘种匾?。綜合比較本章所討論的各種排序方法，大致有如表9.1所示的結(jié)果，其中簡(jiǎn)單排序包括除希爾排序之外的所有插入排序、起泡排序和簡(jiǎn)單選擇排序。

9.6各種內(nèi)部排序方法的比較和選擇具體選擇排序方法時(shí)，應(yīng)考慮以下因素：

(1)平均時(shí)間：平均時(shí)間主要取決于算法的時(shí)間復(fù)雜度以及關(guān)鍵字的分布情況。一般應(yīng)采用時(shí)間復(fù)雜度為O(n?lb?n)的排序方法，例如快速排序、歸并排序。當(dāng)待排序的關(guān)鍵字隨機(jī)分布時(shí)，快速排序所需運(yùn)行時(shí)間最短，但是在最壞情況下性能較差。歸并排序沒(méi)有所謂的最壞情況，當(dāng)n較大時(shí)可作為另一種較好的選擇。

(2)記錄數(shù)目n：若n比較小(如n≤50)，則可采用簡(jiǎn)單的排序方法，而直接插入排序最為簡(jiǎn)單。當(dāng)序列中的記錄基本有序時(shí)，直接插入排序或起泡排序是較好的選擇。當(dāng)n較大時(shí)，可根據(jù)平均時(shí)間來(lái)考慮。

(3)記錄大小：排序算法中的主要操作是關(guān)鍵字的比較和記錄的移動(dòng)。當(dāng)記錄本身數(shù)據(jù)量較大時(shí)，應(yīng)采用記錄移動(dòng)次數(shù)較少的排序方法，例如直接插入排序所需的記錄移動(dòng)次數(shù)要多于直接選擇排序。

(4)穩(wěn)定性：這一點(diǎn)取決于不同的應(yīng)用場(chǎng)合。當(dāng)穩(wěn)定性比較重要時(shí)，較快的算法可以選擇歸并排序或基數(shù)排序，簡(jiǎn)單排序中可以選擇直接插入排序、起泡排序等。必須注意的是，穩(wěn)定的排序方法與其具體的描述形式有關(guān)，改變描述形式后，原本穩(wěn)定的排序方法也會(huì)變得不穩(wěn)定。

本章所討論的內(nèi)部排序算法都是在一維數(shù)組上實(shí)現(xiàn)的。當(dāng)記錄本身的信息量較大時(shí)，采用鏈表結(jié)構(gòu)可以節(jié)約因大量移動(dòng)記錄所耗費(fèi)的時(shí)間。當(dāng)記錄很大時(shí)，可以采用靜態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)，以指針的修改替代記錄的移動(dòng)。另外，對(duì)于任何鏈表結(jié)構(gòu)，我們還可以提取結(jié)點(diǎn)的地址信息存儲(chǔ)為地址向量，然后按照一位數(shù)組的方式對(duì)該地址向量進(jìn)行排序。

一、名詞解釋

排序，穩(wěn)定的排序，不穩(wěn)定的排序，內(nèi)部排序，外部排序

二、填空題

1．按照排序過(guò)程涉及的存儲(chǔ)設(shè)備的不同，排序可分為

排序和

排序。

2．在排序算法中，分析算法的時(shí)間復(fù)雜性時(shí)，通常以

和

為標(biāo)準(zhǔn)操作。評(píng)價(jià)排序的另一個(gè)主要標(biāo)準(zhǔn)是執(zhí)行算法所需要的

。

3．直接插入排序是穩(wěn)定的，它的時(shí)間復(fù)雜性為

，空間復(fù)雜度為

。

習(xí)題9

4．對(duì)于n個(gè)記錄的集合進(jìn)行起泡排序，其最壞情況下所需的時(shí)間復(fù)雜度為

。

5．對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需的附加空間消耗是

。

6．以下為起泡排序的算法。請(qǐng)分析算法，并在

上填充適當(dāng)?shù)恼Z(yǔ)句。

7．對(duì)快速排序來(lái)講，其最好情況下的時(shí)間復(fù)雜度是

，其最壞情況下的時(shí)間復(fù)雜度是

。

8．歸并排序要求待排序列由若干個(gè)

的子序列組成。

三、選擇題

1．以下不穩(wěn)定的排序方法是()。

A.直接插入排序

B.起泡排序

D.直接選擇排序

D.二路歸并排序

2．以下時(shí)間復(fù)雜性不是O(n2)的排序方法是()。

A.直接插入排序

B.二路歸并排序

C.起泡排序

D.直接選擇排序

3．排序的目的是為了以后對(duì)已排序的數(shù)據(jù)元數(shù)進(jìn)行()操作。

A.打印輸出 B.分類(lèi)