9.1排序的基本概念

9.2插入排序

9.3交換排序

9.4選擇排序

9.5歸并排序

9.6基數(shù)排序

9.7各種內部排序算法的比較和選擇9.1排序的基本概念排序可以定義如下：假設序列包含n個記錄{R1,R2,…,Rn}，其對應的關鍵字值序列為{k1,k2,…,kn}，根據(jù)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之前，就稱此排序是穩(wěn)定的；反之，如果排序后變成Ri排在Rj之后，就稱此排序是不穩(wěn)定的。根據(jù)排序過程涉及存儲器的不同，可將排序分為內部排序和外部排序。內部排序是指整個排序過程都在內存中進行的排序；外部排序是指待排序記錄的數(shù)量很大，在排序過程中，除使用內存外，還需對外存進行訪問。顯然，內部排序適用于記錄個數(shù)較少的序列；外部排序則適用于記錄個數(shù)太多，需同時使用內存和外存的長序列。根據(jù)不同算法所用的策略，內部排序可分為插入排序、選擇排序、交換排序、歸并排序及基數(shù)排序等幾大類。每一種算法各有優(yōu)缺點，適合于不同的應用場合，因此要想簡單地評價哪種算法最好且能夠普遍適用是很困難的。判斷排序算法好壞的標準主要有兩條：①算法執(zhí)行所需要的時間；②算法執(zhí)行所需要的附加空間。另外要考慮的一個因素是算法本身的復雜程度。排序算法所需的附加空間量一般都不大，所以時間復雜度是衡量算法好壞最重要的標志。排序所需的時間主要是指算法執(zhí)行中關鍵字的比較次數(shù)和記錄的移動次數(shù)，后面的章節(jié)將會對此進行詳細討論。待排序的記錄有下列三種存儲結構：(1)以一組連續(xù)的地址單元(如一維數(shù)組)作為存儲結構，待排序記錄的次序由其物理位置決定。排序過程必須移動記錄，進行物理位置上的重排，即通過比較和判定，把記錄移到合適的位置。(2)以鏈表作為存儲結構，記錄之間的次序由指針決定。因此，排序過程僅需修改指針。(3)待排序記錄存儲在一組連續(xù)的地址單元內，此時若要避免排序過程中記錄的移動，可以為該序列建立一個輔助表(如索引表)，在排序過程中只需對這個輔助的表目進行物理重排，而不移動記錄本身。待排序記錄的數(shù)據(jù)類型說明如下：9.2插入排序9.2.1直接插入排序直接插入排序(StraightInsertionSort)是一種最簡單的排序方法，其基本思路是把關鍵字ki依次與有序區(qū)的關鍵字ki-1,ki-2,…,k1進行比較，找到應該插入的位置，然后將ki插入。給定待排序的記錄序列為R[1]～R[n]，則初始有序區(qū)為{R[1]}，直接插入排序可以從i?=?2開始，如算法9.1所示。算法9.1中的基本操作是關鍵字比較和記錄移動。記錄R[1]作為最初的有序區(qū)，從i?=?2開始不斷將待插入記錄R[i]的關鍵字依次與有序區(qū)中記錄R[j](j=i-1,i-2,…,1)的關鍵字進行比較。若R[j]的關鍵字大于R[i]的關鍵字，則將R[j]后移一個位置；若R[j]的關鍵字小于或等于R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。數(shù)組單元R[0]預先對記錄R[i]進行備份，使得在后移關鍵字比R[i]大的記錄時不致丟失R[i]中的內容。R[0]在while循環(huán)中還可以作為“監(jiān)視哨”，防止下標變量j越界。由于避免了每次while循環(huán)都要檢測j是否越界，測試循環(huán)條件的時間可以減少約一半。算法9.1直接插入排序。根據(jù)算法9.1對待排序的一組記錄進行排序，記錄的關鍵字分別為49、31、63、85、75、15、26、49，直接插入排序過程如圖9.1所示。直接插入排序的算法9.1非常簡潔，容易實現(xiàn)，下面來分析它的效率。從時間上看，整個排序過程只有比較關鍵字和移動記錄兩種運算。算法中的外循環(huán)表示要進行n-1趟插入排序，內循環(huán)的次數(shù)則取決于待排序關鍵字與有序區(qū)中i個關鍵字的關系?？梢园磧煞N情況來考慮。當一組記錄為正序時(這里按遞增有序)，每趟排序的關鍵字比較次數(shù)為1，記錄移動次數(shù)是2次，即總的比較次數(shù)Cmin?=?n-1，總的移動次數(shù)Mmin=2(n-1)；當文件逆序時，要插入的第i個記錄均要與前i-1個記錄及“監(jiān)視哨”的關鍵字進行比較，即每趟要進行i次比較；從記錄移動的次數(shù)來說，每趟排序中除了上面提到的兩次移動外，還需將關鍵字大于R[i]的記錄后移一個位置。這時關鍵字的比較次數(shù)和記錄的移動次數(shù)均取最大值，總的比較次數(shù)和記錄的移動次數(shù)分別為綜上可知，記錄關鍵字的分布對算法執(zhí)行過程中的時間消耗是有影響的。若在隨機情況下，即關鍵字各種排列出現(xiàn)的概率相同，則可取上述兩種情況的平均值作為比較和記錄移動的平均次數(shù)，約為n2/4。由此，直接插入排序的時間復雜度為O(n2)。從空間上看，直接插入排序只需要一個記錄的輔助空間R[0]，空間復雜度為O(1)。直接插入排序是穩(wěn)定的排序方法。9.2.2希爾排序希爾排序(Shell’sSort)又稱為縮小增量排序(DiminishingIncrementSort)，是一種改進的插入排序方法。該方法是D.L.Shell于1959年提出的，故用他的名字命名。我們知道直接插入排序算法的平均時間復雜度為O(n2)，但是由于其算法簡單，因此當n較小時效率較高。另外，當一組記錄有序時其算法復雜度可以達到最優(yōu)，即O(n)。希爾排序正是基于這兩點對直接插入排序進行改進的。希爾排序的基本思想是：設置t個整數(shù)增量(d1?>?d2?>?…?>?dt-1?>?dt)，其中d1?<?n，dt=1；首先以d1為增量，將所有距離為d1倍數(shù)的記錄放在同一組中，可以得到d1個組，在各組內進行直接插入排序；然后取第二個增量d2，重復上述的分組和排序，直至增量dt=1。設置增量序列時，要使得增量值沒有除1之外的公因子，而且最后一個增量值必須為1。下面先看一個具體例子。設待排序文件共有10個記錄，其關鍵字分別為49、31、63、85、75、15、26、49、53、03，增量序列取值依次為5、3、1，排序過程如圖9.2所示。由圖9.2可見，希爾排序的每一趟就是直接插入排序。增量越大，則得到的子序列越短，此時直接插入排序效率很高；而當增量逐漸減小時，序列已逐漸有序，因此直接插入排序仍然很有效。當增量為1時，所有的記錄已經(jīng)基本有序，并放在同一組中進行直接插入排序。由此，希爾排序的速度較直接插入排序有較大的提高。希爾排序的具體算法如算法9.2所示。算法9.2中沒有設置“監(jiān)視哨”，單元R[0]僅作為暫存單元，所以在內循環(huán)(while循環(huán))中增加了一個循環(huán)判定條件“j>0”，以防下標越界。當搜索位置j≤0或者R[0].key≥R[j].key時，表示插入位置已找到。為了便于對希爾排序算法的理解，我們用偽代碼來描述算法。9.3交換排序9.3.1起泡排序起泡排序(BubbleSort)是最為人們所熟知的交換排序方法。它的過程非常簡單，將關鍵字序列看作是從上到下縱向排列的，按照自下而上的掃描方向對兩兩相鄰的關鍵字進行比較，若為逆序(即kj1>kj)，則將兩個記錄交換位置；重復上述掃描排序過程，直至沒有記錄需要交換為止。第一趟掃描后，關鍵字最小的記錄將上升到第一個記錄的位置上；第二趟對后面的n-1個記錄進行同樣操作，把次小關鍵字的記錄安排在第二個記錄的位置上；重復上述過程，分析可知在第n-1趟后，全部記錄都按關鍵字由小到大的順序排列完畢。在每一趟排序過程中，關鍵字最小的記錄通過比較和交換，會像氣泡一樣上浮至頂；而關鍵字較大的記錄則逐漸下沉，“起泡排序”的名稱由此而得。起泡排序的過程如圖9.3所示。對任一組記錄進行起泡排序時，至多需要進行n-1趟排序。但是，如果在排序過程中的某一趟掃描后，例如圖9.3中的第四趟排序后，待排序記錄已按關鍵字有序排列，則起泡排序便在此趟排序后終止。為了實現(xiàn)這一點，我們可以在起泡排序算法(算法9.3)中引入一個布爾量swap，在每趟排序開始前，先將其置為0，若排序過程中發(fā)生了交換，則將其置為1。在一趟排序之后，如果swap仍為0，則表示本趟未曾交換過記錄，此時可以終止算法。算法9.3起泡排序。下面分析起泡排序的性能。若記錄已按關鍵字有序排列，則只需進行一趟掃描，而且比較次數(shù)和記錄移動次數(shù)均為最小值：比較次數(shù)為n-1，記錄移動次數(shù)為0；若記錄逆序排列，即按關鍵字遞減排列，則一共需進行n-1趟掃描，比較次數(shù)和記錄移動次數(shù)均達到最大值，分別為由此可知，起泡排序的時間復雜度為O(n2)。為提高起泡排序算法的效率，必須減少算法9.3中的比較和交換次數(shù)。除了設置交換標志外，我們還可做如下兩種改進：(1)在算法9.3中，一次掃描可以把最輕的氣泡上升至頂，而最重的氣泡僅能“下沉”一個位置。由此分析可知，對于關鍵字序列{2,3,7,8,9,1}，僅需一趟掃描就可以完成排序；但是對于關鍵字序列{9,1,2,3,7,8}，卻需要從下向上掃描五趟才能完成排序。這兩個序列都是僅有一個元素需要重排，但是產(chǎn)生了完全不同的結果。究其原因，正是掃描的方向導致了兩種情況下的不對稱性。如果改變掃描方向為從上向下，則序列{9,1,2,3,7,8}也僅需一趟掃描?；谏鲜龇治觯覀兛稍谂判蜻^程中交替改變掃描方向，形成雙向起泡算法。(2)在每趟掃描中，記住最后一次交換發(fā)生的位置k，因為該位置之前的記錄都已有序，即R[1,…,k-1]是有序區(qū)，R[k,…,n]是無序區(qū)，那么下一趟沿該方向掃描時可提前終止于位置k+1，而不必進行到預定的下界i+1，從而減少排序的趟數(shù)。9.3.2快速排序快速排序(QuickSort)是對起泡排序的一種改進，其基本思想是：通過一趟排序將記錄序列分成兩個子序列，然后分別對這兩個子序列進行排序，以達到整個序列有序。假設待排序記錄為R[s]～R[t]，任取其中一個記錄R[p]作為比較的“基準”(pivot)，一般取p=s(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]，也即該記錄的最終排序位置。這是一趟快速排序的過程?？梢钥闯觯焖倥判蛑械谋容^都是與基準進行的，發(fā)生交換時記錄移動的距離較大；而在起泡排序中，比較和交換是在相鄰兩記錄之間進行的，每次交換記錄只能前移或后移一個位置，因此快速排序的效率得到提高?？焖倥判蚴且环N縮小規(guī)模算法。當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](即空出數(shù)組單元R[high])；然后令low=low+1并從左向右掃描，當找到第一個關鍵字大于pivot.key的記錄R[low]時，將記錄R[low]移至R[high](即空出數(shù)組單元R[low])；接著令high=high-1并從右向左掃描，如此交替改變掃描方向，從兩端各自往中間靠攏，直至low=high，此時low便是基準的最終位置；最后將pivot放在此位置上就完成了一次劃分。算法9.4和算法9.5分別給出了一次劃分算法及快速排序遞歸算法。算法9.4一次劃分算法。算法9.5快速排序遞歸算法。算法9.5中數(shù)組R的下界s和上界t確定待排序記錄的范圍。對整個序列進行排序時，則調用QuickSort(R,1,n)。圖9.4給出了一次劃分的過程及整個快速排序的過程。下面分析快速排序算法的性能?？梢宰C明，對n個記錄進行快速排序的平均時間復雜度為O(n?lb?n)。在時間復雜度量級相同的算法中，快速排序也被公認是最好的。假設對長度為n的序列進行快速排序所需的比較次數(shù)為C(n)，則C(n)?=?Cp(n)?+?C(m)?+?C(n-m-1)其中，Cp(n)是進行一次劃分所需的比較次數(shù)；m為一個子序列的長度。顯然，Cp(n)與序列長度n有關。設Cp(n)?=?cn，c為常數(shù)，C(m)和C(n-m-1)分別是左、右兩個子序列進行排序所需的比較次數(shù)，根據(jù)算法9.5，遞歸地對左、右兩個子序列進行排序即可得到總的比較次數(shù)。在最好情況下，快速排序每次劃分后基準左、右兩個子序列的長度大致相等，也即所取的基準正好是待劃分序列的“中值”。這樣總的劃分結果類似于一棵左右子樹結點個數(shù)基本相等的二叉樹。假設序列長度n?=?2k，那么總的比較次數(shù)為當待排序記錄已按關鍵字有序或基本有序時，快速排序的效率反而降低。在最壞情況下，每次劃分后基準左、右兩個子序列中有一個長度為0，這樣總的劃分結果則類似于一棵單支的二叉樹。以有序序列為例，在第一趟快速排序中，經(jīng)過n-1次比較之后，第一個記錄仍定位在它原來的位置上，并得到一個包括n-1個記錄的子序列；第二次遞歸調用中需經(jīng)過n-2次比較，第二個記錄仍定位在它原來的位置上，得到的子序列長度為n-2；依次類推，最后，得到總比較次數(shù)為這種情況下，快速排序的時間復雜度為O(n2)，蛻化為起泡排序。要改善此時的性能，通常采用“三者取中”的方法。也就是在進行一趟快速排序之前，對R[s].key、R[t].key和R[(s+t)/2].key進行比較，將三者中的“中值”記錄與R[s]交換。實驗證明，這種方法可以大大改善快速排序在最壞情況下的性能。綜上所述，快速排序的最壞時間復雜度應為O(n2)，最好時間復雜度為O(n?lb?n)。9.4選擇排序9.4.1直接選擇排序直接選擇排序(StraightSelectSort)又稱為簡單選擇排序，其基本思想是：每一趟從待排序記錄中選出關鍵字最小的記錄，依次放在已排序記錄的最后，直至全部記錄有序。直接選擇排序是其中最為簡單的一種方法。直接選擇排序的具體做法是：第一趟排序將待排序記錄R[1]～R[n]作為無序區(qū)，從中選出關鍵字最小的記錄并與無序區(qū)中第1個記錄R[1]交換，此時得到的有序區(qū)為R[1]，無序區(qū)縮小為R[2]～R[n]；第二趟排序則從無序區(qū)R[2]～R[n]中選出關鍵字最小的記錄，將它與R[2]交換；第i趟排序時，從當前的無序區(qū)R[i]～R[n]中選出關鍵字最小的記錄R[k]，并與無序區(qū)中第1個記錄R[i]交換，得到新的有序區(qū)R[1]～R[i]。注意：每趟排序從無序區(qū)中選擇的記錄，其關鍵字是有序區(qū)中的最大值。根據(jù)上述過程類推，進行n-1趟排序后，無序區(qū)中只剩一個記錄，此時整個序列就是遞增有序的。排序過程如圖9.5所示，相應過程的C語言描述詳見算法9.6。算法9.6直接選擇排序。分析算法9.6可知，直接選擇排序需n-1趟排序，每一趟的比較次數(shù)與關鍵字的排列狀態(tài)無關。第一趟找出最小關鍵字需要進行n-1次比較，第二趟找出次小關鍵字需要進行n-2次比較，由此類推，總的比較次數(shù)為每趟比較后要判斷是否要進行兩個記錄的交換，交換則要進行三次記錄的移動。因此，直接選擇排序在最好情況下，記錄移動次數(shù)的最小值為0，最壞情況下最大值為3(n-1)。綜上所述，直接選擇排序的時間復雜度為O(n2)。這種排序方法是不穩(wěn)定的。9.4.2堆排序堆排序(HeapSort)是直接選擇排序的一種改進。在前面介紹的直接選擇排序中，為了從R[1,…,n]中選出關鍵字最小的記錄，必須進行n-1次比較；然后在剩余的無序區(qū)R[2,…,n]中找到關鍵字最小的記錄，又需要做n-2次比較。事實上，后面這n-2次比較中有許多比較可能前面的n-1次比較中已經(jīng)做過，但由于前一趟n-1次比較未保留這些比較結果，因此后一趟排序又重復了這些比較操作。堆排序正是以如何減少記錄的比較次數(shù)為出發(fā)點的一種改進算法。堆排序是在排序過程中，將按照向量存儲的記錄看成一棵完全二叉樹，利用完全二叉樹中雙親結點和孩子結點之間的序號關系來選擇關鍵字最小(最大)的記錄。因此，堆排序的記錄仍然按照數(shù)組順序存儲，而非采用樹的存儲結構，僅僅是借助完全二叉樹的順序結構特征進行分析而已，也就是該記錄數(shù)組從邏輯上可看作是一個堆結構。1.堆的定義堆是具有以下性質的完全二叉樹：所有非終端結點(非葉子結點)的關鍵字都大于或等于其左、右孩子結點的關鍵字，即滿足條件R[i].key≥R[2i].key并且R[i].key≥R[2i+1].key，這樣的完全二叉樹稱為大根堆；所有非終端結點(非葉子結點)的關鍵字都小于或等于其左、右孩子結點的關鍵字，即滿足條件R[i].key≤R[2i].key并且R[i].key≤R[2i+1].key，這樣的完全二叉樹稱為小根堆。從堆的定義我們可以看出，一個完全二叉樹如果是堆，則每棵子樹都是堆，且根結點(稱為堆頂)一定是當前所有結點中的最大者(大根堆)或最小者(小根堆)。例如序列{49,33,42,20,26,30,35,10,15}是一個大根堆，序列{10,20,15,33,26,30,35,49,42}是一個小根堆。這兩個堆的完全二叉樹表示及一維數(shù)組存儲表示如圖9.6所示。以下討論中以大根堆為例。2.堆排序1)堆排序的基本思想堆排序的基本思想是：首先將n個待排序記錄序列構建成一個大根堆，此時，整個序列的最大值就是堆頂?shù)母Y點(一個記錄對應一個結點)；接著將其與末尾結點(記錄)交換，此時末尾結點就為最大值；然后再將剩余n-1個結點重新調整成一個堆，這樣會得到n個記錄序列中次大的記錄。如此反復執(zhí)行n-1趟堆排序，便能得到一個有序(正序)序列。2)堆排序需要解決的關鍵問題在堆排序中，需要解決的關鍵問題是：(1)如何按堆的定義構建一個堆，即建立初始堆。(2)如何處理堆頂結點。(3)如何調整剩余結點，成為一個新的堆，即重建堆。下面通過示例詳細介紹堆排序的實現(xiàn)過程。如待排序記錄序列為{47,33,25,82,72,11}，一般情況下，升序采用大根堆，降序采用小根堆。關鍵問題(1)：構建初始堆。用給定無序序列{47,33,25,82,72,11}構建成一個大根堆，下面介紹初始堆的構建過程。顯然，無序序列{47,33,25,82,72,11}對應的圖9.7(a)是一棵完全二叉樹，但不是一個堆。由二叉樹的性質可知，所有序號大于

