Sorting算法与算法的分析技术课件

Sorting演算法與演算法的分析技術12.1排序（Sorting）問題

有關排序的幾個基本概念：1.全序集：數據集合D稱為關於關係“<”的全序集，如果滿足1°a<b，a=b，b<a三者必居其一；2°a<b，b<c，則a<c。全體整數集、實數集、字串集等都是全序集。2.排序（Sorting）問題：已知：n項記錄R1，R2，…，Rn，其一個域稱為關鍵字（Key），關鍵字值K1，K2，…，Kn屬於一全序集。要求：重排n項記錄為Rπ(1)，Rπ(2)，…，Rπ(n)，其中π：π(1)，π(2)，…，π(n)，為1,…,n的一個排列，使對應的關鍵字滿足：Kπ(1)≤Kπ(2)≤…≤Kπ(n)。23.穩定（Stable）排序演算法：如果排序問題滿足：若Rπ(i)=Rπ(j)

且i<j則π(i)<π(j)，則稱其為穩定排序演算法。穩定排序保證序列中關鍵字相同的記錄在排序過程中不會交換次序。4.內部（Internal）排序演算法：數據在高速隨機存儲設備上（記憶體）進行排序操作，這時數據間的比較和移動指令的代價一般是相同的。5.外部（External）排序演算法：數據主要駐留在外部的低速存儲設備（硬碟、磁帶）上，數據在內存與硬碟（磁帶）之間的傳送、移動的代價明顯高於數據比較操作，因此，外部排序演算法的設計不同於內部排序。36.原址排序演算法：在排序過程中除了全部輸入數據所佔用的空間之外，只需有限的額外空間。如果額外空間的大小與記錄數n無關，則稱為原址排序。7.基於關鍵字比較的排序演算法：這類排序演算法中僅對關鍵字進行比較和移動操作，因此關鍵字的比較和移動是演算法的基本操作。42.2O(n2)階的排序演算法

2.2.1選擇排序（SelectionSorting）

1.選擇排序的思想：把待排序的L[1..n]視為兩個部分：L[1..i-1]為已排序部分，L[i..n]為未排序部分。排序步驟為：

1°i=1；2°選擇：在L[i..n]中求最小元L[k]，i≤k≤n；3°交換L[i]與L[k]，i++，if（i<n）goto2°；4°停止。2.演算法的描述：輸入：L[1..n]存放待排序元素，n(≥0)為元素個數。輸出：L[1..n]按關鍵字遞增順序排列。演算法2.1選擇排序演算法SelectSort53.演算法的分析：

關鍵字的比較發生在if語句中，總的比較次數為：演算法中的比較次數與n個關鍵字的值無關，因此最壞情形和平均情形的比較總次數相同。因此，演算法是O(n2)階的。空間代價只額外佔用了幾個工作單元，因此，它是個原址排序演算法。64.討論：

演算法SelectSort按比較次數計算的最好情形時間複雜度為：如果把關鍵字的移動作為基本操作，情況有所不同。從演算法中的if語句可看出，關鍵字移動min=L[j]的次數可能少於比較min>L[j]的執行次數。另外，函數Swap()需要3次移動，共3(n–1)次。因此，選擇排序演算法的平均移動次數會比較小，而最好情形則為3(n–1)。當數據記錄比較大時，移動代價大於比較代價，選擇排序也可能有較好的性能。72.2.2插入排序（InsertionSorting）

1.插入排序的思路：與選擇排序不同，它是從無序部分不經選擇，任取一元，然後插入到有序部分的正確位置上。其步驟為：L[1..n]分為兩部分：L[1..i]為有序部分，L[i+1..n]為未排序部分。1°i=1；2°把L[i+1]插入到L[1..i]中的正確位置，i++；3°if(i<n)goto2°；4°停止。2.演算法的描述：演算法2.2插入排序演算法InsertSort83.演算法的分析：最壞情形：最好情形：平均情形：設輸入序列滿足兩個條件：1°n個關鍵字值是不同的，這可以簡化分析；2°n個元素的所有不同的排列具有等可能性。在把L[i]插入到有序的L[1..i–1]的過程中，共有i種可能的位置，由假設2°可知落入每個位置的概率為1/i。而這i種情形所需要的比較次數分別為1，2，…，i-2，i-1，i-1，因此期望的比較次數為：9因此，

