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

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

待排序的記錄可有下列三種存儲結構：

(1)以一組連續的地址單元(如一維數組)作為存儲結構，待排序記錄的次序由其物理位置決定。在排序過程中，必須移動記錄來進行物理位置上的重排，即通過比較和判定把記錄移到合適的位置。

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

(3)待排序記錄存儲在一組連續的地址單元內，此時若要避免排序過程中記錄的移動，可以為該序列建立一個輔助表(如索引表)，在排序過程中只需對這個輔助的表目進行物理重排，而不移動記錄本身。

為方便起見，本章假設記錄序列的存儲結構為一維數組，關鍵字為整數。待排序記錄的數據類型說明如下：

typedefstruct //定義記錄為結構類型

{intkey; //關鍵字域

datatypeother; //其他數據域

}rectype;

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

9.2.1直接插入排序

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

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

1,i

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

根據算法9.1對待排序的一組記錄進行排序，記錄的關鍵字分別為49,31,63,85,75,15,26,49

，直接插入排序過程如圖9.1所示。

直接插入排序的算法9.1非常簡潔，容易實現，下面來分析它的效率。

從時間上看，整個排序過程只有兩種運算，即比較關鍵字和移動記錄。算法中的外循環表示要進行n

1趟插入排序，內循環的次數則取決于待排序關鍵字與有序區中i個關鍵字的關系。

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

1，總的移動次數Mmin=2(n

1)；當文件逆序時，要插入的第i個記錄均要與前i

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

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

直接插入排序是穩定的排序方法。

9.2.2希爾排序

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

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

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

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

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

要注意的是，希爾排序中的子序列不是逐段選取的，而是根據增量值跳躍性的抽取。這樣可以實現排序記錄在較大范圍內進行移動，從而提高了排序速度。但是由此導致了希爾排序是不穩定的。

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

算法9.2中沒有設置“監視哨”，單元R[0]僅作為暫存單元，在內循環中增加了一個循環判定條件“j>0”，以防下標越界。若要設置監視哨，需要利用數組R的前t個單元作為監視哨，待排序記錄則要從第t個單元開始存儲。讀者可以自行完成。

希爾排序的時間復雜度取決于增量序列的選取，但是如何選取增量序列才能產生最好的排序效果，這一問題至今沒有得到解決。希爾本人最初提出取d1=

n/2

，di+1=

di/2

，dt=1，t=

lb?n

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

(di

1)/3

，dt=1，t=

log3n

1

以及di+1=

(di

1)/2

，dt=1，t=

lb?n

1

。大量實驗表明，希爾排序所需的比較和移動次數約為n1.3。

9.3.1起泡排序

起泡排序(BubbleSort)是最為人們所熟知的交換排序方法。它的過程非常簡單：對縱向排列的關鍵字序列，按照自下而上的掃描方向對兩兩相鄰的關鍵字進行比較，若為逆序(即kj

1>kj)，則將兩個記錄交換位置；重復上述掃描排序過程，直至沒有記錄需要交換為止。

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

1個記錄重復同樣操作，把次小關鍵字的記錄安排在第二個記錄的位置上；重復上述過程，分析可知，在第n

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

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

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

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

1，記錄移動次數為0。若記錄逆序排列，即按關鍵字遞減排列，則一共需進行n

1趟掃描，比較次數和記錄移動次數均達到最大值，分別為：

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

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

(1)在算法9.3中，一次掃描可以把最輕的氣泡上升至頂，而最重的氣泡僅能“下沉”一個位置。由此分析可知，對于關鍵字序列2,3,7,8,9,1，僅需一趟掃描就可以完成排序；但是對于關鍵字序列9,1,2,3,7,8，卻需要從下到上掃描五趟才能完成排序。這兩個序列都是僅有一個元素需要重排，但是產生了完全不同的結果。究其原因，正是掃描的方向導致了兩種情況下的不對稱性。如果改變掃描方向為從上到下，則序列9,1,2,3,7,8也僅需一趟掃描。基于上述分析，我們可在排序過程中交替改變掃描方向，形成雙向起泡算法。該算法的實現留做習題。