的樹葉結點已經(jīng)是堆(無子結點)。因此，初始建堆從序號為

的最后一個非葉子結點開始，通過調整使所有序號小于等于

的結點為根結點的子樹都滿足堆的定義。在對根結點為i?(如圖9.7(b)中結點33)的子樹建堆過程中，可能要對結點的位置進行調整(交換33和82)，以滿足堆的定義。但這種調整可能會導致原先是堆的下一層子樹不再滿足堆的定義的情況(如圖9.7(c)所示)，這就需要再對下一層進行調整，如此一層層進行下去，直到葉子結點。這種建堆方法就像過篩子一樣，把最大結點向上逐層篩選到根結點位置，把小的結點篩選到下層，該過程稱為篩選(sift)。建初始堆的過程如圖9.7所示。關鍵問題(2)：分區(qū)。在初始堆建好后，將待排序結點序列分成無序區(qū)和有序區(qū)兩部分，無序區(qū)是一個堆，有序區(qū)為空。此時將堆頂與堆中最后一個結點交換，則堆中減少一個結點，有序區(qū)增加一個結點，完成第一趟排序。以圖9.7(e)為例，則是交換結點82和結點11，于是有序區(qū)不再為空，而是有一個記錄82，如圖9.8所示。一般情況下，第i趟堆排序對應的堆中有

