論排序算法的效率

李明達 何麗麗

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

[關鍵詞] 排序算法；程序設計；冒泡法；插入法；快速法

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

[中圖分類號] TP301.6 [文獻標識碼] A [文章編號] 1673 - 0194（2018）05- 0162- 03

0 引 言

在計算機程序設計中，排序算法是一種被廣泛用于解決實際問題的重要方法。排序的目的在于幫助程序設計者提高查找、插入和刪除的效率，使編程過程變得相對簡單化和便捷化。隨著當前計算機及網絡技術的高度發展，以及計算機程序在各個應用領域的大力推廣，基于計算機硬件存儲空間和運行速度的局限性，進一步突出了提高計算機運行速度和節省存儲空間的重要性，因此它也成為今后軟件設計人員共同努力和追求的方向。如何解決上述問題，其視角和思路并不唯一，但目前程序設計人員已將排序算法視為一個重要的因素，因為我們所選擇的排序算法將直接影響程序的執行效率和它對計算機硬件存儲空間的占用額，不僅決定了整個軟件的綜合性能，還會影響整個計算機系統的運行效率。

所謂排序算法，即通過特定的算法因式將一組或多組數據按照既定模式進行重新排序，這種新序列遵循著一定的規則，體現出一定的規律，因此，經處理后的數據便于篩選和計算，大大提高了計算效率。對于排序，我們首先要求其具有一定的穩定性，即當兩個相同的元素同時出現在某個序列之中，則經過一定的排序算法之后，兩者在排序前后的相對位置不發生變化。換言之，即便是兩個完全相同的元素，它們在排序過程中也是各有區別的，不允許混淆不清。

1 計算機程序設計中常見的排序算法

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

1.1 計算機程序設計中的冒泡排序算法

冒泡排序算法是把較小的元素往前調或者把較大的元素往后調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重復進行上述計算，直至完成第（n-1）個和第n個記錄的關鍵字之間的比較；此后，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也說明冒泡排序是一種嚴格的穩定排序算法，它不改變序列中相同元素之間的相對位置關系。

1.2 計算機程序設計中的選擇排序算法

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

1.3 計算機程序設計中的插入排序算法

插入排序算法是基于某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大于該最大元素，則可直接插入最大元素的后面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插入的元素放在該相等元素的后面，因此插入該元素后并未改變原序列的前后順序，我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。

1.4 計算機程序設計中的歸并排序算法

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

1.5 計算機程序設計中的快速排序算法

快速排序算法的基本思想是通過分解、求解和合并這3個主要步驟來計算和排序。具體而言，當我們要對一個序列R進行排序時：第一步要先分解，即在R中任選一個記錄作為基準，以此基準為界將R一分為二，即左、右兩個子區間，前者中的記錄均小于基準，后者中的記錄均大于基準；第二步要求解，即對這兩個區間快速排序；第三步就是合并，對上述兩個分別完成排序的子區間進行合并，即完成整體的排序。快速排序是一個不穩定的排序算法，不穩定發生在中樞元素和右側子區間元素交換的時刻。

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

對于這些常見排序算法的基本思想和步驟，我們已經明確，每種算法所具有的時間、空間復雜性以及穩定性特征，也應是我們研究其算法效率或性能的一個重要基礎。

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

冒泡排序是一種穩定的排序算法。冒泡排序在最佳情況下只需通過1次排序、（n-1）次比較即可實現，此時的時間復雜度為O（n）；相反，當遇到初始序列為逆序的最差情況時，則需要進行（n-1）次排序、（n-1）n/2次比較才能完成，此時的時間復雜度為O（n2）；我們假定附加存儲空間為O（1）。

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

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

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

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

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

歸并排序也是一種穩定的排序算法。選用歸并排序算法對n個記錄進行排序計算，假設其計算時間為T（n），則最佳情況下，T（n）=O（1），且 n≤1；而最差的情況下，T（n）=O（nlogn）；附加存儲空間為O（n）。

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

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

3 排序算法的效率分析

對于各種排序算法的性能或效率的評價，一直以來都是備受關注的一個話題。為了比較上述各種常見排序算法的效率，我們要設定一個相同的運算環境，比如在VS6.0環境下進行C語言編程測試，調用時間函數和隨機函數來對輸入不同規模和排序元素時，各種排序算法的運行狀況。

首先，我們通過改變輸入元素的規模，對各種排序算法的時間消耗上進行分析。當輸入規模相對較小時，上述算法消耗的時間基本上一致，差距甚小；隨著輸入規模的逐步增大，其時間差距越來越明顯，其中以快速算法最具優勢，其次是歸并排序，而選擇排序耗時最多，因此其時間效率也是最低的。其次，我們通過調整輸入順序來研究各種排序算法的時間消耗。正序時，插入排序算法優勢最明顯——不消耗時間，而下面則是歸并排序法、快速排序法和冒泡排序法，而選擇排序耗時最多，因此時間效率最高；逆序時，歸并排序法成為最理想的計算方法，下面是快速排序法和插入排序法，而冒泡排序法和選擇排序法則相對不具有優勢。經過比較我們發現，當規模不斷增加時，各種算法之間的差別是很大的。我們對排序算法進行評價的標準主要參照執行時間、輔助空間和算法穩定性這三個方面。對上述幾種排序算法的相關參數記錄如下。

據此，我們可按照平均時間復雜度把上述五種排序算法分為2類，一類是時間復雜度為O（n2）的冒泡排序、選擇排序和插入排序，其時間復雜度均為平方階排序；一類是時間復雜度為O（nlogn）的歸并排序和快速排序，其時間復雜度均為線性對數階排序。單從平均時間的性能分析，快速排序和歸并排序明顯優于其他三種排序算法，但是，在最差的情況下，快速排序則不如歸并排序；在輸入規模較大時，歸并排序又不如快速排序；在輸入規模較小時，所有算法的效率相差無幾。我們再來看空間方面，快速排序和歸并排序對空間的占用較大，而前三種則耗用較小的空間。

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

4 結 語

排序算法目前已經涉及計算機程序設計、操作系統、編譯原理、數據庫以及人工智能等諸多重要領域，且已經被廣泛應用于信息學和系統工程。我們學習和研究排序算法的目的在于為今后更好地用計算機語言來解決和處理實際問題。

主要參考文獻

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

[2]楊波，肖自碧.信息與計算科學專業“算法分析與設計”研究性教學探索[J].中國電力教育，2013（1）：62-63.

[3]邵順增.穩定快速排序算法研究[J].計算機應用與軟件，2014，31（7）：263-266.