李明達(dá) 何麗麗

[摘 要] 排序算法是計(jì)算機(jī)設(shè)計(jì)中常用的解決問(wèn)題的方法，常見(jiàn)的有冒泡法、選擇法、插入法、歸并法和快速法等。對(duì)于這些排序算法，各自有何種優(yōu)勢(shì)和缺陷？又分別適用于什么情況？搞懂這些問(wèn)題對(duì)于我們進(jìn)行程序設(shè)計(jì)和優(yōu)化都具有十分重要的意義。本文主要通過(guò)對(duì)上述五種排序算法的剖析，分別對(duì)其效率進(jìn)行研究和討論。

[關(guān)鍵詞] 排序算法；程序設(shè)計(jì)；冒泡法；插入法；快速法

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2018. 05. 067

[中圖分類(lèi)號(hào)] TP301.6 [文獻(xiàn)標(biāo)識(shí)碼] A [文章編號(hào)] 1673 - 0194（2018）05- 0162- 03

0 引 言

在計(jì)算機(jī)程序設(shè)計(jì)中，排序算法是一種被廣泛用于解決實(shí)際問(wèn)題的重要方法。排序的目的在于幫助程序設(shè)計(jì)者提高查找、插入和刪除的效率，使編程過(guò)程變得相對(duì)簡(jiǎn)單化和便捷化。隨著當(dāng)前計(jì)算機(jī)及網(wǎng)絡(luò)技術(shù)的高度發(fā)展，以及計(jì)算機(jī)程序在各個(gè)應(yīng)用領(lǐng)域的大力推廣，基于計(jì)算機(jī)硬件存儲(chǔ)空間和運(yùn)行速度的局限性，進(jìn)一步突出了提高計(jì)算機(jī)運(yùn)行速度和節(jié)省存儲(chǔ)空間的重要性，因此它也成為今后軟件設(shè)計(jì)人員共同努力和追求的方向。如何解決上述問(wèn)題，其視角和思路并不唯一，但目前程序設(shè)計(jì)人員已將排序算法視為一個(gè)重要的因素，因?yàn)槲覀兯x擇的排序算法將直接影響程序的執(zhí)行效率和它對(duì)計(jì)算機(jī)硬件存儲(chǔ)空間的占用額，不僅決定了整個(gè)軟件的綜合性能，還會(huì)影響整個(gè)計(jì)算機(jī)系統(tǒng)的運(yùn)行效率。

所謂排序算法，即通過(guò)特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進(jìn)行重新排序，這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計(jì)算，大大提高了計(jì)算效率。對(duì)于排序，我們首先要求其具有一定的穩(wěn)定性，即當(dāng)兩個(gè)相同的元素同時(shí)出現(xiàn)在某個(gè)序列之中，則經(jīng)過(guò)一定的排序算法之后，兩者在排序前后的相對(duì)位置不發(fā)生變化。換言之，即便是兩個(gè)完全相同的元素，它們?cè)谂判蜻^(guò)程中也是各有區(qū)別的，不允許混淆不清。

1 計(jì)算機(jī)程序設(shè)計(jì)中常見(jiàn)的排序算法

目前計(jì)算機(jī)程序設(shè)計(jì)中出現(xiàn)的排序算法已不單一，而是呈現(xiàn)出多樣化的前景，比如有冒泡排序法、選擇排序法、插入排序法、歸并排序法和快速排序法等多種形式。

1.1 計(jì)算機(jī)程序設(shè)計(jì)中的冒泡排序算法

冒泡排序算法是把較小的元素往前調(diào)或者把較大的元素往后調(diào)。這種方法主要是通過(guò)對(duì)相鄰兩個(gè)元素進(jìn)行大小的比較，根據(jù)比較結(jié)果和算法規(guī)則對(duì)該二元素的位置進(jìn)行交換，這樣逐個(gè)依次進(jìn)行比較和交換，就能達(dá)到排序目的。冒泡排序的基本思想是，首先將第1個(gè)和第2個(gè)記錄的關(guān)鍵字比較大小，如果是逆序的，就將這兩個(gè)記錄進(jìn)行交換，再對(duì)第2個(gè)和第3個(gè)記錄的關(guān)鍵字進(jìn)行比較，依次類(lèi)推，重復(fù)進(jìn)行上述計(jì)算，直至完成第（n-1）個(gè)和第n個(gè)記錄的關(guān)鍵字之間的比較；此后，再按照上述過(guò)程進(jìn)行第2次、第3次排序，直至整個(gè)序列有序?yàn)橹?。排序過(guò)程中要特別注意的是，當(dāng)相鄰兩個(gè)元素大小一致時(shí)，這一步操作就不需要交換位置，因此也說(shuō)明冒泡排序是一種嚴(yán)格的穩(wěn)定排序算法，它不改變序列中相同元素之間的相對(duì)位置關(guān)系。