插入排序雖然也是O(n2)階的演算法，但在一般情形下，會比選擇排序塊。演算法的空間代價：基本上不需要額外空間，也是一種原址排序演算法。它也是穩定的。104.討論：在基於相鄰元比較交換的排序演算法中，InsertSort是最優的。如果把數據的移動作為基本操作，每一次數據比較都有一次數據移動與之對應。因此，除了在外迴圈的n–1次移動之外，數據比較與移動次數是一致的，這與SelectSort演算法是不同的。2.2.3起泡排序（BubbleSorting）

演算法2.3起泡排序演算法BubbleSort

演算法BubbleSort的比較次數是確定的：移動次數與數據比較相對應，交換函數Swap需要三次數據移動，在最壞情形下是比較次數的三倍，而在最好情形下不需要移動。11BubbleSort是穩定的、原址排序演算法。BubbleSort的一種實用改進演算法是在程式中設一標記位，當一遍掃描中沒有交換發生，則排序停止。演算法2.4起泡排序的改進演算法BSort

演算法BSort的比較次數有所改進：122.3基於相鄰元比較的排序演算法和

希爾（Shell）排序

2.3.1插入排序的最優性定理2.1基於相鄰元的比較及交換的排序演算法1°在最壞情形下，至少需要n(n-1)/2次比較，即W(n)=Ω(n2)；2°在平均情形下，至少需要n(n-1)/4次比較，即A(n)=Ω(n2)。把n個元素排列問題歸結為以n個關鍵字1,2,…,n的任一排列π：π(1),π(2),…,π(n)作為輸入，排序過程就是消滅序列中的逆序的過程。所謂逆序（Inversion）（π(i),π(j)），即i<j且π(i)>π(j)。例如序列（2，4，1，5，3）有4個逆序：（2，1），（4，1），（4，3），（5，3）；13證明的關鍵是，在序列中，如果兩個相鄰元為一逆序，經過交換肯定消除了這個逆序，但這一交換只能消滅這一個逆序。證明：1°存在一種排列：n,n-1,…,2,1為全逆序，共包含n(n-1)/2個逆序，故在最壞情形，任一依靠相鄰元比較、交換完成的排序過程，至少需n(n-1)/2次比較，即W(n)=Ω(n2)。2°對於平均情形，實際上需要計算1,2,…,n的所有不同排列的平均逆序數。當n>1時，任一排列π，必有一個唯一的、不同於它的對偶排列；π’是π的對偶排列，即π’是π的反序：π’(1)=π(n)，π’(2)=π(n-1),…,π’(n)=π(1)，例如，(2,4,1,5,3)的對偶排列是(3,5,1,4,2)；1～n之間的任一整數對（i,j）（i≠j）如果是逆序，必然出現在任一排列π及其對偶排列π’二者之一；141～n之間共有不同的整數對（i,j）n(n-1)/2個；1,…,n的所有排列是成對出現的，故每一排列平均有n(n-1)/4個逆序，平均至少需n(n-1)/4次比較，即A(n)=Ω(n2)。由定理知：1°演算法InsertSort和BSort在上述條件下是最優的；2°為了設計比θ(n2)階更快的排序演算法，數據的比較和移動必須在間隔較大的元素之間進行。2.3.2希爾（Shell）排序

該排序演算法首先把輸入序列分成h個間距為h的子序列，對每個子序列進行h–sorting。例如，取h=6，則L[1..n]分為6個子序列：15L[1],L[7],L[13],…L[2],L[8],L[14],…L[3],L[9],L[15],…L[4],L[10],L[16],…L[5],L[11],L[17],…L[6],L[12],L[18],…進行h–sorting後，就是逐步減少h的大小，直至把h減少到1，完成排序工作。在最後一次h=1時，採用InsertSort或BSort演算法，可能出現最好情形或幾乎最好情形，而InsertSort的B(n)=n-1，故總比較次數有望縮小。Shell排序演算法有幾個因素可以有大的變化：第一個h值如何取，h值如何逐步減少到1每次h–sorting採用何種演算法，都對整個演算法性能有大的影響。16Shell排序演算法：輸入：KeyL[1..n]：關鍵字數組；inth[1..t]：遞增整數序列，h[1]=1；演算法2.5希爾排序演算法ShellSort當t=1時，ShellSort退化為InsertSort。增量序列ht,ht-1,…h1=1應事先確定，一個較好的選擇是：h1=1,hs+1=3hs+1其中1≤s≤t使ht+1<n，ht+2≥n。當n比較大時，Shell排序比插入排序要快，因為當ht>1時，在h-sort過程中，一次比較和交換可以至多消除2ht-3個逆序。關於Shell排序的研究至今仍在繼續，因為對於已知的n，怎樣的增量h序列使演算法性能最佳，其最優時間複雜度如何，目前尚不清楚。一些比較好的成果指出，適當選取增量序列，Shell排序演算法的複雜度可以達到O(nlog2n)和O(n1.25)。172.4O(nlogn)階的排序演算法

