三、對(duì)于效率提高的初次嘗試

      對(duì)于最自然的幾種排序算法，數(shù)學(xué)家們開始思考如何提高排序算法的效率，可以通過數(shù)學(xué)證明出來如果想達(dá)到這個(gè)目的，必須想辦法將相距較遠(yuǎn)的元素進(jìn)行交換，具體原理涉及到比較一定的數(shù)學(xué)證明，因?yàn)槲也皇菍W(xué)數(shù)學(xué)出生的，所以我不能完整嚴(yán)謹(jǐn)?shù)膶懗鲞@個(gè)證明，所以，套用一句俗話吧，如果感興趣你可以自己查閱一下資料。

      希爾排序是以其發(fā)明人Shell的名字命名的。這里有個(gè)故事就是在一些書上，這個(gè)算法被稱作是Shell-Metzner排序法，但是呢，這個(gè)叫做Metzner的人說“我沒有為這種算法做任何事，我的名字不應(yīng)該出現(xiàn)在算法的名字中。”有沒有瞬間覺得這個(gè)Metzner實(shí)在是太偉大了？特別是在現(xiàn)在這個(gè)大環(huán)境下，這種人如果能多出現(xiàn)在高等教育上，頓時(shí)覺得中國(guó)的高等教育有希望了。作為***批沖刺突破二次時(shí)間界的算法之一，從交換距離較遠(yuǎn)的元素這個(gè)思路出發(fā)，在每一次的交換中獎(jiǎng)待排序數(shù)列分為若干對(duì)，兩兩交換，但是這兩個(gè)對(duì)的距離由近及遠(yuǎn)，不停地交換，看起來感覺有點(diǎn)抽象，那么就先從代碼開始好了。

void ShellSort(int numbers[],int array_size) 
{ 
    int j=0; 
    for(int gap=array_size/2;gap>0;gap=gap/2) 
    {   
        cout<<"Sort time number "<<(j+1)<<":"; 
        for(int i=gap;i<array_size;i++) 
        { 
          int tmp=numbers[i]; 
          int j=i; 
          for(;j>=gap&&tmp<numbers[j-gap];j-=gap) 
          { 
              numbers[j]=numbers[j-gap]; 
          } 
          numbers[j]=tmp; 
        } 
        for (int i = 0; i < array_size; i++){ 
            cout<<numbers[i]<<" "; 
        } 
        j++; 
        cout<<endl; 
    } 
 
} 

     這個(gè)代碼很值得研究，除去***的打印代碼，這個(gè)排序里面竟然用了三次循環(huán)，重要的是雖然是三次循環(huán)但是卻提高了效率!所以說，有的時(shí)候，事情不僅僅不是你看到的那樣而且換一種看似不 看起來確實(shí)令人挺不可思議的，但是為什么呢，如果讓我從一個(gè)最通俗的方式來解釋的話，雖然這里有三個(gè)循環(huán)，但是在你會(huì)發(fā)現(xiàn)因?yàn)橥饷鎯蓚€(gè)循環(huán)的原因，最里面一個(gè)循環(huán)執(zhí)行的次數(shù)是很少的，另外一個(gè)原因就是這里的步長(zhǎng)，步長(zhǎng)不是逐個(gè)增加導(dǎo)致了循環(huán)次數(shù)的減少，從而使得性能的提高。

     這一段話貌似還是很讓人覺得略有些在裝B，所以，還是結(jié)合實(shí)際的數(shù)解釋一下增加點(diǎn)親切感。

      結(jié)合代碼和結(jié)果來看，這里有十個(gè)數(shù)，最開始的步長(zhǎng)是5，那么***輪分別比較（0,5），（11,11），（22，42），（33,18），（24，9），兩兩比較之后進(jìn)行交換的結(jié)果如第二行所示，這時(shí)候最內(nèi)層循環(huán)一共執(zhí)行了2次，接下來，步長(zhǎng)減半，比較的順序應(yīng)該是(0,22),(11,18),[(22,9)（進(jìn)行交換）和(9,0)],[(5,18）（有交換）和(5,11)（有交換）],后面我就不列舉了，實(shí)在是列舉不動(dòng)了，眼睛和腦子雙雙都不行了，在你完成全部列舉完成的時(shí)候很輕松就可以看到在第三輪的時(shí)候基本上已經(jīng)不需要進(jìn)行交換了，這和顯示出來的是一樣的，這說明了在第三輪的時(shí)候最內(nèi)層循環(huán)一次交換操作也沒有進(jìn)行，而外面兩層主要是遍歷，相比于交換，它所耗費(fèi)的資源要少的多，換句話說，由于前面的大步長(zhǎng)的時(shí)候進(jìn)行了一些大刀闊斧的排序，導(dǎo)致在后面的小步長(zhǎng)的時(shí)候只要做些許修正就可以了，有一部分情況下是完全不需要修正的，這樣也得到了一個(gè)效率上的提高。

     所以說增量的選擇對(duì)于希爾排序能否達(dá)到提高的效果是十分重要的，這里采用的是最簡(jiǎn)單不斷將步長(zhǎng)減半的方式，一般來說，最簡(jiǎn)單的效果肯定不是***的，對(duì)于希爾排序增量選擇的研究是非常多的，這個(gè)還是需要一定的數(shù)學(xué)知識(shí)的，有一種Hibbard增量可以使得希爾排序的速度達(dá)到0(N^2/3),這也是為什么希爾排序是能突破二次時(shí)間界的算法。

四、圈圈圓圓圈圈

      在提高排序算法的效率上，各個(gè)大牛數(shù)學(xué)家努力的想辦法減少比較次數(shù)，從而減少交換的速度，在此基礎(chǔ)上，大牛們又發(fā)明了歸并排序，快速排序的算法，使得排序的時(shí)間界達(dá)到了O(N*LOGN），而這后來也被證明了是基于交換的排序算法的時(shí)間下界。也就是說，只要你的思想離不開比較交換，排序算法的最快也就這么快了。

     歸并排序和快速排序的寫法相對(duì)于前面的提到的要看起來“高帥富”很多，看起來非常復(fù)雜的原理用幾行就寫完了，而且邏輯很清晰，這一切都是得益于實(shí)現(xiàn)它們的時(shí)候通常都采用了遞歸的結(jié)構(gòu)，這就像“高帥富”的跑車，先別管這個(gè)“高帥富”是否真的帥，開一個(gè)跑車出來讓你看看至少已經(jīng)讓你在心中有了幾分對(duì)于“高帥富”的敬畏，至于從車上出來的人到底是怎樣的人，與他的車帥不帥關(guān)系不大。這就像用遞歸結(jié)構(gòu)實(shí)現(xiàn)的算法，使用遞歸結(jié)構(gòu)往往會(huì)使人覺得這個(gè)算法看起來很牛逼，而且可以使這個(gè)算法思想看起來十分清晰，但是至于這樣實(shí)現(xiàn)效率是否高效，那就不一定了。

     在寫這兩個(gè)算法之前，首先非常有必要闡述一下遞歸的思想，說到遞歸，簡(jiǎn)單的用程序的語言來解釋就是不定的調(diào)用自己直到滿足某一個(gè)條件結(jié)束輸出某一個(gè)值或者進(jìn)行某一個(gè)操作，很多人***個(gè)想到的應(yīng)該是斐波那契數(shù)列，其實(shí)吧，我覺得很多書把這個(gè)作為遞歸思想的啟蒙例子很有誤導(dǎo)性，因?yàn)殪巢瞧鯏?shù)列的計(jì)算，如果使用遞歸的話，效率是非常差的，雖然這個(gè)求斐波那契數(shù)列某一項(xiàng)的代碼很簡(jiǎn)單，我還是貼出來一下。

