以下文章整理的不對。還請見諒。

四種簡單的排序算法

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

好了，閑話就說這么多吧，我們回到正題。因?yàn)檫@方面的著作很多，所以這里只給出簡單的描述和實(shí)現(xiàn)，供我本人及感興趣的朋友參考。我會盡量用C#和C++兩種語言實(shí)現(xiàn)，對于一些不好用C#表達(dá)的結(jié)構(gòu)，僅用C++實(shí)現(xiàn)。

本文將描述四種最簡單的排序方法，插入排序、泡沫排序、選擇排序、希爾排序，我在這里將其稱為“簡單排序”，是因?yàn)樗鼈兿鄬τ诳焖倥判?、歸并排序、堆排序、分配排序、基數(shù)排序從理解和算法上要簡單一些。對于后面這幾種排序，我將其稱為“高級排序”。

簡單排序

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

1.插入排序

算法思想

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

現(xiàn)在我們考察一下第i條記錄的處理情況：假設(shè)外層循環(huán)遞進(jìn)到第i條記錄，設(shè)其關(guān)鍵碼的值為X，那么此時(shí)有可能有兩種情況：

算法實(shí)現(xiàn)(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);        }    }    // 交換數(shù)組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()方法依次打印了數(shù)組的內(nèi)容。swap<T>()方法則用于交換數(shù)組中的兩條記錄，也對交換數(shù)進(jìn)行了打?。ㄟ@里我注釋掉了，但在測試時(shí)可以取消對它們的注釋）。外層for循環(huán)控制變量i表示當(dāng)前處理第i條記錄。
public class AlgorithmHelper {    // 打印數(shù)組內(nèi)容    public static void PrintArray<T>(T[] array) {        Console.Write("   Array:");        foreach (T item in array) {            Console.Write(" {0}", item);        }        Console.WriteLine();    }}// 獲得Comparer，進(jìn)行比較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);        }    }}上面這段代碼我們創(chuàng)建了一個ComparerFactory類，它用于獲得一個IntComparer對象，這個對象實(shí)現(xiàn)了IComparer<T>接口，規(guī)定了兩個int類型的關(guān)鍵碼之間比較大小的規(guī)則。如果你有自定義的類型，比如叫MyType，只需要在ComparerFactory中再添加一個類，比如叫MyTypeComparer，然后讓這個類也實(shí)現(xiàn)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());}
算法實(shí)現(xiàn)(C++)
// 對int類型進(jìn)行排序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.冒泡排序
算法思想
如果你從沒有學(xué)習(xí)過有關(guān)算法方面的知識，而需要設(shè)計(jì)一個數(shù)組排序的算法，那么很有可能設(shè)計(jì)出的就是泡沫排序算法了。因?yàn)樗芎美斫?，?shí)現(xiàn)起來也很簡單。它也含有兩層循環(huán)，假設(shè)數(shù)組長度為n，外層循環(huán)控制變量i由0到n-2遞增，這個外層循環(huán)并不是處理某個記錄，只是控制比較的趟數(shù)，由0到n-2，一共比較n-1趟。為什么n個記錄只需要比較n-1趟？我們可以先看下最簡單的兩個數(shù)排序：比如4和3，我們只要比較一趟，就可以得出3、4。對于更多的記錄可以類推。
數(shù)組記錄的交換由里層循環(huán)來完成，控制變量j初始值為n-1（數(shù)組下標(biāo)），一直遞減到1。數(shù)組記錄從數(shù)組的末尾開始與相鄰的上一個記錄相比，如果上一記錄比當(dāng)前記錄的關(guān)鍵碼大，則進(jìn)行交換，直到當(dāng)前記錄的下標(biāo)為1為止（此時(shí)上一記錄的下標(biāo)為0）。整個過程就好像一個氣泡從底部向上升，于是這個排序算法也就被命名為了冒泡排序。
我們來對它進(jìn)行一個考察，按照這種排序方式，在進(jìn)行完第一趟循環(huán)之后，最小的一定位于數(shù)組最頂部（下標(biāo)為0）；第二趟循環(huán)之后，次小的記錄位于數(shù)組第二（下標(biāo)為1）的位置；依次類推，第n-1趟循環(huán)之后，第n-1小的記錄位于數(shù)組第n-1（下標(biāo)為n-2）的位置。此時(shí)無需再進(jìn)行第n趟循環(huán)，因?yàn)樽詈笠粋€已經(jīng)位于數(shù)組末尾（下標(biāo)為n-1）位置了。
算法實(shí)現(xiàn)(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());}
算法實(shí)現(xiàn)(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.選擇排序
算法思想
選擇排序是對冒泡排序的一個改進(jìn)，從上面冒泡排序的輸出可以看出，在第一趟時(shí)，為了將最小的值13由數(shù)組末尾冒泡的數(shù)組下標(biāo)為0的第一個位置，進(jìn)行了多次交換。對于后續(xù)的每一趟，都會進(jìn)行類似的交換。
選擇排序的思路是：對于第一趟，搜索整個數(shù)組，尋找出最小的，然后放置在數(shù)組的0號位置；對于第二趟，搜索數(shù)組的n-1個記錄，尋找出最小的（對于整個數(shù)組來說則是次小的），然后放置到數(shù)組的第1號位置。在第i趟時(shí)，搜索數(shù)組的n-i+1個記錄，尋找最小的記錄（對于整個數(shù)組來說則是第i小的），然后放在數(shù)組i-1的位置（注意數(shù)組以0起始）?？梢钥闯觯x擇排序顯著的減少了交換的次數(shù)。
需要注意的地方是：在第i趟時(shí)，內(nèi)層循環(huán)并不需要遞減到1的位置，只要循環(huán)到與i相同就可以了，因?yàn)橹暗奈恢靡欢ǘ急人。ㄒ簿褪堑趇小）。另外里層循環(huán)是j>i，而不是j>=i，這是因?yàn)閕在進(jìn)入循環(huán)之后就被立即保存到了lowestIndex中。
算法實(shí)現(xiàn)(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;        // 最小記錄的數(shù)組索引        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());}
算法實(shí)現(xiàn)(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.希爾排序
希爾排序利用了插入排序的一個特點(diǎn)來優(yōu)化排序算法，插入排序的這個特點(diǎn)就是：當(dāng)數(shù)組基本有序的時(shí)候，插入排序的效率比較高。比如對于下面這樣一個數(shù)組：
int[] array = { 1, 0, 2, 3, 5, 4, 8, 6, 7, 9 };
插入排序的輸出如下：
可以看到，盡管比較的趟數(shù)沒有減少，但是交換的次數(shù)卻明顯很少。希爾排序的總體想法就是先讓數(shù)組基本有序，最后再應(yīng)用插入排序。具體過程如下：假設(shè)有數(shù)組int a[] = {42,20,17,13,28,14,23,15}，不失一般性，我們設(shè)其長度為length。
第一趟時(shí)，步長step = length/2 = 4，將數(shù)組分為4組，每組2個記錄，則下標(biāo)分別為(0,4)(1,5)(2,6)(3,7)；轉(zhuǎn)換為數(shù)值，則為{42,28}, {20,14}, {17,23}, {13,15}。然后對每個分組進(jìn)行插入排序，之后分組數(shù)值為{28,42}, {14,20}, {17,23}, {13,15}，而實(shí)際的原數(shù)組的值就變成了{(lán)28,14,17,13,42,20,23,15}。這里要注意的是分組中記錄在原數(shù)組中的位置，以第2個分組{14,20}來說，它的下標(biāo)是(1,5)，所以這兩個記錄在原數(shù)組的下標(biāo)分別為a[1]=14;a[5]=20。
第二趟時(shí)，步長 step = step/2 = 2，將數(shù)組分為2組，每組4個記錄，則下標(biāo)分別為(0,2,4,6)(1,3,5,7)；轉(zhuǎn)換為數(shù)值，則為{28,17,42,23}, {14,13,20,15}，然后對每個分組進(jìn)行插入排序，得到{17,23,28,42}{13,14,15,20}。此時(shí)數(shù)組就成了{(lán)17,13,23,14,28,15,42,20}，已經(jīng)基本有序。
第三趟時(shí)，步長 step=step/2 = 1，此時(shí)相當(dāng)進(jìn)行一次完整的插入排序，得到最終結(jié)果{13,14,15,17,20,23,28,42}。
算法實(shí)現(xiàn)(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()方法的參數(shù)，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());}
算法實(shí)現(xiàn)(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;        }    }}對于上面三種算法的代碼，插入排序、冒泡排序、選擇排序，都是Θ(n2)，而希爾排序略好一些，是Θ（n1.5），關(guān)于算法分析，大家感興趣可以參考相關(guān)書籍。這里推薦《數(shù)據(jù)結(jié)構(gòu)與算法分析(C++版)第二版》和《算法I~IV（C++實(shí)現(xiàn)）——基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、排序和搜索》，都很不錯，我主要也是參考這兩本書。