2.4.1快速排序演算法QuickSort

1.演算法的思路：其關鍵操作是劃分（partition）：取n元中的任一元（例如首元）作為劃分元（pivot），令其餘n–1個元與劃分元經過比較，把較小者移至劃分元左邊，而較大者置於劃分元之右，形成兩個序列。左序列的所有元都小於劃分元，右序列都不小於劃分元，然後用同樣的方法對左、右序列排序，從而完成排序目標。如Fig.2.1所示。劃分過程中，劃分元被放置到了排序過程的最終位置，其左、右兩個序列雖然是無序的，但作為整體卻被確定了位置，因此在完成左、右子序列的排序之後，整個排序過程也就完成。18192.演算法QuickSort：

輸入：未排序的L[1..n]，為了方便寫遞歸程序可表示為L[first..last]。輸出：已排序的L[first..last]。演算法2.6快速排序演算法QuickSort3.劃分演算法Partition：

QuickSort的核心是Partition。劃分過程中，元素在數組中有較大幅度的移動，因此，這也是快速排序速度較快的內在原因。有各種不同的劃分演算法，其性能也不盡相同。一種較好的劃分演算法，其思想如Fig.2.2所示。2021程式開始，指針left=first，指向空位，即劃分元pivot的位置，指針right=last，指向最右元，序列L[2..n]全為未做劃分處理部分；首先自right開始，向左掃描，找到第一個小於pivot的元素，把它送往left指向的左空位，left右移一位；然後從left向右掃描，找到第一個不小於pivot的元素，把它送到right指向的位置（右空位），right左移一位，完成劃分的一次迴圈。重複上述迴圈，直到left=right，令L[left]=pivot，返回left。演算法2.7快速排序的劃分演算法Partition22劃分過程中的實例：

234.QuickSort的複雜度分析：

最壞情形的總比較次數為：平均時間性能分析：首先假設：1°n個元素的關鍵字值互不相等。2°n個元素的關鍵字的所有不同排列，以等可能即相等的概率出現在輸入序列中，因此，劃分元的最終位置i也以相等概率分別取值為1,…,n。QuickSort的平均比較次數A(n)應滿足遞歸方程：

24可簡化為： （公式2.4.1）在最好情形時劃分元總是處於序列的中間，遞歸方程可大致簡化成：25定理2.2在輸入序列的所有排列具有等可能性的條件下，演算法QuickSort的平均數據比較次數為:其中c>0為一常數。證明方法1：採用歸納法

當n=1時，A(n)=0，cnlnn=0，命題成立；假設當1≤k＜n，A(K)≤cklnk

成立；由公式2.4.1和假設得：

根據積分的性質：26於是，當n＞1取c=2時，A(n)≤2nlnn

成立。推論2.3在輸入序列的不同排序均勻分佈的假設條件下，演算法QuickSort的平均數據比較次數為:證明方法2：為了簡化關於A(n)的遞歸方程，由

27推出：為了消除過多的A(i)項，計算nA(n)-(n-1)A(n-1)：即 令 則有：28這是一個較為簡單的遞歸方程，不難得到：由Harmonic級數， 為Euler常數， ，得：29

由此可以得到A(n)的更準確的運算式：5.空間複雜度分析：

單從劃分演算法來看，QuickSort除有限的工作單元外，不佔用額外的空間，但在遞歸過程中，待排序段的首元和尾元下標需要保存，在最壞情形可能遞歸n–1次。因此，QuickSort在最壞情形下需要的空間代價為S(n)=θ(n)。306.關於QuickSort演算法的幾點討論：

