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

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),河南企業(yè)網(wǎng)站建設(shè),河南品牌網(wǎng)站建設(shè),網(wǎng)站定制,河南網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷(xiāo),網(wǎng)絡(luò)優(yōu)化,河南網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M(mǎn)足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專(zhuān)業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶(hù)成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

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

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

二、從幾種“屌絲”的排序算法開(kāi)始

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

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

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

 
 
 
 

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

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

    

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

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

 
 
 
 

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

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

     

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

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

 
 
 
 

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

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

     

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

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

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

【編輯推薦】

1. Java數(shù)據(jù)結(jié)構(gòu)：棧的實(shí)現(xiàn)
2. 淺談C++開(kāi)發(fā)中數(shù)據(jù)結(jié)構(gòu)和算法的分離
3. 從淘寶數(shù)據(jù)結(jié)構(gòu)來(lái)看電子商務(wù)中商品屬性設(shè)計(jì)
4. 如何用Perl關(guān)聯(lián)數(shù)組創(chuàng)建數(shù)據(jù)結(jié)構(gòu)
5. 詳細(xì)介紹C++中的虛函數(shù)和動(dòng)態(tài)聯(lián)編

網(wǎng)頁(yè)名稱(chēng)：你所能用到的數(shù)據(jù)結(jié)構(gòu)（二）
文章源于：http://uogjgqi.cn/article/cciohjc.html