陳思敏

（武漢科技大學(xué) 湖北 武漢 430081）

排序算法（Sorting algorithm）就是以一組記錄中的某個或某些關(guān)鍵字的大小為依據(jù)，按照一定的排列方式將這組記錄有序的排列出來的相應(yīng)方法。隨著科技的不斷發(fā)展，計算機的應(yīng)用領(lǐng)域越來越廣，但由于計算機硬件的速度和存儲空間的有限性，如何提高計算機速度并節(jié)省存儲空問一直成為軟件編制人員努力的方向[1]。排序方法選擇得當(dāng)與否直接影響程序執(zhí)行的速度和輔助存儲空間的占用量，進而影響整個軟件的性能。

1 排序的概念

在實際中，待排序的序列很少是單個的值，它們通常都是某個記錄的一部分，每個記錄都有一個關(guān)鍵字key，它是排序的根據(jù)。我們通過對這個關(guān)鍵字key進行排序，然后確定每個記錄的排列方式，使其成為一個有序的記錄。

假設(shè)待排序的n個記錄為：{R1，R2，……，Rn}

其相應(yīng)的關(guān)鍵字序列為：

{K1，K2，……，Kn}

排序要做的就是對關(guān)鍵字序列進行重新排列使其滿足某一遞增或遞減關(guān)系，從而使得其對應(yīng)的記錄成為一組有序的序列[2]。

2 常用排序算法

2.1 冒泡排序法

冒泡排序（BubbleSort）的基本概念：依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序[3]。

按照上述定義，很容易寫出冒泡排序的核心代碼，以C語言作為示例如下：

冒泡排序是通過n－1趟子排序過程完成的，第i趟子排序從第1個數(shù)至第n－i個數(shù)，若第i個數(shù)比后一個數(shù)打，則交換兩數(shù)。不難知道冒泡排序的效率是低下的，它的時間復(fù)雜度為O（n2），不及堆排序或者快速排序的O（n lon2n），但是它的優(yōu)點也是很明顯的，冒泡排序的代碼很容易編寫，而且具有穩(wěn)定性[4]。綜上所述，只有在少數(shù)數(shù)據(jù)規(guī)模比較小的排序中，才用到該種算法。

2.2 快速排序算法

快速排序（QuickSort）算法的是對冒泡排序的一種改進。其基本思想是：先在序列中設(shè)置一個基準(zhǔn)數(shù)，然后通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

快速排序算法的C語言核心代碼如下：

在平均情況下該算法的時間復(fù)雜度為O（n log2n），在最壞的情況下為O（n2）。實際上，快速排序算法比一些時間復(fù)雜度為O（n log2n）的算法要更快一些[5]，因為在大多數(shù)架構(gòu)下其內(nèi)部循環(huán)的實現(xiàn)是高效的。快速排序適合在被排序的序列基本無序的情況下使用。

2.3 插入排序算法

插入排序（InsertionSort）算法的工作原理非常簡單，是通過構(gòu)建一個有序的序列，對于未排序的數(shù)據(jù)，在已排序的序列中從后向前掃描，找到相應(yīng)的位置，然后插入該數(shù)據(jù)，使得新得到的序列依然有序。

插入排序的C語言核心代碼如下：

插入排序在最好的情況下，即待排序數(shù)據(jù)已經(jīng)是升序排列了，在這種情況下需要進行比較的次數(shù)是（n－1）次，在最壞的情況即待排序數(shù)據(jù)位降序排列的時候，需要進行比較的次數(shù)為n（n－1）/2次，平均來說，排序算法的復(fù)雜度為O（n2）。所以插入排序不適合數(shù)據(jù)量比較大的排序應(yīng)用。對于需要排序的數(shù)據(jù)量比較小的時候，插入排序是一個不錯的選擇。

2.4 歸并排序

歸并排序（MergeSort）是將兩個或兩個以上的有序數(shù)列合并成一個新的有序數(shù)列的方法，即將多個有序的數(shù)列合并成一個新的有序數(shù)列的方法。在實際處理排序問題時，我們可以將一個待排序數(shù)列分成兩個或多個待排序的子數(shù)列，將這些子序列分別排序之后，再將這些有序的子序列合并為整體的一個有序序列。

歸并排序需要進行比較操作的次數(shù)介于n log2n/2和n log2n－n+1之間，其算法復(fù)雜度為O（n log2n）[6]。歸并排序的速度僅次于快速排序，一般針對總體無序，但是各子序列有序的情況下使用。

3 結(jié)束語

文中就幾種常用的排序方法，從算法的基本思想，到其C語言實現(xiàn)代碼，以及算法的時間復(fù)雜度和適用情況進行了分析說明。當(dāng)然，排序算法的種類遠(yuǎn)不止此幾種，沒有最好的算法，只有最合適的。在實際應(yīng)用中，應(yīng)根據(jù)不同的情況，選擇合適的排序算法。

[1]潘金貴，顧鐵成，曾檢，等.現(xiàn)代計算機常用數(shù)據(jù)結(jié)構(gòu)和算法[M].南京：南京大學(xué)出版社，1994.

[2]譚浩強.C程序設(shè)計[M].北京：清華大學(xué)出版社，2005

[3]范興福.C語言程序設(shè)計[M].北京：機械工業(yè)出版社，2008.

[4]宋美英.基于C語言的冒泡排序算法探討[J].現(xiàn)代計算機，TANG Yan-qin，LI Qing，LI Wei-wei.The discussion of 2011（23）：37－39.sorting algorithm[J].Modern Computer，2010（12）：64－66.SONG Mei-ying.The discussion of bubble sorting algorithm

[5]唐艷琴，李清，李衛(wèi)衛(wèi).排序算法探討[J].現(xiàn)代計算機，WANG Li.The comparison and choice of commonly used 2010（12）：64－66.internal sorting algorithm[J].Software Guide，2006（12）：45－46.

[6]王莉.常用內(nèi)部排序算法的比較與選擇[J].軟件導(dǎo)刊，based on Clanguage[J].Modern Computer，2011（23）：37－39.2006（1）：45－46.