先回答幾個留言中的一個問題和我對無損編碼那一節(jié)的一個留言的一個看法，***個是推薦算法書，首先，我不是什么高手和大牛，所以當(dāng)不起“推薦”這個詞。我見過很多人，對于這個問題我覺得很多人都會說出《算法導(dǎo)論》，但是我不完全這么認(rèn)為，我始終認(rèn)為人和人是不一樣的，《算法導(dǎo)論》肯定是一本經(jīng)典的書，但是學(xué)習(xí)知識的目的是要學(xué)懂，比誰的能力大不是比誰看的經(jīng)典書籍多，而是比誰懂得多。所以如果讓我推薦的話，我覺得要分三種情況，***種，你有很深的數(shù)學(xué)基礎(chǔ)，高中特別喜歡做數(shù)學(xué)題，我覺得可以嘗試看看《算法導(dǎo)論》甚至是傳說中的《計算機(jī)程序設(shè)計藝術(shù)》，第二種就是高中并不對數(shù)學(xué)很感興趣，但是大學(xué)確實(shí)很喜歡編程但是對于數(shù)學(xué)看多了覺得頭會昏昏的人，其實(shí)我特別覺得好的是《算法概論》和《算法設(shè)計與分析基礎(chǔ)》，除了這兩本，我覺得看一些《離散數(shù)學(xué)》對于培養(yǎng)算法的基本思維方式真很有幫助，第三種是對于數(shù)學(xué)理解不是那么強(qiáng)的，我覺得不妨看看《編程之美》這類的有實(shí)際例子不會那么抽象的書，培養(yǎng)出興趣，有了興趣，后面只是時間問題了。

      第二個是對無損編碼有一個朋友說的這是“時間換空間”，從編程上說確實(shí)是時間換空間，但是這些一般都是在有實(shí)際應(yīng)用背景下的，比如我的所謂研究方向是“可逆水印”，這個玩意兒必須要靠無損編碼做前期處理，所以這個看法是正確的，但是卻不是最需要考慮的，因?yàn)檫@個有應(yīng)用背景。

      好了，開始這次的內(nèi)容，不同于很多數(shù)據(jù)結(jié)構(gòu)先從列表和堆棧說起，我先幾個和數(shù)據(jù)結(jié)構(gòu)結(jié)合不太強(qiáng)的排序算法開始，因?yàn)槲矣X得在學(xué)這一系列之前對算法的效率建立一個認(rèn)識是必要的。

二、從幾種“屌絲”的排序算法開始

      先介紹幾種簡單的時間效率是O(N*N)的排序算法，雖然這些排序算法比較初級，但是任何高級的東西都是從初級的東西演化推理出來的，不學(xué)小學(xué)的123你也不可能學(xué)會高數(shù)的微積分。所以說這些算法雖然“屌絲”，但是沒有這些“屌絲”哪來的“高帥富”？可以證明的出來，通過交換的排序算法效率最快只能到O(N*logN）。

      除了上面的這個，我還想強(qiáng)調(diào)的一點(diǎn)是在有的書里面提到的排序算法是否是穩(wěn)定的這個概念，所謂有序就是說待排序數(shù)列中相等的值在經(jīng)過排序算法之后是否會交換位置，比如一組數(shù)據(jù)（2,0,2),在排序之后自然是（0,2,2）,如果這個排序算法是穩(wěn)定的，那么(0,2,2)中***個出現(xiàn)的2應(yīng)該是(2,0,2)中的***個2，也就是待排序數(shù)列中的兩個2的相對位置不會發(fā)生交換。關(guān)于穩(wěn)定的定義可以參看百度的這個http://baike.baidu.com/view/547325.htm?fromTaglist 這個看似不起眼的知識點(diǎn)就是昨天微軟校園招聘倒數(shù)第二題的考點(diǎn)，不得不說大公司出的題目牛逼。

     選擇排序是最為符合人類自然思維的一種排序方式，不斷找到數(shù)列中的最小值，將其放在目前最小的位置上，簡單方便快捷，不得不說是最“屌絲”的排序算法，沒有什么特殊的技巧，完全靠兩個循環(huán)，代碼如下所示：

