四種簡單的排序算法

我覺得如果想成為一名優秀的開發者，不僅要積極學習時下流行的新技術，比如WCF、Asp.Net MVC、AJAX等，熟練應用一些已經比較成熟的技術，比如Asp.Net、WinForm。還應該有著牢固的計算機基礎知識，比如數據結構、操作系統、編譯原理、網絡與數據通信等。有的朋友可能覺得這方面的東西過于艱深和理論化，望而卻步，但我覺得假日里花上一個下午的時間，研究一種算法或者一種數據結構，然后寫寫心得，難道不是一件樂事么？所以，我打算將一些常見的數據結構和算法總結一下，不一定要集中一段時間花費很大精力，只是在比較空閑的時間用一種很放松的心態去完成。我最不愿意的，就是將寫博客或者是學習技術變為一項工作或者負擔，應該將它們視為生活中的一種消遣。人們總是說堅持不易，實際上當你提到“堅持”兩個字之時，說明你已經將這件事視為了一種痛苦，你的內心深處并不愿意做這件事，所以才需要堅持。你從不曾聽人說“我堅持玩了十年的電子游戲”，或者“堅持看了十年動漫、電影”、“堅持和心愛的女友相處了十年”吧？我從來不曾堅持，因為我將其視為一個愛好和消遣，就像許多人玩網絡游戲一樣。

好了，閑話就說這么多吧，我們回到正題。因為這方面的著作很多，所以這里只給出簡單的描述和實現，供我本人及感興趣的朋友參考。我會盡量用C#和C++兩種語言實現，對于一些不好用C#表達的結構，僅用C++實現。

本文將描述四種最簡單的排序方法，插入排序、泡沫排序、選擇排序、希爾排序，我在這里將其稱為“簡單排序”，是因為它們相對于快速排序、歸并排序、堆排序、分配排序、基數排序從理解和算法上要簡單一些。對于后面這幾種排序，我將其稱為“高級排序”。

簡單排序

開始之前先聲明一個約定，對于數組中保存的數據，統一稱為記錄，以避免和“元素”，“對象”等名稱相混淆。對于一個記錄，用于排序的碼，稱為關鍵碼。很顯然，關鍵碼的選擇與數組中記錄的類型密切相關，如果記錄為int值，則關鍵碼就是本身；如果記錄是自定義對象，它很可能包含了多個字段，那么選定這些字段之一為關鍵碼。凡是有關排序和查找的算法，就會關系到兩個記錄比較大小，而如何決定兩個對象的大小，應該由算法程序的客戶端（客戶對象）決定。對于.NET來說，我們可以創建一個實現了IComparer<T>的類（對于C++也是類似）。關于IComparer<T>的更多信息，可以參考這篇文章《基于業務對象的排序》。最后，為了使程序簡單，對于數組為空的情況我并沒有做處理。

1.插入排序

算法思想

插入排序使用了兩層嵌套循環，逐個處理待排序的記錄。每個記錄與前面已經排好序的記錄序列進行比較，并將其插入到合適的位置。假設數組長度為n，外層循環控制變量i由1至n-1依次遞進，用于選擇當前處理哪條記錄；里層循環控制變量j，初始值為i，并由i至1遞減，與上一記錄進行對比，決定將該元素插入到哪一個位置。這里的關鍵思想是，當處理第i條記錄時，前面i-1條記錄已經是有序的了。需要注意的是，因為是將當前記錄與相鄰的上一記錄相比較，所以循環控制變量的起始值為1（數組下標），如果為0的話，上一記錄為-1，則數組越界。

現在我們考察一下第i條記錄的處理情況：假設外層循環遞進到第i條記錄，設其關鍵碼的值為X，那么此時有可能有兩種情況：

如果上一記錄比X大，那么就交換它們，直到上一記錄的關鍵碼比X小或者相等為止。
如果上一記錄比X小或者相等，那么之前的所有記錄一定是有序的，且都比X小，此時退出里層循環。外層循環向前遞進，處理下一條記錄。

