李家宏，孫慶英

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

0 引言

1 排序的定義及分類(lèi)

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

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

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

圖1 常用排序算法分類(lèi)

由于排序的類(lèi)別較多，各種排序的原理原則不盡相同，本文主要以交換排序?yàn)槔齺?lái)簡(jiǎn)單分析一下排序算法。

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

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

2.1 冒泡排序

冒泡排序就是在排序交換過(guò)程中，類(lèi)似水冒泡。較大的數(shù)往下沉、較小的數(shù)類(lèi)似氣泡一樣往上冒，小（大）的元素?cái)?shù)據(jù)經(jīng)過(guò)不斷的交換，整個(gè)過(guò)程就像冒泡一樣，最小值元素一直往上“冒泡”，所以稱(chēng)為冒泡排序(Bubble Sort) 。

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

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

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

圖3 改進(jìn)冒泡排序算法

2.2 快速排序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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