兩種交換排序算法的分析比較

李家宏，孫慶英

(1.淮陰師范學院，江蘇 淮安 223300；2.淮陰師范學院，淮安市大數(shù)據(jù)智能計算與分析重點實驗室，江蘇 淮安 223300)

0 引言

1 排序的定義及分類

排序(sort)就是把一組雜亂無章的數(shù)據(jù)記錄或元素，按照一定的關(guān)鍵碼重新排列成有序的序列。假定給定記錄序列有n個記錄(R1,R2,...,Rn) ,它們的關(guān)鍵碼分別為(Ks1,Ks2,...,Ksn) ,排序的過程就是將這些記錄排列成順序為(Rs1,Rs2,...,Rsn) 的序列，使得相應的關(guān)鍵碼滿足Ks1≤Ks2≤... ≤Ksn（升序或非降序）或Ks1≥Ks2≥... ≥Ksn（降序或非升序）[1-2]。

排序按照數(shù)據(jù)存儲的介質(zhì)分為內(nèi)部排序和外部排序。內(nèi)部排序是數(shù)據(jù)元素全部放在內(nèi)存中的排序。外部排序是數(shù)據(jù)元素太多無法同時存放在內(nèi)存中，根據(jù)排序過程的要求，在內(nèi)存和外存之間多次交換移動數(shù)據(jù)的排序。在本文中，主要涉及的排序算法均為內(nèi)部排序算法[3]。

對于內(nèi)部排序依據(jù)不同的排序原則，一般分為插入排序、選擇排序、交換排序、歸并排序四大類，結(jié)合目前比較經(jīng)典的7大排序算法：直接插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、二路歸并排序[4]。具體分類如圖1所示。

圖1 常用排序算法分類

由于排序的類別較多，各種排序的原理原則不盡相同，本文主要以交換排序為例來簡單分析一下排序算法。

2 交換排序的算法及實現(xiàn)

交換排序，顧名思義就是基于“交換”思想的排序。即通過對序列中元素進行兩兩比較來判斷是否符合排序要求，如果不符合就交換他們之間的位置來達到滿足排序的目的。假定在待排序序列中選取兩個元素Ri和Rj，若滿足i＜j且Ri＞Rj則通過交換Ri和Rj的位置來實現(xiàn)滿足排序要求實現(xiàn)Ri＜Rj，完成排序過程。交換排序的主要方法有冒泡排序和快速排序。

2.1 冒泡排序

冒泡排序就是在排序交換過程中，類似水冒泡。較大的數(shù)往下沉、較小的數(shù)類似氣泡一樣往上冒，?。ù螅┑脑財?shù)據(jù)經(jīng)過不斷的交換，整個過程就像冒泡一樣，最小值元素一直往上“冒泡”，所以稱為冒泡排序(Bubble Sort) 。

冒泡排序算法的基本思想：對序列中相鄰的兩個元素進行比較，如果符合排序要求就保持不變，如果不符合排序要求，就進行位置交換。通過重復循環(huán)訪問序列，直到?jīng)]有可交換的元素為止，整個序列排序完成。冒泡排序每一趟排序結(jié)果只能確定將一個數(shù)歸位，即第一次排序的結(jié)果將序列的末位上的數(shù)確定，第二次排序的結(jié)果將序列的倒數(shù)第二位上的數(shù)確定，以此類推，假設(shè)有n個數(shù)進行排序，則需要進行n-1 次的排序操作。第1 次排序，通過“冒泡”，將前n個元素中最大的值移動到序列的最后一位，這輪排序結(jié)束后就剩下前n- 1個元素未排序。第i次排序，此時剩余前n-i+ 1個元素未排序，通過“冒泡”，將前n-i+ 1個元素中最大的值移動到剩余序列的最后一位。最后第n- 1 次排序，只剩余2 個元素未排序，將其中較大的值移動到后一位，整個排序完畢[5]。冒泡排序的基礎(chǔ)算法如圖2。

圖2 冒泡排序的基礎(chǔ)算法

通過對上述程序算法分析不難發(fā)現(xiàn)，對于有些排序序列在經(jīng)歷過幾次遍歷之后就達到了排序要求，但程序還繼續(xù)執(zhí)行，繼續(xù)進行遍歷，從而浪費了計算機資源。從冒泡排序算法交換排序思想中，不難發(fā)現(xiàn)判斷冒泡排序的結(jié)束條件應該是一趟排序過程中有無進行交換的操作。為此，為了優(yōu)化冒泡排序，很多時候我們在每趟排序開始前設(shè)置標志，用來記錄每輪遍歷過程中是否有數(shù)據(jù)交換發(fā)生，如果有交換發(fā)生繼續(xù)執(zhí)行下一次，如果沒有發(fā)生數(shù)據(jù)交換直接可以判斷整個冒泡排序已經(jīng)完成。改進的冒泡排序算法如圖3。

