五種排序算法的分析與比較

五種排序算法的分析與比較廣東醫(yī)學(xué)院醫(yī)學(xué)信息專業(yè)郭慧玲摘要：排序算法是計算機程序設(shè)計廣泛使用的解決問題的方法,研究排序算法具有重要的理論意義和廣泛的應(yīng)用價值。文章通過描述冒泡、選擇、插入、歸并和快速5種排序算法,總結(jié)了它們的時間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。通過實驗驗證了5種排序算法在隨機、正序和逆序3種情況下的性能,指出排序算法的適用原則,以供在不同條件下選擇適合的排序算法借鑒。關(guān)鍵詞：冒泡排序;選擇排序;插入排序;歸并排序;快速排序。排序是計算機科學(xué)中基本的研究課題之一,其目的是方便記錄的查找、插入和刪除。隨著計算機的發(fā)展與應(yīng)用領(lǐng)域的越來越廣,基于計算機硬件的速度和存儲空間的有限性,如何提高計算機速度并節(jié)省存儲空間一直成為軟件設(shè)計人員的努力方向。其中,排序算法已成為程序設(shè)計人員考慮的因素之一[1]，排序算法選擇得當(dāng)與否直接影響程序的執(zhí)行效率和內(nèi)外存儲空間的占用量,甚至影響整個軟件的綜合性能。排序操作[2，3],就是將一組數(shù)據(jù)記錄的任意序列,重新排列成一個按關(guān)鍵字有序的序列。而所謂排序的穩(wěn)定性是指如果在排序的序列中，存在前后相同的兩個元素，排序前和排序后他們的相對位臵不發(fā)生變化。1算法與特性冒泡排序冒泡排序的基本思想冒泡排序的基本思想是[5,6]:首先將第1個記錄的關(guān)鍵字和第2個記錄的關(guān)鍵字進行比較,若為逆序,則將2個記錄交換,然后比較第2個和第3個記錄的關(guān)鍵字，依次類推，直至n-1個記錄和第n個記錄的關(guān)鍵字進行過比較為止。然后再按照上述過程進行下一次排序,直至整個序列有序為止。冒泡排序的特性容易判斷冒泡排序是穩(wěn)定的。可以分析出它的效率,在最好情況下,只需通過n-1次比較，不需要移動關(guān)鍵字，即時間復(fù)雜度為O(n)(即正序);在最壞情況下是初始序列為逆序，則需要進行n-1次排序,需進行n(n-1)/2次比較，因此在最壞情況下時間復(fù)雜度為O(n2),附加存儲空間為O(1)。選擇排序選擇排序的基本思想選擇排序的基本思想是[5,6] :每一次從待排序的記錄中選出關(guān)鍵字最小的記錄,順序放在已排好序的文件的最后,直到全部記錄排序完畢.常用的選擇排序方法有直接選擇排序和堆排序,考慮到簡單和易理解,這里討論直接選擇排序。直接選擇排序的基本思想是n個記錄的文件的直接排序可經(jīng)過n-1次直接選擇排序得到有序結(jié)果。選擇排序的特性容易得出選擇排序是不穩(wěn)定的。在直接選擇排序過程中所需進行記錄移動的操作次數(shù)最少為0,最大值為3(n-1)。然而,無論記錄的初始排序如何，所需進行的關(guān)鍵字間的比較次數(shù)相同，均為n(n-1)/2,時間復(fù)雜度為O(n2),附加存儲空間為O(1)。插入排序插入排序的基本思想插入排序的基本思想是[5,6]:每次將1個待排序的記錄按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中適當(dāng)?shù)奈慌Z,直到全部記錄插入完成為止。插入排序分直接插入排序、折半插入排序和希爾排序3類?？紤]到簡單、易理解的因素,這里討論直接插入排序,其基本思想是:初始時R[0]自成一個有序區(qū),無序區(qū)為R[1,…,n-1],從1=1至1二n-1為止,依次將R[1]插入到當(dāng)前的有序區(qū)中，生成含n個記錄的有序區(qū)。容易得出插入排序是穩(wěn)定的。插入排序的特性當(dāng)待排序文件為正序時,所需進行的關(guān)鍵字間比較的次數(shù)達最小值n-1,記錄不需要移動;反之,逆序時比較次數(shù)達最大值(n+2)(n-1)/2,移動次數(shù)為(n+4)(n-1)/2,因此，其時間復(fù)雜度為O(n2),附加存儲空間為O(1)。歸并排序歸并排序的基本思想歸并排序的基本思想是[7,8] :采用分治策略,將待排序文件分成大小大致相同的2個子集合,分別對2個子集合進行排序,最終將排好序的子集合并成所要求的排好序的集合。假設(shè)初始序列含有n個記錄 ，則可以將每個記錄看成是長度為1的子序列,然后兩兩歸并，得到對n/2個長度為2或1的有序子序列;再兩兩歸并,如此重復(fù),直至得到1個長度為n的有序序列為止。歸并排序的特性容易得出歸并排序穩(wěn)定。歸并排序算法對n個待排序記錄進行排序在最壞的情況下所需的計算時間T (n)滿足：nW1,T(n)=O(1);otherwise,T(n)=O(nlogn)。附加存儲空間為O(n)?？焖倥判蚩焖倥判虻幕舅枷肟焖倥判虻幕舅枷胧荹7,9] ：具體過程如下,假設(shè)當(dāng)前待排序序列為R[low,…，high],排序過程分為分解、求解和合并3個步驟：①分解,在R[low,…,high]中任選一個記錄作為基準(zhǔn)(base),以此基準(zhǔn)將當(dāng)前待排序序列分為左、右2個子區(qū)間，前者為R[low,…，base-1],均小于基準(zhǔn),后者為R[base+1,…,high],均大于基準(zhǔn)，基準(zhǔn)則處于正確的位臵上；②求解，通過遞歸調(diào)用快速排序?qū)ψ蟆⒂?2個子區(qū)間進行快速排序;③合并，當(dāng)求解中的2個遞歸調(diào)用結(jié)束時，左、右2個子區(qū)間已有序，即完成排序。 需附加存儲空間為O(log2n).容易得出快速排序不穩(wěn)定?？焖倥判虻奶匦愿鶕?jù)對此排序的描述,可以分2種情況討論：1)當(dāng)待排序序列有序(序列按正序排列)時,每次劃分只得到1個比上一次少1個記錄的子序列。這樣，必須經(jīng)過n-1次才能把所有記錄定位,而且第i次需要n-i次比較才能找到第i個記錄的正確位臵,故總的比較次數(shù)達到1/2*n(n-1)=O(n2)。2)當(dāng)排序序列是隨機序列時，且T(n)是對n個記錄的序列進行排序所需的時間，每次對1個記錄正確定位后，正好把序列劃分為長度相等的2個子序列，此時T(n)滿足nW1,T(n)=O(1);otherwise,T(n)=O(nlogn)。2性能評價實驗與結(jié)果為了比較各種排序算法的性能，我們使用一臺桌面電腦，在VS6.0環(huán)境下，用C語言編寫程序，調(diào)用隨機函數(shù)、時間函數(shù)來統(tǒng)計輸入規(guī)模不同和排序不同的元素時五種排序算法的用時情況。以下實驗結(jié)果引用于:五種排序算法的性能分析表1不同規(guī)模卜5種排序算法的耗時表規(guī)模/個排序算法耗時/$冒泡選擇插入歸并快速1000(1015(1()00Q016(10000,()002000Cl016(1032Q015(100000004000Q063(1109Q062(1015U000X()00(1203(1469(1219Q031(1()(}()10000(1328(1734Q266(1046{).()0020000L2K129221.265Q265(10154000047651L734SS43L515a016800001&18847.20319.407(\859{).03】由表1可知：當(dāng)輸入規(guī)模為10000時,5種排序算法的用時情況差不多，但隨著輸入規(guī)模的增大，快速排序算法的優(yōu)勢就體現(xiàn)出來，其次是歸

并排序,最差的是選擇排序，插入排序略優(yōu)于冒泡排序表2止序輸入時5種排序并法的耗時表排序算法耗時/s規(guī)模/個 冒泡選擇插入歸并快速100()(100()Q000ft000(X000(10()02000(JL016<103200000000a0154000(JL047(1110aooo(k015a063X00()(1284(1469(X{}{)()(h()31(121910000a328(17340000(X046a328由表2可知：當(dāng)輸入序列是正序時，插入排序算法最佳，其次是歸并排序,快速排序略優(yōu)于冒泡排序，最差的是選擇排序。表3逆序輸入時5種排序并法的耗時農(nóng)排序算法耗時/$規(guī)模/個 冒泡選擇插入歸并快速1000(1000(I016(1ooo(100()0.ooo200(*(1032(1031(1031(1()0()a016400()(k125(1125(1()62a015a047K000(1437(1485a281(i015a28310000(1703(1766a438a0310.328由表3可知:當(dāng)輸入序列是逆序時，歸并排序算法是最理想的，最壞的是選擇排序；輸入規(guī)模在8000個記錄范圍內(nèi)時，插入排序和快速排序差不多，隨著輸入規(guī)模的增大，快速排序比插入排序耗時更少；輸入規(guī)模在4000個記錄范圍內(nèi)時，冒泡排序和選擇排序幾乎一樣，差別極其微小,隨著規(guī)模增大，冒泡排序優(yōu)于選擇排序。算法性能評價評價排序算法好壞的標(biāo)準(zhǔn)主要有3條［11］:執(zhí)行時間、所需的輔助空間以及算法的穩(wěn)定性。算法本身的復(fù)雜程度 ，即空間復(fù)雜度和時間復(fù)雜度。如果所需的輔助空間并不依賴于問題的規(guī)模，即輔助空間是O(1),稱之為就地排序；非就地排序一般要求的輔助空間為O(n)。然而,時間復(fù)雜度［12］取決于算法本身涉及的記錄之間的比較次數(shù)和交換次數(shù)?？偨Y(jié)排序算法比較(表4)排序方法平均時間復(fù)雜度最壞情況空間復(fù)雜度穩(wěn)定性冒泡排序O(n2)0(n2)0(1)穩(wěn)定選擇排序O(n2)0(n2)0(1)不穩(wěn)定插入排序O(n2)0(n2)0(1)穩(wěn)定歸并排序0(nlogn)0(nlogn)0(n)穩(wěn)定快速排序0(nlogn)0(n2)O(log2n)不穩(wěn)定綜合比較上述討論的幾種內(nèi)部排序算法，可得到如表4所示的結(jié)論。根據(jù)表4,可以將5種排序算法按照平均時間分為2類:冒泡排序、選擇排序、插入排序其時間復(fù)雜度為O(n2),即平方階排序；歸并排序、快速排序其時間復(fù)雜度為O(nlogn),即線性對數(shù)階排序。從平均時間性能而言，快速排序和歸并排序優(yōu)越于其他3種排序,所需時間最省，但在最壞情況下，快速排序則不如歸并排序。在輸入規(guī)模較大時，快速排序比較有優(yōu)勢，但當(dāng)輸入規(guī)模不是很大時,5種排序算法的耗時相差無幾。就空間復(fù)雜度而言，快速和歸并排序的輔助空間開銷比較大 ，冒泡、選擇、插入排序輔助空間開銷比較少。根據(jù)以上實驗結(jié)果,可得出結(jié)論:當(dāng)記錄較小,基本有序，要求穩(wěn)定時，則采用直接插入排序；若記錄較小，分布隨機，穩(wěn)定性不做要求時，則采用直接選擇排序；若記錄較大，內(nèi)存允許，要求排序穩(wěn)定時，則采用歸并排序。所以在選擇合適的排序算法時,應(yīng)該考慮到算法本身的時間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性等.其具體的用法應(yīng)根據(jù)應(yīng)用環(huán)境而定,側(cè)重點不同,則選擇的排序方法也各異。參考文獻王德超.常用排序算法的分析與比較.現(xiàn)代計算機,2012,6(1):36-40.張銘,趙海燕,王騰蛟等.北京大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》教學(xué)設(shè)計[J],計算機教育,2008,11(20):64-68.葛建梅.《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)方法改革的思考[J]，中國成人教育,2008,9(1)，51-55.范策,周世平,胡嘵琨等.數(shù)據(jù)結(jié)構(gòu)(C語言版).機械工業(yè)出版社，2004，8(4):81-93.嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京清華大學(xué)出版社,1997:263-289.⑹曹衍龍，林瑞仲，徐慧.C語言實例解析[M].北京人民郵電出版社,2007:94-117.王曉東.計算機算法設(shè)計與分析[M].北京電子工業(yè)出版社,2007:21-25.王穎，李肯立,李浪等.縱橫多路