1.2 計(jì)算機(jī)程序設(shè)計(jì)中的選擇排序算法

選擇排序算法的基本思路是為每一個(gè)位置選擇當(dāng)前最小的元素。選擇排序的基本思想是，基于直接選擇排序和堆排序這兩種基本的簡(jiǎn)單排序方法，首先從第1個(gè)位置開(kāi)始對(duì)全部元素進(jìn)行選擇，選出全部元素中最小的給該位置；再對(duì)第2個(gè)位置進(jìn)行選擇，在剩余元素中選擇最小的給該位置即可；以此類(lèi)推，重復(fù)進(jìn)行“最小元素”的選擇，直至完成第（n-1）個(gè)位置的元素選擇，則第n個(gè)位置就只剩唯一的最大元素，此時(shí)不需再進(jìn)行選擇。使用這種排序時(shí)，要注意其中一個(gè)不同于冒泡法的細(xì)節(jié)，舉例說(shuō)明：序列5 8 5 3 9，我們知道第一遍選擇第1個(gè)元素“5”會(huì)和元素“3”交換，那么原序列中的兩個(gè)相同元素“5”之間的前后相對(duì)順序就發(fā)生了改變。因此，我們說(shuō)選擇排序不是穩(wěn)定的排序算法，它在計(jì)算過(guò)程中會(huì)破壞穩(wěn)定性。

1.3 計(jì)算機(jī)程序設(shè)計(jì)中的插入排序算法

插入排序算法是基于某序列已經(jīng)有序排列的情況下，通過(guò)一次插入一個(gè)元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開(kāi)始執(zhí)行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大于該最大元素，則可直接插入最大元素的后面即可，否則再向前一位比較查找直至找到應(yīng)該插入的位置為止。插入排序的基本思想是，每次將1個(gè)待排序的記錄按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中，尋找最適當(dāng)?shù)奈恢?，直至全部記錄插入完畢。?zhí)行過(guò)程中，若遇到和插入元素相等的位置，則將要插入的元素放在該相等元素的后面，因此插入該元素后并未改變?cè)蛄械那昂箜樞?，我們認(rèn)為插入排序也是一種穩(wěn)定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類(lèi)。

1.4 計(jì)算機(jī)程序設(shè)計(jì)中的歸并排序算法

歸并排序算法就是把序列遞歸劃分成為一個(gè)個(gè)短序列，以其中只有1個(gè)元素的直接序列或者只有2個(gè)元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規(guī)則進(jìn)行排序?yàn)殚L(zhǎng)序列。歸并排序融合了分治策略，即將含有n個(gè)記錄的初始序列中的每個(gè)記錄均視為長(zhǎng)度為1的子序列，再將這n個(gè)子序列兩兩合并得到n/2 個(gè)長(zhǎng)度為2（當(dāng)n為奇數(shù)時(shí)會(huì)出現(xiàn)長(zhǎng)度為1的情況）的有序子序列；將上述步驟重復(fù)操作，直至得到1個(gè)長(zhǎng)度為n的有序長(zhǎng)序列。需要注意的是，在進(jìn)行元素比較和交換時(shí)，若兩個(gè)元素大小相等則不必刻意交換位置，因此該算法不會(huì)破壞序列的穩(wěn)定性，即歸并排序也是穩(wěn)定的排序算法。

1.5 計(jì)算機(jī)程序設(shè)計(jì)中的快速排序算法

快速排序算法的基本思想是通過(guò)分解、求解和合并這3個(gè)主要步驟來(lái)計(jì)算和排序。具體而言，當(dāng)我們要對(duì)一個(gè)序列R進(jìn)行排序時(shí)：第一步要先分解，即在R中任選一個(gè)記錄作為基準(zhǔn)，以此基準(zhǔn)為界將R一分為二，即左、右兩個(gè)子區(qū)間，前者中的記錄均小于基準(zhǔn)，后者中的記錄均大于基準(zhǔn)；第二步要求解，即對(duì)這兩個(gè)區(qū)間快速排序；第三步就是合并，對(duì)上述兩個(gè)分別完成排序的子區(qū)間進(jìn)行合并，即完成整體的排序?？焖倥判蚴且粋€(gè)不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和右側(cè)子區(qū)間元素交換的時(shí)刻。