個結點，即堆中最后一個記錄是

。將R[1]和

交換完成第i趟排序。關鍵問題(3)：重新建堆。重新建堆也就是如何將堆中剩余的

個結點調整為堆。由關鍵問題(2)的處理結果(圖9.8)可知，這個

結點(即序列{11,72,25,33,47})序列相比之前的堆，只有堆頂結點(已交換成11)發(fā)生了改變，其余結點未發(fā)生改變，即根結點11的左、右子樹都是堆，以11為根結點的子樹不是堆。因此，此時要解決的問題是如何調整根結點11，使得

個結點構成的整棵二叉樹成為一個堆。下面在圖9.8(b)的基礎上介紹重新建堆過程。首先將結點11和其左、右孩子比較，根據(jù)堆的定義，應將11和72交換，如圖9.9(a)所示。經(jīng)過這一次交換，破壞了原來左子樹的堆結構，需要對左子樹再進行調整，如圖9.9(b)所示。調整后的堆如圖9.9(c)所示。其余各趟排序后的重新建堆操作過程都類似。3)堆排序的操作過程綜上可知，堆排序的操作過程(大根堆)如下(小根堆類似)：(1)將初始待排序關鍵字序列(R1，R2，…，Rn)構建成大根堆，此堆為初始的無序區(qū)；構建過程中每個非葉子結點都經(jīng)過一次調整，調整順序為從底層至頂層(調整過程中含有遞歸)，這樣調整下來這棵二叉樹整體上就是一個大根堆了，見圖9.7。(2)將堆頂元素R[1]與最后一個元素R[n]交換，得到新的無序區(qū)(R1，R2，…，Rn-1)和新的有序區(qū)(Rn)，且滿足