算法實現(C#)

public class SortAlgorithm {
??? // 插入排序
??? public static void InsertSort<T, C>(T[] array, C comparer)
??????? where C:IComparer<T>
??? {??????????
??????? for (int i = 1; i <= array.Length - 1; i++) {
??????????? //Console.Write("{0}: ", i);
??????????? int j = i;
??????????? while (j>=1 && comparer.Compare(array[j], array[j - 1]) < 0) {
??????????????? swap(ref array[j], ref array[j-1]);
??????????????? j--;
??????????? }
??????????? //Console.WriteLine();
??????????? //AlgorithmHelper.PrintArray(array);
??????? }
??? }

??? // 交換數組array中第i個元素和第j個元素
??? private static void swap<T>(ref T x,ref T y) {
??????? // Console.Write("{0}<-->{1} ", x, y);
??????? T temp = x;
??????? x = y;
??????? y = temp;
??? }
}

上面Console.WriteLine()方法和AlgorithmHelper.PrintArray()方法僅僅是出于測試方便，PrintArray()方法依次打印了數組的內容。swap<T>()方法則用于交換數組中的兩條記錄，也對交換數進行了打印（這里我注釋掉了，但在測試時可以取消對它們的注釋）。外層for循環控制變量i表示當前處理第i條記錄。

public class AlgorithmHelper {
??? // 打印數組內容
??? public static void PrintArray<T>(T[] array) {
??????? Console.Write("?? Array:");
??????? foreach (T item in array) {
??????????? Console.Write(" {0}", item);
??? ??? }
??????? Console.WriteLine();
??? }
}

// 獲得Comparer，進行比較
public class ComparerFactory {
??? public static IComparer<int> GetIntComparer() {
??????? return new IntComparer();
??? }

??? public class IntComparer : IComparer<int> {
??????? public int Compare(int x, int y) {
??????????? return x.CompareTo(y);
??????? }
??? }
}

上面這段代碼我們創建了一個ComparerFactory類，它用于獲得一個IntComparer對象，這個對象實現了IComparer<T>接口，規定了兩個int類型的關鍵碼之間比較大小的規則。如果你有自定義的類型，比如叫MyType，只需要在ComparerFactory中再添加一個類，比如叫MyTypeComparer，然后讓這個類也實現IComparer<T>接口，最后再添加一個方法返回MyTypeComparer就可以了。

輸出演示(C#)

接下來我們看一下客戶端代碼和輸出：

static void Main(string[] args) {
??? int[] array = {42,20,17,13,28,14,23,15};
??? //int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
??? AlgorithmHelper.PrintArray(array);

??? SortAlgorithm.InsertSort
??????? (array, ComparerFactory.GetIntComparer());
}

算法實現(C++)

// 對int類型進行排序
class IntComparer{
??? public:
??????? static bool Smaller(int x, int y){
??????????? return x<y;
??????? }
??????? static bool Equal(int x, int y){
??????????? return x==y;
??????? }
??????? static bool Larger(int x, int y){
??????????? return x>y;
??????? }
};

// 插入排序
template <class T, class C>
void InsertSort(T a[], int length){
??? for(int i=1;i<=length-1;i++){
??????? int j = i;
??????? while(j>=1 && C::Smaller(a[j], a[j-1])){
??????????? swap(a[j], a[j-1]);
??????????? j--;
??????? }
??? }
}

2.冒泡排序

算法思想

如果你從沒有學習過有關算法方面的知識，而需要設計一個數組排序的算法，那么很有可能設計出的就是泡沫排序算法了。因為它很好理解，實現起來也很簡單。它也含有兩層循環，假設數組長度為n，外層循環控制變量i由0到n-2遞增，這個外層循環并不是處理某個記錄，只是控制比較的趟數，由0到n-2，一共比較n-1趟。為什么n個記錄只需要比較n-1趟？我們可以先看下最簡單的兩個數排序：比如4和3，我們只要比較一趟，就可以得出3、4。對于更多的記錄可以類推。

數組記錄的交換由里層循環來完成，控制變量j初始值為n-1（數組下標），一直遞減到1。數組記錄從數組的末尾開始與相鄰的上一個記錄相比，如果上一記錄比當前記錄的關鍵碼大，則進行交換，直到當前記錄的下標為1為止（此時上一記錄的下標為0）。整個過程就好像一個氣泡從底部向上升，于是這個排序算法也就被命名為了冒泡排序。

我們來對它進行一個考察，按照這種排序方式，在進行完第一趟循環之后，最小的一定位于數組最頂部（下標為0）；第二趟循環之后，次小的記錄位于數組第二（下標為1）的位置；依次類推，第n-1趟循環之后，第n-1小的記錄位于數組第n-1（下標為n-2）的位置。此時無需再進行第n趟循環，因為最后一個已經位于數組末尾（下標為n-1）位置了。

算法實現(C#)

// 泡沫排序
public static void BubbleSort<T, C>(T[] array, C comparer)
??? where C : IComparer<T>
{
??? int length = array.Length;

??? for (int i = 0; i <= length - 2; i++) {
??????? //Console.Write("{0}: ", i + 1);
??????? for (int j = length - 1; j >= 1; j--) {
??????????? if (comparer.Compare(array[j], array[j - 1]) < 0) {
??????????????? swap(ref array[j], ref array[j - 1]);
??????????? }
??????? }
??????? //Console.WriteLine();
??????? //AlgorithmHelper.PrintArray(array);
??? }
}

輸出演示(C#)

static void Main(string[] args) {
??? int[] array = {42,20,17,13,28,14,23,15};
??? AlgorithmHelper.PrintArray(array);

??? SortAlgorithm.BubbleSort
??????? (array, ComparerFactory.GetIntComparer());
}

算法實現(C++)

// 冒泡排序
template <class T, class C>
void BubbleSort(T a[], int length){
??? for(int i=0;i<=length-2;i++){
??????? for(int j=length-1; j>=1; j--){
??????????? if(C::Smaller(a[j], a[j-1]))
??????????????? swap(a[j], a[j-1]);
??????? }
??? }
}

3.選擇排序

算法思想

選擇排序是對冒泡排序的一個改進，從上面冒泡排序的輸出可以看出，在第一趟時，為了將最小的值13由數組末尾冒泡的數組下標為0的第一個位置，進行了多次交換。對于后續的每一趟，都會進行類似的交換。

選擇排序的思路是：對于第一趟，搜索整個數組，尋找出最小的，然后放置在數組的0號位置；對于第二趟，搜索數組的n-1個記錄，尋找出最小的（對于整個數組來說則是次小的），然后放置到數組的第1號位置。在第i趟時，搜索數組的n-i+1個記錄，尋找最小的記錄（對于整個數組來說則是第i小的），然后放在數組i-1的位置（注意數組以0起始）。可以看出，選擇排序顯著的減少了交換的次數。

需要注意的地方是：在第i趟時，內層循環并不需要遞減到1的位置，只要循環到與i相同就可以了，因為之前的位置一定都比它小（也就是第i小）。另外里層循環是j>i，而不是j>=i，這是因為i在進入循環之后就被立即保存到了lowestIndex中。

算法實現(C#)

public static void SelectionSort<T, C>(T[] array, C comparer)
??? where C : IComparer<T>
{
??? int length = array.Length;
??? for (int i = 0; i <= length - 2; i++) {
??????? Console.Write("{0}: ", i+1);
??????? int lowestIndex = i;??????? // 最小記錄的數組索引
??????? for (int j = length - 1; j > i; j--) {
??????????? if (comparer.Compare(array[j], array[lowestIndex]) < 0)
??????????????? lowestIndex = j;
??????? }
??????? swap(ref array[i], ref array[lowestIndex]);
??????? AlgorithmHelper.PrintArray(array);
??? }
}

輸出演示(C#)

static void Main(string[] args) {
??? int[] array = {42,20,17,13,28,14,23,15};
??? AlgorithmHelper.PrintArray(array);

??? SortAlgorithm.SelectionSort
??????? (array, ComparerFactory.GetIntComparer());
}

算法實現(C++)

// 選擇排序
template <class T, class C>
void SelectionSort(T a[], int length) {
??? for(int i = 0; i <= length-2; i++){
??????? int lowestIndex = i;
??????? for(int j = length-1; j>i; j--){
??????????? if(C::Smaller(a[j], a[lowestIndex]))
??????????????? lowestIndex = j;
??????? }
??????? swap(a[i], a[lowestIndex]);
??? }
}

4.希爾排序

希爾排序利用了插入排序的一個特點來優化排序算法，插入排序的這個特點就是：當數組基本有序的時候，插入排序的效率比較高。比如對于下面這樣一個數組：

int[] array = { 1, 0, 2, 3, 5, 4, 8, 6, 7, 9 };

插入排序的輸出如下：

可以看到，盡管比較的趟數沒有減少，但是交換的次數卻明顯很少。希爾排序的總體想法就是先讓數組基本有序，最后再應用插入排序。具體過程如下：假設有數組int a[] = {42,20,17,13,28,14,23,15}，不失一般性，我們設其長度為length。

第一趟時，步長step = length/2 = 4，將數組分為4組，每組2個記錄，則下標分別為(0,4)(1,5)(2,6)(3,7)；轉換為數值，則為{42,28}, {20,14}, {17,23}, {13,15}。然后對每個分組進行插入排序，之后分組數值為{28,42}, {14,20}, {17,23}, {13,15}，而實際的原數組的值就變成了{28,14,17,13,42,20,23,15}。這里要注意的是分組中記錄在原數組中的位置，以第2個分組{14,20}來說，它的下標是(1,5)，所以這兩個記錄在原數組的下標分別為a[1]=14;a[5]=20。

第二趟時，步長 step = step/2 = 2，將數組分為2組，每組4個記錄，則下標分別為(0,2,4,6)(1,3,5,7)；轉換為數值，則為{28,17,42,23}, {14,13,20,15}，然后對每個分組進行插入排序，得到{17,23,28,42}{13,14,15,20}。此時數組就成了{17,13,23,14,28,15,42,20}，已經基本有序。

第三趟時，步長 step=step/2 = 1，此時相當進行一次完整的插入排序，得到最終結果{13,14,15,17,20,23,28,42}。

算法實現(C#)

// 希爾排序
public static void ShellSort<T, C>(T[] array, C comparer)
??? where C : IComparer<T>
{
??? for (int i = array.Length / 2; i >= 1; i = i / 2) {
??????? Console.Write("{0}: ", i);
??????? for (int j = 0; j < i; j++) {
??????????? InsertSort(array, j, i, comparer);
??????? }
??????? Console.WriteLine();
??????? AlgorithmHelper.PrintArray(array);
??? }
}

// 用于希爾排序的插入排序
private static void InsertSort<T, C>
??? (T[] array, int startIndex, int step, C comparer)
??? where C : IComparer<T>
{
??? for (int i = startIndex + step; i <= array.Length - 1; i += step) {
??????? int j = i;
??????? while(j>= step && comparer.Compare(array[j], array[j - step]) <0 ){
??????????? swap(ref array[j], ref array[j - step]);
??????????? j -= step;
??????? }
??? }
}

注意這里插入排序InsertSort()方法的參數，startIndex是分組的起始索引，step是步長，可以看出，前面的插入排序只是此處step=1,startindex=0的一個特例。

輸出演示(C#)

static void Main(string[] args) {
??? int[] array = {42,20,17,13,28,14,23,15};
??? AlgorithmHelper.PrintArray(array);

??? SortAlgorithm.ShellSort
??????? (array, ComparerFactory.GetIntComparer());
}

算法實現(C++)

// 希爾排序
template<class T, class C>
void ShellSort(T a[], int length){
??? for(int i = length/2; i >= 1; i = i/2 ){
??????? for(int j = 0; j<i; j++){
??????????? InsertSort<T, C>(&a[j], length-1, i);
??????? }
??? }
}

// 用于希爾排序的插入排序
template<class T, class C>
void InsertSort(T a[], int length, int step){
??? for(int i = step; i<length; i+= step){
??????? int j = i;
??????? while(j>=step && C::Smaller(a[j], a[j-step])){
??????????? swap(a[j], a[j-step]);
??????????? j-=step;
??????? }
??? }
}