int Fibonacci(int n) 
{ 
    if(n==0||n==1) 
        return n; 
    else 
        return Fibonacci(n-1)+ Fibonacci(n-2); 
} 

     我們來測(cè)試一下它的運(yùn)行時(shí)間好了，我們求前50項(xiàng)的值，看看它所要耗費(fèi)的時(shí)間。

     我已經(jīng)等不到第50項(xiàng)的值出來了，從運(yùn)行結(jié)果可以看到到第39項(xiàng)的時(shí)候運(yùn)行時(shí)間已經(jīng)開始飆升了，到不了第50項(xiàng)就已經(jīng)到了無法忍受的地步了，這明顯完全無法滿足實(shí)際的要求，某種程度上這會(huì)給人一種誤導(dǎo)，遞歸在實(shí)際運(yùn)用中用處不大。明顯，這種想法是錯(cuò)誤的。

     來看這樣一個(gè)例子，將一個(gè)數(shù)字倒序輸出，比如輸入的是12345，輸出是54321，這個(gè)問題的解法相當(dāng)簡(jiǎn)單，就是不停將自身的對(duì)10取余，不停地?cái)?shù)以10。這個(gè)解法符合遞歸的思想，其代碼如下所示：

void PrintReverse(int n) 
{ 
    if(n!=0) 
    { 
        cout<<n%10; 
        PrintReverse(n/10); 
     
    }     
} 

     這樣的一個(gè)例子就適合用遞歸的思想去做，因?yàn)橐粋€(gè)整數(shù)很少能大到擁有100位以上，所以這個(gè)遞歸算法的運(yùn)行效率會(huì)很高，加上這個(gè)程序從上到下讀下來和我前面說的基本思想非常的符合，比較符合人的邏輯思維習(xí)慣，增加了程序的可讀性。所以說，遞歸并不是像有些書里面說的那樣，效率低，一般情況下盡量不要用，任何一樣?xùn)|西都沒有絕對(duì)的好壞，只有你有沒有用到適合的地方。

      ***，一個(gè)經(jīng)常遇到的問題是不是任何遞歸都能轉(zhuǎn)換成為非遞歸的程序呢？答案是可以的，只要你運(yùn)用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，都能轉(zhuǎn)換成為非遞歸程序，但是轉(zhuǎn)換的過程并沒有那么的簡(jiǎn)單，所以將遞歸轉(zhuǎn)換成為非遞歸，有時(shí)候還是需要一定的數(shù)學(xué)知識(shí)的。