圖3 改進冒泡排序算法

2.2 快速排序

快速排序(quick sort) 是對冒泡排序的一種改進。冒泡排序中每次比較相鄰的兩個數(shù)據(jù)，每次交換只能移動一個位置，導致在程序的執(zhí)行過程中比較次數(shù)和移動的次數(shù)均較多。為了減少比較和移動的次數(shù)，快速排序中采取了比較和移動從兩端向中間進行，值較大的數(shù)據(jù)一次就能從前面移動到后面，反之值較小的數(shù)據(jù)也能一次從后面移動到前面[6]。

導致華盛頓沒有積極因應緬甸提出的各種安全、軍援訴求，首先是當時美國的東南亞政策目標所致。魯塞爾·法菲爾德認為，1899—1954年，美國在東南亞的政治經(jīng)濟利益是有限的。美國只是對東南亞的事件做出反應，而不是主動地影響這個地區(qū)的發(fā)展，美國在東南亞的目的以促進各國內(nèi)部穩(wěn)定和集體安全為中心。[35]美國在緬甸的政策目標是，援助緬甸，幫助其實現(xiàn)國內(nèi)的穩(wěn)定和社會經(jīng)濟發(fā)展，倒向美國，防止其成為一個共產(chǎn)黨國家。1954年之前，美國在東南亞區(qū)域和緬甸的政策目標決定其對緬甸的各種援助訴求反應有限。

快速排序采用的是分治思想，即在一個無序的序列中選取一個任意的基準元素pivot（一般為該序列的第一個元素或者中間元素），利用pivot 將待排序的序列分成兩部分，前面部分元素均小于或等于基準元素，后面部分均大于或等于基準元素，然后采用遞歸的方法分別對前后兩部分重復上述操作，直到將無序序列排列成有序序列。

假設(shè)有一待排序序列R，設(shè)數(shù)據(jù)元素序列最低為first,最高位為last，其中first＜=last，則該序列可以將數(shù)據(jù)元素存儲在R[first]～R[last]中。選取第一個元素作為基準元素 即pivot=R[first],設(shè)置區(qū)域劃分令i=first,j=last。開始右側(cè)遍歷，找到小于等于pivot的數(shù)，如果找到R[i]和R[j]交換，i++;開始左側(cè)遍歷，找到大于pivot 的數(shù)，如果找到R[i]和R[j]交換，j--。重復執(zhí)行上述操作，直到i與j重合，返回該位置的數(shù)正好是基準元素pivot 元素。經(jīng)典快速排序的算法如圖4。

圖4 經(jīng)典快速排序算法

經(jīng)典快速排序算法由于每次總是固定選取第一個元素作為基準元素，這樣會導致每次依據(jù)基準元素劃分出來的兩個序列極其的不平衡，尤其對于完全有序序列，快速排序每趟結(jié)束后，基準元素pivot 處于邊緣，形成一個為空，一個只比上次少一個元素的子序列，最終使得快速排序算法退化為冒泡算法。為了避免這種情況的發(fā)生，對經(jīng)典排序算法做了一定的改進，目前常用的有以下三種方法。

隨機選擇法即在序列的下標第一位first和最后一位last之間的所有元素中隨機選取一位元素作為基準元素pivot。這種方法最大限度地避免了選到序列中最大或最小元素作為基準元素，但由于隨機選取，這與排序數(shù)據(jù)的分布和運氣有關(guān)，不易控制。

三數(shù)取中法即取序列的下標第一位first、最后一位last及下標為(first + last)/2這三元素的中間值作為基準元素pivot。由于此法取到的中值不是最值，雖然不能保證每次劃分的完全平衡，但基本上避免了出現(xiàn)極度不平衡。

還有一種不常用的九數(shù)取中法即從序列中分3次隨機取樣，每次取樣3個，從每次取樣的3個中選取中間數(shù)，然后再從這3個中間數(shù)中取出中間數(shù)作為基準元素pivot。這種取法大概率能保證每次劃分的平衡，但由于多次使用隨機函數(shù)增加系統(tǒng)開銷。

3 兩種交換排序算法的比較