1）在最重要的性能，即平均時間代價上優於其他演算法。當n比較大時，一般運行確實很快，因此被廣泛採用。2）改善劃分元的選取，可能產生更好的效果。常見的幾種劃分元的選取方法是：

·在first,…,last中取亂數i，以L[i]代替L[1]；

·

在first,…,last中，取中間值i=int((first+last)/2)；

·

取first，last，int（（first+last）/2）三者的中值為劃分元下標。3）演算法的核心是劃分。不同的劃分策略會影響到移動次數。4）QuickSort採用遞歸演算法的形式，簡明但運行時在時間和空間上開銷較大。一種改進方法是使用由用戶設計的棧取代遞歸。演算法2.8快速排序的改進演算法QStackSort

315）空間複雜度的改進：快速排序演算法的額外空間需求與遞歸和棧有關。當把兩次遞歸調用改為單側進棧，可以改進空間複雜度。當輸入為昇冪（已排序）時，共需n–1次進棧，佔用O(n)空間。如果在程式中，每進行一次劃分以後，就對[f,i-1],[i+1,l]兩段進行比較，把較大的一半進棧，先計算（劃分）較小的一半，其內層迴圈次數（即棧的長度）必然小於logn，因此空間代價可降為O(logn)。6）快速排序演算法對於較小的n，其性能不及插入演算法。因此，可以設計一種綜合演算法，當輸入序列長度小於某個固定值（例如n0=50）時，改用InsertSort進行排序。7）快速排序的最壞情形時間複雜度和額外空間代價，無論如何改進，總是它的缺點和不足。322.4.2合併排序演算法MergeSort

1.演算法的思路：

把序列分為兩部分，分別遞歸（排序）後，再把兩個有序序列合併為一個有序序列。如Fig.2.4。332.有序序列的合併演算法：

演算法2.9有序序列的合併演算法Merge

3.合併排序演算法MergeSort：演算法2.10合併排序演算法MergeSort

4.演算法的複雜度分析：

該演算法對兩個長度為m的有序序列的合併，在最壞情形下至少需要2m–1次比較。演算法在最壞情形下的比較次數可用遞歸方程表示： （公式2.4.2）34忽略n為奇數的情形，由主項定理可得 。假定n=2k（k為正整數），則公式2.4.2可以簡化為：直接推導得：該演算法平均情形比較次數A(n)=Ω(nlogn)。其空間代價較大，需要大小為O(n)的額外空間。該演算法是不穩定的。355.關於合併排序演算法的討論：

1）對於時間複雜度而言，在最壞情形下大大優於快速排序，但在平均情況下不一定優於快速排序。數據的移動次數也會對時間性能有所影響。2）可以比較容易地改寫成非遞歸程序。3）合併排序的一種改進方法是充分利用輸入序列中可能的已排序部分。演算法2.11合併排序改進演算法IIMergeSort2

例如，輸入序列為（4，12，8，6，0，11，27，5，20），實際上是4個有序串：（4，12），（8），（6，，11，27），（5，20）。第一趟掃描合併為：（4，8，12），（5，6，9，11，20，27），第二趟掃描就已排好序。這個演算法在在最好情形下的比較次數為B(n)=n–1。364）主要缺點是空間代價較大，每次合併操作都需要與待合併的數據等長的額外空間，其額外空間代價為O(n)階。

5）適合於並行計算。2.4.3堆排序演算法HeapSort

1.堆排序演算法的思路：

如Fig.2.5，演算法把待排序的數組L[1..n]視為一個二叉樹，數組元素依次按廣度第一的順序與二叉樹的結點相對應。結點間的鏈接利用下標來計算。對於結點i，如果2i>n，則i為葉結點，否則，2i為其左兒子下標，2i+1為其右兒子下標。37這樣的二叉樹的所有的葉結點位於樹的最底層即d層或d–1層，在最底層的葉結點位於左端。演算法由兩部分組成，第一部分稱為建堆（BuildingHeap），就是通過數據的比較和移動，使得二叉樹上每個內部節點的值大於其左、右子結點的值。這樣的二叉樹稱為堆（Heap），如Fig.2.6所示。38第二部分稱為根刪除—堆修復（Delete–Fix）過程，如Fig.2.7，可以描述為：for(i=n;i>=2;i--){Swap(L[1],L[i]);

FixHeap(L[1..i-1]);}堆的修復過程，就是每次把兩個兒子中的較大者上升，直到元素L[i]降到適當的位置為止。這一Delete–Fix過程至多重複n次，每次修復所需的比較次數不會大於樹高，而平衡二叉樹的高不會大於logn（n為結點數），故此演算法應有較好的性能。2.演算法的描述：