，見圖9.8。(3)將新的無序區(qū)調整為新的堆。由于交換后新的堆頂R[1]可能不滿足堆的性質，因此需要將當前的無序區(qū)(R1，R2，…，Rn-1)調整為新堆，見圖9.9；然后再次將R[1]與無序區(qū)最后一個元素R[n-1]交換，得到新的無序區(qū)(R1，R2，…，Rn-2)和新的有序區(qū)(Rn-1，Rn)。不斷重復此過程，直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成，見圖9.10。因此對于堆排序，最重要的兩個操作就是構建初始堆和調整堆。事實上，構造初始堆的過程也是調整堆的過程，只不過構造初始堆是對所有的非葉子結點都進行調整，而其余各趟重新調整建堆則是從整棵完全二叉樹的樹根開始調整。自堆頂至葉子的調整過程稱為“篩選”。3.堆排序算法下面先給出基于大根堆篩選調整堆的偽代碼，然后給出篩選調整堆的算法。篩選調整堆用偽代碼描述為：假設當前要篩選結點的編號為s，堆中最后一個結點的編號為t，并且結點s的左、右子樹均為堆，即R[s+1]～R[t]滿足堆的條件，堆調整算法如下：算法9.7篩選調整堆的算法。下面為堆排序算法。算法9.8堆排序算法。堆排序是一種選擇排序，它的運行時間主要消耗在初始建堆和重建堆時進行的反復篩選調整上。初始建堆需要O(n?lb?n)時間，第i次取堆頂結點重建堆需要O(n?lb?i)時間，并且n-1趟排序需要取n-1次堆頂結點，因此總的實際復雜度為O(n?lb?n)。堆排序的最壞、最好、平均時間復雜度均為O(n?lb?n)，它對原始記錄序列的排列狀態(tài)不敏感。相對于快速排序，這是堆排序最大的優(yōu)點。在堆排序算法中，只需要一個用于交換的暫存單元，所以算法的空間復雜度為O(1)。堆排序是一種不穩(wěn)定的排序算法。9.5歸并排序1．二路歸并排序的實現(xiàn)過程二路歸并排序的具體實現(xiàn)分為三步：1)一次歸并一次歸并算法是將相鄰的兩個有序子表歸并為一個有序子表。假設R[low]～R[mid]和R[mid?+?1]～R[high]表示同一數(shù)組中相鄰的兩個有序表，現(xiàn)在要將它們合并為一個有序表R1[low]～R1[high]，需要設置三個指示器i、j和k，其初值分別為這三個記錄區(qū)的起始位置，具體實現(xiàn)如算法9.9所示。算法9.9一次歸并算法。在算法9.9中，從兩個有序表R[low]～R[mid]和R[mid+1]～R[high]的左端開始，依次比較R[i]和R[j]的關鍵字，并將關鍵字較小的記錄復制到R1[k]中；然后指向被復制記錄的指示器和指向復制位置的指示器k右移，重復這一過程，直至其中一個有序表中全部記錄復制完畢；最后將另一個有序表的剩余記錄直接復制到數(shù)組R1[low]～R1[high]中。2)一趟歸并假設在待排序序列中，每個有序表的長度均為length(最后一個有序表的長度可能小于length)，那么在歸并前R[1]～R[n]中共有n/length個有序的子表：R[1]～R[length]，R[length+1]～R[2length],…,R[(n/length-1)length+1]～R[n]。一趟歸并算法多次調用一次歸并算法將相鄰的一對有序表進行歸并，完成一趟排序，具體算法見算法9.10。算法9.10一趟歸并算法。算法9.10中要考慮到三種情況，即有序表的個數(shù)為偶數(shù)且長度均為length、有序表的個數(shù)為偶數(shù)但是最后一個有序表長度小于length以及有序表的個數(shù)為奇數(shù)。3)歸并排序歸并排序算法如算法9.11所示，實際上就是對“一趟歸并”的重復調用過程。有序表的初始長度為1，每趟歸并后有序表長度增大一倍；若干趟歸并后，當有序表的長度等于n時，排序結束。算法9.11歸并排序算法。2．二路歸并排序示例及算法性能分析圖9.11所示為歸并排序的示例。對于一組待排序的記錄，其關鍵字分別為49,31,63,85,75,15,26,49。根據(jù)算法9.9，首先將這8個記錄看作是長度為1的8個有序表，然后兩兩歸并，直至有序表的長度不小于8。分析算法9.9、算法9.10以及圖9.11可知，第i趟歸并后，有序表長度為2i。因此，對于長度為n的無序表，必須執(zhí)行