(2)在每趟掃描中，記住最后一次交換發生的位置k，因為該位置之前的記錄都已有序，即R[1..k

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

9.3.2快速排序

快速排序是對起泡排序的一種改進，其基本思想是：通過一趟排序將記錄序列分成兩個子序列，然后分別對這兩個子序列進行排序以達到整個序列有序。

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

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

R[s]～R[i

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

此時基準所處的位置為R[i]，也即該記錄的最終排序位置。這是一趟快速排序的過程。

可以看出，快速排序中的比較都是與基準進行的，發生交換時記錄移動的距離較大；而在起泡排序中，比較和交換是在相鄰兩記錄之間進行的，每次交換記錄只能前移或后移一個位置，因此快速排序的效率得到提高。

快速排序是一種縮小規模算法。當R[s]～R[i

1]和R[i+1]～R[t]均非空時，還應分別對它們進行上述的劃分過程，直至所有記錄均已排好序為止。

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

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

算法9.5中，數組R的下界s和上界t確定了待排序記錄的范圍。對整個序列進行排序時，則調用QuickSort(R,1,n)。

圖9.4給出了一次劃分的過程及整個快速排序的過程。

圖9.4快速排序示例下面分析快速排序算法的性能?？梢宰C明，對n個記錄進行快速排序的平均時間復雜度為O(n?lb?n)。在時間復雜度量級相同的算法中，快速排序也被公認是最好的。假設對長度為n的序列進行快速排序所需的比較次數為C(n)，則

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

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

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)是一常數。

當待排序記錄已按關鍵字有序或基本有序時，快速排序的效率反而降低。在最壞情況下，每次劃分后基準左、右兩個子序列中有一個長度為0，這樣總的劃分結果類似于一棵單支的二叉樹。以有序序列為例，在第一趟快速排序中，經過n

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

1個記錄的子序列；第二次遞歸調用中，需經過n

2次比較，第二個記錄仍定位在它原來的位置上，得到的子序列長度n

2；依次類推，最后得到總比較次數為

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

(s+t)/2

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

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

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

lb?n

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

快速排序是不穩定的。

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

9.4直接選擇排序直接選擇排序的具體做法是：第一趟排序將待排序記錄R[1]～R[n]作為無序區，從中選出關鍵字最小的記錄并與無序區中第1個記錄R[1]交換，此時得到有序區為R[1]，無序區縮小為R[2]～R[n]；第二趟排序則在無序區R[2]～R[n]中選關鍵字最小的記錄，將它與R[2]交換；第i趟排序時，在當前的無序區R[i]～R[n]中選出關鍵字最小的記錄R[k]，并與無序區中第1個記錄R[i]交換，得到新的有序區R[1]～R[i]。注意到，每趟排序從無序區中選擇的記錄其關鍵字是有序區中的最大值。根據上述過程類推，進行n

1趟排序后，無序區中只剩一個記錄，此時整個序列就是遞增有序的。其排序過程如圖9.5所示，相應過程的c語言描述詳見算法9.6。

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

1趟排序，每一趟的比較次數與關鍵字的排列狀態無關。第一趟找出最小關鍵字需要進行n

1次比較，第二趟找出次小關鍵字需要進行n

2次比較，由此類推，總的比較次數為

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

1)。

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

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

n/2

個長度為2或1的有序子表；再兩兩歸并，如此重復，直至得到一個長度為n的有序子表為止。這種方法稱為“二路歸并排序”。

9.5歸并排序

1．二路歸并

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

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

2．一趟歸并

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

n/length

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

length]，…，R[(

n/length

1)

length+1]～R[n]。一趟歸并所解決的問題是，調用二路歸并算法將相鄰的一對有序表進行歸并。具體算法見算法9.8。

在算法9.8中要考慮三種情況：有序表的個數為偶數且長度均為length，有序表的個數為偶數但最后一個有序表的長度小于length，有序表的個數為奇數。

3．二路歸并排序

二路歸并排序如算法9.9所示，實際上就是對“一趟歸并”的重復調用過程。有序表的初始長度為1，每趟歸并后有序表長度增大一倍；若干趟歸并后，當有序表的長度大于或等于n時，排序結束。

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

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

。根據算法9.9，首先將這8個記錄看做是長度為1的8個有序表，然后兩兩歸并，直至有序表的長度不小于8。圖9.6二路歸關排序示例分析算法9.9以及圖9.6可知，第i趟歸并后，有序表長度為2i。因此，對于長度為n的無序表，必須執行

lb?n

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

與快速排序算法相比，二路歸并排序的最大特點是它是穩定的。

實際應用中并不提倡從長度為1的序列開始進行二路歸并?？梢韵壤弥苯硬迦肱判虻玫捷^長的有序表，然后再進行兩兩歸并。二者的混合排序仍然是穩定的。

內部排序方法還有堆排序、分配排序、基數排序等多種，本章不做一一介紹。各種排序方法中沒有哪一種是絕對最優的，不同排序方法各有其優缺點，因此，在不同的場合根據需要選擇適當的排序方法是十分重要的。綜合比較本章所討論的各種排序方法，大致有如表9.1所示的結果，其中簡單排序包括除希爾排序之外的所有插入排序、起泡排序和簡單選擇排序。

9.6各種內部排序方法的比較和選擇具體選擇排序方法時，應考慮以下因素：

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

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

(3)記錄大?。号判蛩惴ㄖ械闹饕僮魇顷P鍵字的比較和記錄的移動。當記錄本身數據量較大時，應采用記錄移動次數較少的排序方法，例如直接插入排序所需的記錄移動次數要多于直接選擇排序。

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

本章所討論的內部排序算法都是在一維數組上實現的。當記錄本身的信息量較大時，采用鏈表結構可以節約因大量移動記錄所耗費的時間。當記錄很大時，可以采用靜態鏈表作為存儲結構，以指針的修改替代記錄的移動。另外，對于任何鏈表結構，我們還可以提取結點的地址信息存儲為地址向量，然后按照一位數組的方式對該地址向量進行排序。

一、名詞解釋

排序，穩定的排序，不穩定的排序，內部排序，外部排序

二、填空題

1．按照排序過程涉及的存儲設備的不同，排序可分為

排序和

排序。

2．在排序算法中，分析算法的時間復雜性時，通常以

和

為標準操作。評價排序的另一個主要標準是執行算法所需要的

。

3．直接插入排序是穩定的，它的時間復雜性為

，空間復雜度為

。

習題9

4．對于n個記錄的集合進行起泡排序，其最壞情況下所需的時間復雜度為

。

5．對于n個記錄的集合進行歸并排序，所需的附加空間消耗是

。

6．以下為起泡排序的算法。請分析算法，并在

上填充適當的語句。

7．對快速排序來講，其最好情況下的時間復雜度是

，其最壞情況下的時間復雜度是

。

8．歸并排序要求待排序列由若干個

的子序列組成。

三、選擇題

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

A.直接插入排序

B.起泡排序

D.直接選擇排序

D.二路歸并排序

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

A.直接插入排序

B.二路歸并排序

C.起泡排序

D.直接選擇排序

3．排序的目的是為了以后對已排序的數據元數進行()操作。

A.打印輸出 B.分類