void SelectionSort(int a[],int length) 
{ 
    for(int i=0;i<length;i++) 
    { 
        cout<<"Sort time number "<<(i+1)<<":"; 
               int min=i;         
        int j=i; 
        for(;j<length;j++) 
        { 
            if(a[min]>a[j]) 
               min=j; 
        } 
        int tmp=a[min]; 
        a[min]=a[i]; 
        a[i]=tmp; 
 
        for(int k=0;k<length;k++) 
            cout<<a[k]<<" "; 
        cout<<endl; 
 
    } 
} 

    運(yùn)行結(jié)果如下所示:

    從結(jié)果中可以看到，***輪排序中，最小的元素3被安排在了***個位置上，第二輪5被安排在次小的位置上，以此類推。選擇排序算法是不是穩(wěn)定的呢？選擇排序明顯不是有序的，就像連接里面寫的那樣，因?yàn)槟阍诮粨Q的過程中，如果出現(xiàn)相同的元素，無法保證交換的過程中元素被交換的位置是否在第二次出現(xiàn)該元素之后。

    接下來當(dāng)然是冒泡排序，這種排序算法通過不斷比較相鄰兩個數(shù)的大小并交換位置來達(dá)到排序的目的，這種算法比較符合人類的自然思維，這樣就自然需要兩個循環(huán)，***個循環(huán)是遍歷整個數(shù)組，第二個循環(huán)是不停地未排序的數(shù)列中兩個相鄰的元素，每一輪之后，***的元素都可以排在目前***的位置（當(dāng)然這取決于你的比較部分的代碼是如何寫的），所以這個算法也很容易寫出來。

void bubble(int a[],int length) 
{ 
    int temp=0; 
    for(int j=0;j<length;j++) 
    {  
       cout<<"Sort time number "<<(j+1)<<":"; 
       
       for (int i=0;i<length-1;i++) 
        if (a[i]>a[i+1]) 
        {  
            temp=a[i]; 
            a[i]=a[i+1]; 
            a[i+1]=temp; 
        } 
        for(int k=0;k<length;k++) 
         cout<<a[k]<<" "; 
        cout<<endl; 
    } 
 
} 

     其結(jié)果如下圖所示：

     這個簡單的排序算法卻反應(yīng)出了排序算法的一個最初級的思路就是比較和交換，別小看任何不起眼的概念，因?yàn)楹竺娲笈儗τ谂判蛩惴ǖ母倪M(jìn)就是通過相近辦法減少比較和交換，或者是不做相鄰元素的比較。可以看到每一趟排序之后，當(dāng)前***的元素都到了當(dāng)前***的位置上，冒泡排序算法是穩(wěn)定的排序算法，但是前提是你不會在比較的過程中使用<=或者>=這種符號，交換兩個相等的元素是沒有意義的，加上算法一般是到大數(shù)據(jù)集中才顯示出作用，這些環(huán)境下一個重要的因子就是要快，這種交換會無謂的增大程序的開銷，所以一般在排序算法中不會用到=的交換，你也就不用鉆牛角尖的說排序算法的穩(wěn)定性會取決于用于比較的符號。

      除了冒泡排序，插入排序我覺得是***人的排序自然思維方式的拓展，這個算法的思想基本就是不停地排出有序的數(shù)列，比如10個數(shù)，先將前兩個數(shù)的順序排好，再看第三個數(shù)，然后將這三個數(shù)排好，不斷吸收元素，不斷的排序，這樣會保持了待排序數(shù)列的相對穩(wěn)定性，也保持了算法排序的穩(wěn)定性。其實(shí)現(xiàn)代碼如下：

void InsertSort(int numbers[],int array_size) 
{ 
    int j; 
    for(int p=1;p<array_size;p++) 
    { 
        cout<<"Sort time number "<<p<<":"; 
        int tmp=numbers[p]; 
         
        for(j=p;j>0&&tmp<numbers[j-1];j--) 
        { 
             numbers[j]=numbers[j-1]; 
        } 
        numbers[j]=tmp; 
       for(int k=0;k<array_size;k++) 
         cout<<numbers[k]<<" "; 
        cout<<endl; 
    } 
} 

      實(shí)現(xiàn)結(jié)果如下圖所示：

     可以看到這種排序算法，吸收，排序的特點(diǎn)，最開始是兩個元素的數(shù)組編程有序的，第二次是3個元素變成的，如此往復(fù)。

     這三種最簡單的排序算法是排序算法的入門，如果想測試其效率，可以使用我上一節(jié)的代碼，這里我還要說一句的是，我寫的這三段代碼參數(shù)的命名都是不一樣的，這是因?yàn)槲沂呛脦滋鞂懙模@也反過來說明了在軟件開發(fā)中有一個規(guī)范的重要性，試想如果是很多人一起開發(fā)軟件，一樣的參數(shù)意思，你今天想到用著表示，明天想到用那個表示，對于別人這是一種莫大的痛苦。

原文鏈接：http://www.cnblogs.com/ZXYloveFR/archive/2012/09/23/2698563.html

【編輯推薦】