趟歸并。每趟歸并的時間復雜度是O(n)，二路歸并排序算法的時間復雜度為O(n?lb?n)。算法中的輔助空間即數(shù)組R1的長度為n，因此空間復雜度是O(n)。歸并排序是一種穩(wěn)定的排序算法。與快速排序算法相比，這是它的最大特點。實際應用中并不提倡從長度為1的序列開始進行二路歸并。可以先利用直接插入排序得到較長的有序表，然后再進行兩兩歸并。二者的混合排序仍然是穩(wěn)定的。9.6基數(shù)排序9.6.1多關鍵字排序的概念1．多關鍵字的排序過程多關鍵字排序的定義：給定一個含有n個記錄的序列{R1,R2,…,Rn}，每個記錄Ri含有d個關鍵字

。多關鍵字排序是指對d個關鍵字有序，即對于序列中任意兩個記錄Ri和Rj(

)都滿足如下有序關系：2．多關鍵字的排序方法多關鍵字排序按照從最主位關鍵字到最次位關鍵字或從最次位關鍵字到最主位關鍵字的順序逐次排序，有兩種基本的方法：1)最次位優(yōu)先法最次位優(yōu)先法簡稱LSD法(LeastSignificantDigitFirst)，是指先從kd開始分組和收集，同一組記錄具有相同的關鍵字kd，再按kd-1進行分組和收集，依次重復，直到按最主位關鍵字k1進行分組和收集后得到一個有序序列為止。2)最主位優(yōu)先法最主位優(yōu)先法簡稱MSD法(MostSignificantFirst)，是指先按最主位關鍵字k1進行分組和收集，同一組子序列中的記錄具有相同的關鍵字k1；再對各組子序列按k2排序分割成若干更小的子序列，每個更小的子序列具有相同的k2；依此類推，直到按最次位關鍵字kd對各子組分組和收集后得到一個有序序列為止。9.6.2基數(shù)排序的過程及鏈式基數(shù)排序算法1．基數(shù)排序的基本思想基數(shù)排序是指將待排序記錄的關鍵字看成由若干個子關鍵碼(字)復合而成，每個子關鍵碼作為一個“關鍵字”。比如關鍵字為3位整數(shù)，則可以把關鍵字拆分成3個關鍵字，每位看成一個關鍵字，然后對單關鍵字的排序就可以按上述介紹的多關鍵字排序方法進行。拆分后的每個關鍵字的取值范圍相同，我們稱這個取值范圍為“基”，并記作r?；贚SD的基數(shù)排序的基本思想是：根據(jù)