排序算法的性能取決于算法中比較和交換的次數(shù)以及是否需要額外的空間用于存放臨時值，也就是算法的時間復雜度和空間復雜度。

冒泡排序算法的時間復雜度由執(zhí)行排序過程中的遍歷數(shù)決定，即外循環(huán)和內(nèi)循環(huán)以及判斷和交換元素的時間開銷。最優(yōu)的情況是排序序列為正序序列，只需要遍歷不需要數(shù)據(jù)交換，正常的比較次數(shù)為[n*(n- 1) ]2,則時間復雜度為O(n2),但優(yōu)化后的冒泡排序設(shè)置了標志位來判斷是否排序好，則此時只需要進行n- 1 次比較，則時間復雜度為O(n)。反之如果排序序列為反序序列，每一次都要交換兩個元素，時間花費為[3*n*(n- 1) ]2 ,則時間復雜度為O(n2),由于在冒泡排序中涉及交換的操作肯定多，所有冒泡排序的平均時間復雜度為O(n2)。冒泡算法的空間復雜度主要是元素交換過程中所用的臨時變量所占用的空間，如果是正序序列不需要交換數(shù)據(jù)則空間復雜度為0,如逆序則為O(n),平均空間復雜度為O( 1)。

快速排序算法的時間復雜度由執(zhí)行的遞歸算法的復雜度決定，即遞歸深度決定。最優(yōu)的情況是基準元素pivot 每一次劃分后，左右兩側(cè)的序列長度相同，此時采用遞歸算法的時間復雜度計算公式為：T[n]=2T[n2 ]+f(n),其中T[n2 ]為平分后序列的時間復雜度，f[n]為平分這個序列所花的時間。采用迭代法依此推算，平分到最后不能再平分，已迭代完得到了T[n/(2m)]=T[1] (T[1]為常量）即n= 2m，計算得到T[n]= 2(logn)T[1]+mn=nT[1]+nlogn。最后得出最優(yōu)時間復雜度為O(nlogn)。最差的情況是基準元素pivot是序列中最大或最小的元素，這種情況就是冒泡排序了，時間復雜度為O(n2) 。正常的情況下基準元素pivot是待排序序列中的記錄，快速排序的平均時間復雜度也是O(nlogn)?？焖倥判虻目臻g復雜度比較復雜，主要為遞歸調(diào)用消耗的空間，最優(yōu)情況即每次都平分的情況下為O(logn)，最差情況即退化為冒泡排序的情況下為O(n) 。排序算法的穩(wěn)定性主要在排序比較過程中，關(guān)鍵字相同的兩個元素之間是否發(fā)生交換。判斷排序算法穩(wěn)定性的方法很簡單，即排序在相鄰的兩個元素之間進行，就不可能發(fā)生相同元素的交換，這個算法就是穩(wěn)定的，如果是間隔的排序，就會發(fā)生交換，這個算法就是不穩(wěn)定的。根據(jù)前面冒泡排序和快速排序的算法排序思想，可以判斷冒泡排序的穩(wěn)定性是穩(wěn)定的，快速排序的穩(wěn)定性是不穩(wěn)定的。

綜上分析冒泡排序及快速排序兩種算法的時間復雜度、空間復雜度和穩(wěn)定性比較如表1所示。

表1 算法的復雜度及穩(wěn)定性

綜上對冒泡排序和快速排序的分析，不難發(fā)現(xiàn)冒泡排序算法作為基本交換排序算法易懂，原理簡單易學，成為很多初學排序人員的入門排序算法。但由于使用雙重循環(huán)，時間復雜度較高，對于大數(shù)據(jù)量處理實用價值不大?？焖倥判蜃鳛槊芭菖判虻母倪M和優(yōu)化，結(jié)合了分治與遞歸的思想，也極易理解，運行也比冒泡快，但它的不穩(wěn)定性也帶來一定的限制。

4 結(jié)束語

本文對交換排序中冒泡排序和快速排序進行了研究比較，闡述了兩種排序算法的基本思想和執(zhí)行過程，并對兩種算法的時間復雜度、空間復雜度和穩(wěn)定性做了比較，為程序開發(fā)者選擇交換排序算法提供一定參考。在實際運用中，針對冒泡排序和快速排序兩種排序算法的選擇，要根據(jù)排序序列的具體情況具體分析，數(shù)據(jù)量增大時，快速排序比冒泡排序效率高出很多，如果數(shù)據(jù)規(guī)模較小，兩者效率相差不大。