基于C語言的幾種排序算法的分析

陳思敏

（武漢科技大學 湖北 武漢 430081）

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

1 排序的概念

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

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

其相應的關鍵字序列為：

{K1，K2，……，Kn}

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

2 常用排序算法

2.1 冒泡排序法

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

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

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

2.2 快速排序算法

快速排序（QuickSort）算法的是對冒泡排序的一種改進。其基本思想是：先在序列中設置一個基準數，然后通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

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

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

2.3 插入排序算法

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

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

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

2.4 歸并排序

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

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

3 結束語

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

[1]潘金貴，顧鐵成，曾檢，等.現代計算機常用數據結構和算法[M].南京：南京大學出版社，1994.

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

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

[4]宋美英.基于C語言的冒泡排序算法探討[J].現代計算機，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]唐艷琴，李清，李衛衛.排序算法探討[J].現代計算機，WANG Li.The comparison and choice of commonly used 2010（12）：64－66.internal sorting algorithm[J].Software Guide，2006（12）：45－46.

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