演算法2.12堆排序演算法HeapSort

39403.演算法的分析：

令n'=2d–1且n'/2≤n≤n'，並把建堆過程寫成遞歸形式：voidBHeap(H){

BHeap(Hleft);

BHeap(Hright);

FixHeap(L,n,root,L[root]);return;}它與函數BuildHeap是等價的。由於FixHeap(L,n',root,L[root])的比較次數為2logn'，故有：41根據主項定理：因為b=2，c=2，取ε=0.1，有

故

因此，建堆過程在最壞情形下的時間複雜度為線性階。對於演算法的第二部分，因為對於有k個結點的堆進行修復，至多需要 次比較，即全部比較次數至多為：

42定理2.4

HeapSort在最壞情形下的數據比較次數為W(n)=2nlogn+O(n)，即HeapSort是一個θ(nlogn)階的排序演算法。HeapSort在平均情形下的比較次數是O(nlogn)。它是一個原址排序演算法。4.堆排序演算法的缺點：

1）當輸入序列為有序或幾乎有序時，堆排序演算法根本沒有利用序列有序的條件，需要θ(nlogn)次比較，與最壞情形相比幾乎沒有改進。2）堆排序大約需要2*nlogn次比較，在大多數情況下，比快速排序和合併排序要慢。5.加速堆排序演算法AHeapSort：

在原來的FixHeap演算法中，每一次需要做兩次比較，即：if(L[vac*2]<L[vac*2+1])和if(k<L[larger])。改進後的AFixHeap演算法，每一步只做一次比較。43演算法2.13改進的堆恢復過程AfixHeap

在大多數情況下，第一個迴圈把空位移至葉結點，共用logn次比較，而向上的移動次數則很少。結點的比較次數在最壞情形下仍為2logn，但在大多數情況下則接近（大於）logn。如Fig.2.9所示。44為了把最壞情形下的比較次數由2nlogn縮小到nlogn，進一步改進的思路描述如下：設堆的高度為 ，空位的移動分為下移和上移，每下移、上移一層需要一次比較。開始時空位在頂點，設待插入元素的最終應插入的位置在h層，0≤h≤H。1°m=H/2；2°空位下移m層，共用m次比較；3°if(L[vac/2]<k)goto5°；4°m/=2;goto2°；5°空位上移至最終位置，至多用m次比較。利用這一改進，AheapSort在最壞情形下的數據比較次數應為W(n)=nlogn+nloglogn+O(n)。456.另一種樹排序演算法：

如果排序時建成一個頂元最小的堆（如圖Fig.2.10），根消除後很難修復（合併）為一個堆，這就是堆排序為什麼要把最大元素放到堆頂的原因。

46有改進演算法LheapSort，把數組L[1..n]視為一個被稱為左完全2-3樹（簡稱LECT樹或L樹）的樹結構。實例：L[1..n]，n=23。

每次取不大於剩餘元素數的2k-1個元素形成一個完全二叉樹，因n=15+7+1，故n=23個元的數組唯一地與Fig.2.11的樹結構對應。數組元素按深度優先的順序排列。47對於下標為i的結點，i+1是其左子結點的下標，右子結點的下標則需要利用其右鄰完全樹的根下標r來計算，即(i+r+1)/2。例如，結點2的左子結點下標為3=2+1，該完全樹的右子結點下標為6=（2+9+1）/2。這需要至多為logn的額外空間來保存各個完全子樹的根下標，即保留24、9、2、1四個值。LHeapSort同樣由兩部分——建堆過程和刪除—整理過程組成建堆過程之後，L[1..n]已經對應一個n=23結點的左完全2-3樹，故L[1]已是最小元。前幾步刪除—整理過程如圖：48495051

刪去L[1]，空位置不動，由L[2..23]形成另一棵L樹—LT2；

LT2已是一個堆，故不需整理，轉至下一步刪除—整理；

刪去L[2]，由L[3..23]形成新的L樹—LT3；

整理LT3稱為堆，其過程與HeapSort的FixHeap過程類似。一個簡單的實例：n=11，L[1..11]={8，4，7，2，3，9，6，1，10，11，5}。下圖是LheapSort(L,n)的排序過程，其中1～11步是建堆過程，12～23步是刪除—整理過程。52537.演算法LHeapSort的分析：

1）最壞情形和平均情形：在最壞情形下的時間複雜度為W(n)=θ(nlogn)。LHeapSort在最壞情形、平均情形下的性能與HeapSort大致相同。已有的研究成果指出，LHeapSort在最壞情形下的移動次數約為1.5nlogn次。2）最好情形：

表2.1有序條件下的各種演算法性能

當輸入序列為有序時，LHeapSort極快，不同演算法的實驗數據如表：54LHeapSort在最好情形下的比較次數為B(n)=2n=O(n)，數據移動次數為0次，而HeapSort在最好情形下的複雜度為B(n)=θ(nlogn)，已有的研究結果認為是B(n)≥nlogn/2。3）當輸入序列為幾乎有序時，性能比其他排序演算法要好。4）空間代價：LHeapSort在排序過程中需要一個長度為logn+1的整型數組，用於存放各個完全數的根的下標。552.5排序演算法的時間複雜度下界

2.5.1判定樹（DecisionTree）模型對於n=3，設三個關鍵字為a，b，c，可以用程式區分出六種可能的排列次序。它對應於Fig.2.13的判定樹（程式）561°比較排序演算法與圖中的判定樹是一致的；2°任一比較排序演算法（對某一確定n值）都與一棵判定樹相對應；3°判定樹的全部外部結點對應於所有不同的排序結果。例如，n=3時，a，b，c的六種不同結果都應包含在判定樹的外部結點中。從DT的根到一個葉結點的路長，即某條路上的內部結點數，也是演算法運行所需要的比較次數。判定樹DT的最長路長即為演算法在最壞情形下的比較次數，平均路長（從根到所有葉結點路長的平均值）即為演算法在平均情形下的比較次數。因此我們把對於演算法在最壞情形下和期望的時間複雜度的計算變換為對於演算法對應的判定樹的最長路長和平均路長的計算。572.5.2最壞情形引理2.5判定樹DT的葉結點數l與樹的深度d有如下關係： l≤2d。引理2.6有l個葉結點的DT的深度為：引理2.7任意一棵n元判定樹DT至少有n!個葉結點。定理2.8任何n元比較排序演算法在最壞情形下的比較次數為：2.5.3平均情形判定樹DT中，根到所有葉結點的路徑之和稱為DT的外部路長epl（externalpathlength），而epl/l就是平均路長，其中葉結點數l>n!。58引理2.9在所有具有l個葉結點的判定樹中，若某棵樹的epl最小，則這個DT的所有葉結點是平衡的，即它的葉結點之多分佈在樹的最下麵兩層。如Fig.2.14。證明：

設判定樹有葉結點X位於k層，k<d–1。因DT有d層，故必有葉結點Z1，Z2在d層，其父結點Y在d–1層。

59對判定樹DT做一小的調整，把葉結點Z1，Z2從父結點Y上摘下，掛到結點X上（如Fig.2.15）。顯然它仍然是一個有l個葉結點的判定樹DT’，但外部路長epl發生了變化。具體地說有三條路長髮生了變化：在DT上，從根到X，Z1，Z2的三條路長為k+2d。在DT’上，從根到Z1，Z2，Y的三條路長為2(k+1)+d-1=2k+d+1。因k<d–1，所以2k+d+1<k+(d-1)+d+1=k+2d，得證。60引理2.10有l個葉結點的判定樹DT的最小epl可表示為：1°l=2k，有上面引理可以斷定，最佳DT為完全滿二叉樹，即葉結點全在底層，顯然

epl=llogl，即為上式。2°若l≠2k，設DT深度為d，全部葉結點在d層和d–1層，如Fig.2.16所示。這時，因 ，因此有下麵的定理：61定理2.11任何n元比較排序演算法在平均情形下的比較次數至少為log(n!)，即A(n)≥log(n!)≈nlogn–1.443n證明：因任一n元比較排序演算法的判定樹的葉結點數l≤n!，且所以622.6排序演算法的有關研究

比較排序演算法的改進與分析基數排序（RadixSorting）

例如當元素關鍵字有三位十進位整數組成時，演算法如Fig.2.17所示。外部排序演算法粗排序（RoughlySorting）

並行排序（ParallelSorting）第二章完6364演算法2.1選擇排序演算法SelectSorttemplate<classKey>voidSelectSort(KeyL[],intn){

inti,j,k;

for(i=1;i<n;i++){

for(j=i+1,k=i;j<=n;j++)

if(L[k]>L[j])k=j;Swap(L[i],L[k]);}

return;}返回65演算法2.2插入排序演算法InsertSort

template<classKey>void

InsertSort(KeyL[],intn){

inti,j;Keytemp;

for(i=2;i<=n;i++){

for(j=i-1,temp=L[i];j>0;j--){

if(L[j]>temp)L[j+1]=L[j];

else{L[j+1]=temp;break;}}}

return;}返回66演算法2.3起泡排序演算法BubbleSort

template<classKey>void

BubbleSort(KeyL[],intn){

inti,j;

for(i=1;i<n;i++){

for(j=n;j>i;j--)

if(L[j]<L[j-1])Swap(L[j],L[j-1]);}

return;}返回67演算法2.4起泡排序的改進演算法BSort

template<classKey>void

BSort(KeyL[],

intn){

intp=1;

inti,j;

for(i=1;(i<n)&&p;i++)for(j=n;j>i;j--){p=0;

if(L[j]<L[j-1]){p=1;Swap(L[j],L[j-1]);}}}

return;}返回68演算法2.5希爾排序演算法ShellSorttemplate<classKey>void