2 排序算法的基本特性分析

對(duì)于這些常見(jiàn)排序算法的基本思想和步驟，我們已經(jīng)明確，每種算法所具有的時(shí)間、空間復(fù)雜性以及穩(wěn)定性特征，也應(yīng)是我們研究其算法效率或性能的一個(gè)重要基礎(chǔ)。

2.1 冒泡排序算法的特性分析

冒泡排序是一種穩(wěn)定的排序算法。冒泡排序在最佳情況下只需通過(guò)1次排序、（n-1）次比較即可實(shí)現(xiàn)，此時(shí)的時(shí)間復(fù)雜度為O（n）；相反，當(dāng)遇到初始序列為逆序的最差情況時(shí)，則需要進(jìn)行（n-1）次排序、（n-1）n/2次比較才能完成，此時(shí)的時(shí)間復(fù)雜度為O（n2）；我們假定附加存儲(chǔ)空間為O（1）。

2.2 選擇排序算法的特性分析

選擇排序是一種不穩(wěn)定的排序算法。選擇排序以直接選擇排序法最為典型，選擇排序過(guò)程中移動(dòng)記錄的操作次數(shù)最少可能為0，最大則為3（n-1）次，而關(guān)鍵字之間的比較次數(shù)均為（n-1）n/2次，時(shí)間復(fù)雜度也是O（n2）；附加存儲(chǔ)空間也是O（1）。

2.3 插入排序算法的特性分析

插入排序也是一種穩(wěn)定的排序算法。為了方便理解，我們以直接插入進(jìn)行探討：當(dāng)所研究的序列為正序時(shí)，需要最少進(jìn)行（n-1）次關(guān)鍵字之間的比較，此時(shí)不需要對(duì)記錄進(jìn)行移動(dòng)操作，時(shí)間復(fù)雜度為O（n）；相反，遇到逆序時(shí)，則對(duì)關(guān)鍵字的比較呈現(xiàn)出最大值（n+2）（n-1）/2次，而對(duì)應(yīng)的記錄移動(dòng)次數(shù)為（n+4）（n-1）/2次，其時(shí)間復(fù)雜度為O（n2），附加存儲(chǔ)空間為O（1）。

2.4 歸并排序算法的特性分析

歸并排序也是一種穩(wěn)定的排序算法。選用歸并排序算法對(duì)n個(gè)記錄進(jìn)行排序計(jì)算，假設(shè)其計(jì)算時(shí)間為T(mén)（n），則最佳情況下，T（n）=O（1），且 n≤1；而最差的情況下，T（n）=O（nlogn）；附加存儲(chǔ)空間為O（n）。

2.5 快速排序算法的特性分析

快速排序主要分2種情況，一種是待排序序列為有序序列，一種是待排序序列為隨機(jī)無(wú)序序列。當(dāng)待排序序列有序時(shí)，每一次劃分將只能得到1個(gè)比上一次少1個(gè)記錄的子序列，因此需要經(jīng)過(guò)（n-1）次才能完成全部計(jì)算，其中第m次需要（n-m）次比較才能準(zhǔn)確找到第m個(gè)記錄的位置，此時(shí)總的比較次數(shù)為1/2n（n-1）=O（n2）。當(dāng)待排序序列是隨機(jī)序列時(shí)，我們假設(shè)對(duì)n個(gè)記錄的序列排序的時(shí)間為T(mén)（n），則每一次正確定位1個(gè)記錄后，該序列恰被劃分為長(zhǎng)度相等的兩個(gè)子序列，此時(shí)T（n）=O（1），且n≤1；相反，則最差的情況下，T（n）=O（n2）；附加存儲(chǔ)空間為O（log2n）。

3 排序算法的效率分析

對(duì)于各種排序算法的性能或效率的評(píng)價(jià)，一直以來(lái)都是備受關(guān)注的一個(gè)話(huà)題。為了比較上述各種常見(jiàn)排序算法的效率，我們要設(shè)定一個(gè)相同的運(yùn)算環(huán)境，比如在VS6.0環(huán)境下進(jìn)行C語(yǔ)言編程測(cè)試，調(diào)用時(shí)間函數(shù)和隨機(jī)函數(shù)來(lái)對(duì)輸入不同規(guī)模和排序元素時(shí)，各種排序算法的運(yùn)行狀況。

首先，我們通過(guò)改變輸入元素的規(guī)模，對(duì)各種排序算法的時(shí)間消耗上進(jìn)行分析。當(dāng)輸入規(guī)模相對(duì)較小時(shí)，上述算法消耗的時(shí)間基本上一致，差距甚??；隨著輸入規(guī)模的逐步增大，其時(shí)間差距越來(lái)越明顯，其中以快速算法最具優(yōu)勢(shì)，其次是歸并排序，而選擇排序耗時(shí)最多，因此其時(shí)間效率也是最低的。其次，我們通過(guò)調(diào)整輸入順序來(lái)研究各種排序算法的時(shí)間消耗。正序時(shí)，插入排序算法優(yōu)勢(shì)最明顯——不消耗時(shí)間，而下面則是歸并排序法、快速排序法和冒泡排序法，而選擇排序耗時(shí)最多，因此時(shí)間效率最高；逆序時(shí)，歸并排序法成為最理想的計(jì)算方法，下面是快速排序法和插入排序法，而冒泡排序法和選擇排序法則相對(duì)不具有優(yōu)勢(shì)。經(jīng)過(guò)比較我們發(fā)現(xiàn)，當(dāng)規(guī)模不斷增加時(shí)，各種算法之間的差別是很大的。我們對(duì)排序算法進(jìn)行評(píng)價(jià)的標(biāo)準(zhǔn)主要參照?qǐng)?zhí)行時(shí)間、輔助空間和算法穩(wěn)定性這三個(gè)方面。對(duì)上述幾種排序算法的相關(guān)參數(shù)記錄如下。

據(jù)此，我們可按照平均時(shí)間復(fù)雜度把上述五種排序算法分為2類(lèi)，一類(lèi)是時(shí)間復(fù)雜度為O（n2）的冒泡排序、選擇排序和插入排序，其時(shí)間復(fù)雜度均為平方階排序；一類(lèi)是時(shí)間復(fù)雜度為O（nlogn）的歸并排序和快速排序，其時(shí)間復(fù)雜度均為線性對(duì)數(shù)階排序。單從平均時(shí)間的性能分析，快速排序和歸并排序明顯優(yōu)于其他三種排序算法，但是，在最差的情況下，快速排序則不如歸并排序；在輸入規(guī)模較大時(shí)，歸并排序又不如快速排序；在輸入規(guī)模較小時(shí)，所有算法的效率相差無(wú)幾。我們?cè)賮?lái)看空間方面，快速排序和歸并排序?qū)臻g的占用較大，而前三種則耗用較小的空間。

綜上所述，這五種算法中，快速排序比較和移動(dòng)次數(shù)最少，效率最高。選擇排序（直接選擇排序）雖然交換次數(shù)很少，但比較次數(shù)較多，因此其效率不如快速排序算法。當(dāng)序列中的記錄較小且基本有序時(shí)，如果要求穩(wěn)定性，則可以采用直接插入的排序算法；當(dāng)序列中的記錄較小且分布隨機(jī)時(shí)，一般不對(duì)穩(wěn)定性做特殊要求，宜采用直接選擇排序的算法；當(dāng)序列中的記錄較大且要求排序穩(wěn)定時(shí)，若內(nèi)存空間允許，一般宜采用歸并排序算法。因此，在選擇具體排序算法時(shí)，必須充分考慮算法本身的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性等特征。

4 結(jié) 語(yǔ)

排序算法目前已經(jīng)涉及計(jì)算機(jī)程序設(shè)計(jì)、操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)以及人工智能等諸多重要領(lǐng)域，且已經(jīng)被廣泛應(yīng)用于信息學(xué)和系統(tǒng)工程。我們學(xué)習(xí)和研究排序算法的目的在于為今后更好地用計(jì)算機(jī)語(yǔ)言來(lái)解決和處理實(shí)際問(wèn)題。

主要參考文獻(xiàn)

[1]湯亞玲，秦鋒.高效快速排序算法研究[J]. 計(jì)算機(jī)工程，2011，37（6）：77-78.

[2]楊波，肖自碧.信息與計(jì)算科學(xué)專(zhuān)業(yè)“算法分析與設(shè)計(jì)”研究性教學(xué)探索[J].中國(guó)電力教育，2013（1）：62-63.

[3]邵順增.穩(wěn)定快速排序算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（7）：263-266.