ShellSort(KeyL[],intn,intt,int

h[]){

for(inth=h[t],s=t;s>=1;s--,h=h[s])

for(intk=1;k<=h;k++)

for(inti=h+k;i<=n;i+=h){Keytemp=L[i];

intj=i–h;

while((L[j]>temp)&&(j>0)){L[j+h]=L[j];j-=h;}L[j+h]=temp;}

return;}返回69演算法2.6快速排序演算法QuickSort

template<classKey>void

QuickSort(KeyL[],intfirst,intlast){

if(first<last){

intsplit=Partition(L,first,last);

QuickSort(L,first,split–1);

QuickSort(L,split+1,last);}

return;}返回70演算法2.7快速排序的劃分演算法Partitiontemplate<classKey>intPartition(KeyL[],intfirst,intlast){

intleft=first;intright=last;Keypivot=L[first];

while(left<right){

while(L[right]>=pivot)right--;L[left++]=L[right];

while(L[left]<pivot)left++;L[right--]=L[left];}L[left]=pivot;

returnleft;}返回71演算法2.8快速排序的改進演算法QStackSort

template<classKey>void

QStackSort(KeyL[],intn){

intf,l,i;stack.push(1,n);

while(!stack.empty){stack.pop(f,l);

while(f<l){i=Partition(L,f,l);Stack.push(i+1,l);l=i–1;}}

return;}返回72演算法2.9有序序列的合併演算法Mergetemplate<classKey>voidMerge(KeyS[],intl,intm,

intr){KeyT[];

inti=l;intj=m+1;intk=l;

while((i<=m)&&(j<=r)){

if(S[i]<=S[j])T[k++]=S[i++];

elseT[k++]=S[j++];}

if(i>m)

for(intp=j;p<=r;p++)T[k++]=S[p];else

for(intp=i;p<=m;p++)T[k++]=S[p];

for(p=l;p<=r;p++)S[p]=T[p];

return;}返回73演算法2.10合併排序演算法MergeSorttemplate<classKey>void

MergeSort(KeyL[],intfirst,intlast){

if(first<last){

intmid=(first+last)/2;

MergeSort(L,first,mid);

MergeSort(L,mid+1,last);Merge(L,first,mid,last);}

return;}返回74演算法2.11合併排序改進演算法IIMergeSort2template<classType>voidMergeSort2(TypeL[],intn){

while(n>1){

inti=1;intj,k;

do{

for(j=i;(j<n)&&(L[j]<L[j+1]);j++);

if(j==n)return;

for(k=j;(k<n)&&(L[k]<L[k+1]);k++);

if(k>j){Merge(L,i,j,k);i=k+1;}}

while(i<=n)}

return;}返回75演算法