摘要：算法的運行時間用大表示法表示。事實上還有另一種算法即也就是階乘算法。五選擇排序算法在理解選擇排序算法的原理之前，我們需要了解大表示法，數組與鏈表等概念。這種辦法，我們暫且稱之為預留座位。

任何代碼片段都可以被稱作是算法,這也就是說算法其實就是完成一組任務的指令.算法的優點在于要么速度很快,要么解決一些很有趣的問題,要么兼而有之.并且算法可以應用于任何編程語言中.

學算法的人必須要懂得一定的數學知識,具體點就是線性代數的知識.只要你能做出這樣一道題,那么恭喜你,可以學算法.

f(x) = x * 10;f(5) = ?;

假設存在一個有序列表,比如1,2,3...100.如果我要你猜測我心中所想的數字是這個有序列表中的哪個數字,你會怎么猜呢?

最簡單的辦法就是從1到100挨著猜,這樣一算,那么很明顯,假如我想的是數字100,你有可能就要猜100次.如此一來,豈不是很浪費時間.

那么,同樣的道理,如果在一行有100個字符的字符串中查找某個字母,你是不是也要查找100次呢?

其實有更快速的辦法,就第一個例子而言,試想,如果我們第一次就把100拆一半,也就是50,然后猜測50,根據我的回答來做下一步的確定.也許我回答小了,那么猜測的范圍就會在50到100之間了,如果是大了,那么猜測的范圍也就到了1到50之間,依次類推,我們把每次猜測都分成一半,即100 -> 50 -> 25 -> 13->7->4->2->1,如此一來,我們最多猜7次就能猜中我心中想的數字.

像這樣的把元素分一半來查找就叫二分查找.而通過二分查找實現的算法就叫二分算法,簡稱二分法.

一般地,我們把包含n個元素的列表,用二分查找最多需要log2^n步.

也許你可能不記得對數的概念了,但你應該記得冪的概念.而對數log10^100相當于將多少個10的乘積結果為100.答案自然是2個,即10*10=100.因此log10^100 = 2;

總的來說,對數就是冪運算的逆運算.

僅當列表有序的時候,我們才可以用二分法來進行查找嗎?那倒不一定,其實我們可以將這些列表的元素存儲在一個數組中,就好像,我們把一個東西放在桶里一樣,然后給這些桶標上順序,而順序則是從0開始編號的,第一個桶是0,第二個桶是1,依次類推.

比如有這樣一個有序數組[1,2,3...100];我想要查找75這個數字的索引,很明顯75這個數字對應的索引就是74.我們可以使用二分法編寫代碼,如下(這里以JavaScript代碼為例,其它語言的代碼也可以的):

var arr = [];
for(var i = 1;i <= 100;i++){
    arr.push(i);
}
var checknum = 75;
//定義第一個索引與最后一個索引
var low = 0;
var high = arr.length - 1;
//我們查找數字只能在兩者之間查找,使用循環,只要范圍沒有縮小到只剩一個元素,都可以繼續使用二分法拆成一半來查找
while(low <= high){
    //索引取一半,如果不是整數則向下取整
    var center = Math.floor((low + high) / 2);
    //最終結果一定是索引所對應的元素
    var result = arr[center];
    //判斷結果是否等于想要的結果
    if(result === checknum ){
        console.log(center);
    }else if(result < checknum){
            //如果取得索引對應元素值小于猜的值,則修改最低索引的值,以縮小猜測范圍
            low = center + 1;
    }else if(result > checknum){
            //如果取得索引對應元素值大于猜的值,則修改最大索引的值,以縮小猜測范圍
            high = center - 1;  
    }else{
        console.log(null);
    }
}

得出最終結果就是74.

我以如下圖來展示上例代碼的算法:

如此一來，我們還可以封裝成一個函數，參數為數組和數組元素對應的值.如下:

function  getArrIndex(arr,result){
    var low = 0,high = arr.length - 1,center = Math.floor((low + high) / 2);
    while(low <= high){
        if(arr[center] === result){
            return center;
        }else if(arr[center] < result){
            low = center + 1;
        }else if(arr[center] > result){
            high = center - 1;
        }else{
            return "沒有這個索引值";
        }  
    } 
}
//測試
getArrIndex([1,4,6,8,10],6);//2

在前面,我總結到二分算法,并且在二分算法中也提到過運行時間.一般說來,我們在寫程序時都會選擇效率最高的算法,以最大限度的減少運行時間或者占用空間.

前面二分算法中說到,如果挨著簡單的查找從1到100的列表,最多需要猜測100次,如果列表的長度更大呢?比如是1億,那我們就要猜測1億次.換句話說,最多需要猜測的次數與列表長度相同,這樣所用到的時間,我們稱之為線性時間.

而二分查找則不同,100次我們僅需猜測log2^100 ≈ 7次.而如果是1億,我們也只需猜測log2^100000000 ≈ 26次.這樣通過二分查找所需要的時間,我們稱之為對數時間.

我們可以利用一種特殊的表示法來表示這種運行時間,即大O表示法.大O表示法指出算法的速度有多快.

在了解什么是大O表示法之前,我們先來看一個例子:

假設有100個元素的列表,我們使用二分查找大約需要7次(因為log2^100≈7),如果每一次大約為1毫秒.二分查找就需要7毫秒,而簡單查找呢?簡單查找就需要100毫秒,大約是二分查找的15倍左右.

那么假如有1億個元素的列表呢,使用簡單查找就是大約1億毫秒,而二分查找則需要26毫秒(log2^100000000)左右就可以了.如此一來,簡單查找比二分查找慢的多,而且簡單查找足足是二分查找的將近400萬倍.

這說明一個什么問題呢?

這說明算法的運行時間是以不同的速度增加的,也就是說隨著元素的增多,二分查找所需要的額外時間并不多,而簡單查找卻要多很多.我們把這種情況稱之為增速.僅僅知道算法的運行時間是不行的,我們還需要知道運行時間隨著列表的增加而增加,即增速,大O表示法的用武之地就在于此.

一般的,擁有n個列表,簡單查找需要執行n次操作,我們用大O表示法表示為O(n).當然單位不一定是毫秒或者秒,大O表示法也就指出了算法的增速.而使用二分查找,我們可以表示為O(log2^n).

再比如一個示例:假設我們要畫一個16X16的網格圖,簡單查找就是一個一個的畫,結果需要畫256次.而如果我們把一張紙對折,再對折,再對折,再對折,每對折一次,格子數就會增加,對折一次畫一次,如此一來,頂多需要log2^256,也就是8次就可以畫出來.

我們用大O表示法,就可以表示成:簡單查找為O(n)的運行時間,而O(log2^n)則是二分查找所需時間.

大O表示法指出了最糟情況下的時間.什么意思呢?再看一個示例:

如果你要在一本書中使用簡單查找查找一篇文章,所需要的時間就是O(n).這意味著在最糟糕的情況下,必須查找一本書中的每一頁.如果要查找的文章剛好在第一頁,一次就能找到,那么請問簡單查找的運行時間是O(1)還是O(n)呢?
答案自然是O(n)呢.因為大O表示法指出了最糟糕情況下的運行時間.如果只用1次就能翻到,那這是最佳情況.

從這些案例當中,我們得出了如下結論:

1.算法的速度指的并非時間,而是增速。
2.談論算法的速度時,我們應該說的是隨著速度的增加,運行時間將以什么樣的速度增加。
3.算法的運行時間用大O表示法表示。
4.O(log2^n)比O(n)快,當搜索的元素越多,前者快的越多。

事實上,還有另一種算法.即O(!n).也就是階乘算法。來看一個案例:假如一個人要去4個城市旅行,并且還要確保旅程最短.利用排列與組合的知識得出,前往4個城市大約需要執行24次操作,而如果是5個城市,則大約需要執行120次操作.也就是說隨著城市的增加,大約需要執行!n次操作.雖然這確實是一種算法,但這種算法很糟糕。

在理解選擇排序算法的原理之前，我們需要了解大O表示法，數組與鏈表等概念。

經常與計算機接觸，相信都會聽到內存這一個詞，那么何為內存呢？我們用一個很形象的比喻來說明這個問題。

假設有一個柜子，柜子有很多抽屜，每個抽屜能放一些東西。也就是說，當我們往抽屜里放東西的時候，柜子就保存了這些東西。一個東西放一個抽屜，兩個東西放兩個抽屜。計算機內存的工作原理就如此，計算機的內存更像是許多抽屜的集合。

需要將數據存儲到計算機中，你會請求計算機提供存儲空間，然后計算機就會給你一個存儲地址。在存儲多項數據的時候，有兩種數據結構，計算機可以存儲，那便是數組和鏈表。

數組就是一系列元素的列表集合。比如，你要寫一個待辦事項的應用程序（前端術語也可以說是todolist）。那么你就需要將許多待辦事項存儲到內存中。使用數組意味著內存是緊密相連的，為何如此說呢？

數組的元素自帶編號，每個元素的位置，我們也叫做索引。例如:

[10,20,30,40]這一個數組，元素20的索引或者說所處的位置是1。因為數組的編號都是從0開始的，這可能會讓很多新手程序員搞不明白。幾乎所有編程語言對數組的編號都是從0開始的，絕對不止JavaScript這一門語言。

假設，你要為以上[10,20,30,40]再添加一個元素，很明顯，利用JavaScript提供的數組方法，你只能在之前或者最末又或者中間插入元素。但在內存中卻不是這樣。還是用一個比喻來說明。

相信每個人都有看電影的經歷，試想當你到了電影院之后，找到地方之后就坐下，然后你的朋友來了，本想靠著你坐，但是靠著你的位置都被人占領了。你的朋友就不得不轉移位置，在計算機中，請求計算機重新分配一個內存，然后才能轉移到另一個位置。如此一來，添加新元素的速度就會很慢。

那么，有沒有辦法解決呢？

似乎，很多人都這樣做過，由一個人占領位置之后，然后把旁邊的預留座位也給占領，不僅僅是在電影中，在公交車上搶座位也是如此。這種辦法，我們暫且稱之為"預留座位"。

這在計算機中也同樣適用。我們在第一次請求計算機分配內存的時候，就請求計算機分配一些空余的內存，也就是"預留座位"出來。假定有20個"預留座位"，這似乎是一個不錯的措施。但你應該明白，這個措施，也存在缺點:

你額外請求的位置有可能根本就用不上，還將浪費內存。比如你選了座位，結果你的朋友沒有來，其他人也不知道你的朋友不會來，也就不會坐上去，那么這個座位就空下來了。

如果來的人超過了20個之后，你預留的座位又不夠，這就不得不繼續重新請求轉移。

針對這種問題，我們可以使用鏈表來解決。

鏈表也是一種數據結構，鏈表中的元素可存儲在內存的任何地方。并且鏈表中 每一個元素都存儲了下一個元素的地址，從而使一系列隨機的內存串聯在一起。

這就好像一個掃雷游戲，當你掃中一個，這個就會提醒你的四周格子有沒有地雷，從而好作判斷，讓你是否選擇點擊下一個格子。因此，在鏈表中添加一個元素很容易：只需要將元素放入內存，并將這個元素的內存存儲地址放到前一個元素中。

而且，使用鏈表還不用移動元素。因為只要有足夠的內存空間，計算機就能為鏈表分配內存。比如如果你要為數組分配100個位置，內存也僅有100個位置，但元素不能緊靠在一起，在這樣的條件下，我們是無法為數組分配內存的，但鏈表卻可以。

鏈表好像自動就會說，“好吧，我們分開來坐這些位置”。

但鏈表也并非沒有缺點。我們再做一個比喻：

假如你看完了一本小說的第一章覺得第一章不好看，想跳過幾章去看，但并沒有這樣的操作，因為一般都是下一章下一章的看的，這意味著你要看第五十章，就要點下一章49次，這樣真的很煩。（點目錄不算）

鏈表也正是存在這一個問題，你在讀取鏈表的最后一個元素時，你需要先讀取上一個元素的存儲地址，然后根據上一個元素的地址來讀取最后這個元素。如果你是讀取所有的元素，那么鏈表確實效率很高，但如果你是跳躍著讀取呢？鏈表效率就會很低。

這也正是鏈表的缺點所在。但數組就不同，因為數組有編號，意味著你知道數組每個元素的內存地址，你只需要執行簡單的數學運算就能推算出某個元素的位置。

利用大O表示法，我們可以表示將數組和鏈表的運行時間表示出來，如下:

      數組   鏈表
讀取: O(1)    O(n)
插入: O(n)    O(1)

其中O(1)稱作常量時間，O(n)則是線性時間。

如果你要刪除元素呢？鏈表顯然也是更好的選擇，因為你只需要修改前一個元素指向的地址即可。

那么問題來了，數組與鏈表究竟哪種數據結構用的最多呢？

要看情況。但數組顯然用的更多，因為數組支持隨機訪問。元素的訪問有兩種方式：順序訪問與隨機訪問。順序訪問意味著 你需要挨著順序一個一個的訪問元素，而隨機訪問則不必如此。因為數組有編號，所以在隨機訪問上，數組更能體現它的優勢。

有了前面的知識，現在，咱們來學習選擇排序算法吧！
假設你的計算機存儲了一些視頻，對于每個視頻的播放次數，你都做了記錄，比如:

視頻1:50
視頻2:35
視頻3:25
視頻4:55
視頻5:60

現在，你要做的就是將播放次數從少到多按順序排列出來。該如何做呢？

首先，你肯定需要遍歷這個列表，找出播放次數最少的，然后添加到新的一個列表中去，并將這個添加的元素在原來列表中刪除，然后，你再次這樣做，將播放次數第二少的找出來，依次類推……

最后，你就會得到一個有序列表

視頻3:25
視頻2:35
視頻1:50
視頻4:55
視頻5:60

編寫代碼如下:

//用一個數組表示播放次數即可
var arr = [50,35,25,55,60];
// 編寫一個函數，參數傳入排序的數組
function selectSort(arr){
    //獲取傳入數組的長度
    var len = arr.length;
    //定義最小索引與數組每一項元素變量
    var minIndex,ele;
    for(var i = 0;i < len;i++){
            //最小索引等于當前i值，相當于初始化值
            minIndex = i;
            //初始化每一項
            ele= arr[i];
         for(var j = i + 1;j < len;j++){
                //獲取相鄰數，比較大小，得到最小數索引
                if(arr[j] < arr[minIndex]){
                        minIndex = j;
                }
         }
         //將得到的最小數排列在最前面
        arr[i] = arr[minIndex];
        //與最小數做比較的值放在最小數所處的位置
        arr[minIndex] = ele;
    }
    return arr;
}
//測試:
selectSort(arr);//[25,35,50,55,60]

下面我們來測試一下代碼運行時間。對每個元素進行查找時，意味著每個元素都要查找一次，所以運行時間為O(n),需要找出最小元素，又要檢查每個元素，這意味著又要O(n)的運行時間。因此需要的總時間為O(nxn)=O(n^2)。這也就是說，需要執行n次操作。

選擇排序只是一種很靈巧的算法，但還稱不上速度最快，速度最快的是快速排序法。

JavaScript遞歸一直讓許多開發者又愛又恨,因為它很有趣但也很難.最經典的莫過于一個階乘函數呢,如下:

function fn(num){
    if(num <= 1){
       num = 1;
    }else{
       num = num * fn(num - 1);
    }
    return num;
}
fn(5);//5*4*3*2*1= 120

面對如上的一個結果,許多開發者不免疑惑,為何會是這樣的結果.這個咱們暫且不解釋,咱們先來用一個生活中常見的例子來分析:

假設有一個盒子,盒子里面又包含盒子,盒子里面再包含盒子,一直包含n個盒子,那第n個盒子中有一本書.如果讓你找到這本書,你會如何查找?

以下是一個示意方法:

首先是定義一個盒子:

var box = {
        box:{
            box:{
                box:{
                    ......
                }
            }
        }
}

其次只要盒子不空,我們就取出一個盒子,如下:

if(box !== {}){
   box = box.box;
}

現在,咱們再來做判斷,如果取出的盒子里面存在書,那么說明已經找到了,不必在繼續取盒子,即:

//假定書變量
var book = "book";
if(box !== {}){
        box = box.box;
        if(box === book){
             console.log("已經找到了")!
        }else{
             box = box.box.box;
             //......
        }
}

可如果不是書,那么就繼續取盒子,即如上的else代碼塊中的語句.

通常,咱們可以用一個循環來完成這樣的操作,如下:

var box = {
   // ......
}
var book = "book";
for(var key in box){
        if(box !== {}){
                box = box[key];
                if(box[key] === book){
                  console.log("已經找到了");
                }else{
                    box[key] = box[key][key]
                    //......
                }
        }
}

但似乎這樣做有很大的缺點,因為一旦涉及到最里面層數太多,則需要循環n次.這不太合適,結果會取決于循環.因此,我們可以定義一個函數,然后為函數傳參,反復的讓函數自己調用自己,這樣,結果就取決于程序而不是循環了.如下:

//傳入box對象
var box = {
    //......
}
var book = "book";
function checkOutBook(box){
    //遍歷box對象
    for(var key in box){
        if(box !== {}){
                if(box[key] === book){
                    console.log("找到了");
                }else{
                     //反復調用函數,直到找到書為止
                    box = checkOutBook(box[key]);
                }
        }
    }
}

如此一來,遞歸的原理我們就能清楚了,遞歸就是層層遞進,反復的調用自己,就拿函數來說,就是反復的調用自己,直到條件不滿足時,則遞歸停止.

現在,咱們再來分析以上的階乘函數:

函數需要傳入一個數值參數,然后我們對這個參數做判斷,如果這個參數小于等于1,則讓這個參數等于1.如果不滿足,則執行這個參數,等于這個參數與這個參數減1的乘積.

fn(5) => 這意味著num = 5=>num=5 <= 1 (條件不成立) => num = 5 * fn(4) => 

num = 4 => num = 4 <= 1(條件不成立) => num = 5 * 4 * fn(3) => num = 3 => num = 3 <= 1(條件不成立) => num = 5 * 4 * 3 * fn(2) => num = 2 => num=2 <= 1(條件不成立) => num = 5 * 4 * 3 * 2 * fn(1) => num = 1 => num = 1 <= 1(條件成立) => num = 1 => 最終結果就是num = 5 * 4 * 3 * 2 * 1 = 120;

結合最后return語句返回num,則不難得出結果.我們嘗試用循環來完成階乘:

function fn(num){
        var i = 0,result = 1;
        while(i < num){
              if(i <= 1){         
                   i = 1;
               }else{
                    result *= i;
               }      
         }
        return result;
}
fn(5);//120

就性能上而言,遞歸并不比循環好,但遞歸勝在比循環更好理解.也就是說遞歸更容易讓程序被人理解.

遞歸函數有什么特點呢？

我們來看一個遞歸函數:

function fn(){
   var i = 10;
   console.log(i);
   fn(i - 1);
}

運行如上的函數,你會發現程序會一直無限循環下去,直到死機都還會運行.因此,在編寫遞歸算法的時候,我們要告訴程序何時停止遞歸.

遞歸有兩個條件:基線條件和遞歸條件.遞歸條件指的就是函數調用自己,而基線條件則指的是停止遞歸的條件,如函數不再調用自己.

比如:

function fn(){
  var i = 10;
  console.log(i);
  //基線條件
  if(i <= 1){
     i = 1;
   }else{
    //遞歸條件
     fn(i - 1);
   }
}

棧:棧是一種數據結構,前面講到數組和鏈表的時候,曾說過,元素的插入,刪除和讀取.其中插入也被稱作是壓入,刪除和讀取也被叫做彈出.而這種能夠插入并能夠刪除和讀取的數據結構就叫棧.也就是說數組是一種棧,鏈表也是一種棧.

就拿如上的示例來說:

function fn(){
  var i = 10;
  console.log(i);
  //基線條件
  if(i <= 1){
     i = 1;
   }else{
     //遞歸條件
     fn(i - 1);
   }
}

變量i被分的一塊內存,當每次調用函數fn()的時候,而每次i都會減一,這也意味著每次都會分的一塊內存.計算機用一個棧來表示這些內存,或者也可以說是內存塊.當調用另一個函數的時候,當前函數就已經運行完成或者處于暫停狀態.

棧被用于存儲多個函數變量,也被叫做調用棧.雖然我們不必跟蹤內存塊,由于棧已經幫我們做了.再來看一個簡單的示例:

function greet(){
   console.log("hello");
}
greet();
function bye(){
    console.log("bye");
}
bye();

首先調用函數greet(),后臺就會創建一個變量對象,打印出"hello"字符串,此時棧被調用.也存儲了一個變量對象,相當于該字符串被分了一塊內存.緊接著調用bye()函數,也被分配了一個內存.

雖然使用棧很方便,但也有缺點,那就是不要使用棧存儲太多的信息,因為這可能會占用你電腦很多內存.

算法中有一個重要的思想，那就是分而治之（D&C，divide and conquer），這是一種著名的遞歸式問題解決方法。

理解分而治之，意味著你將進入算法的核心。快速排序算法是這個思想當中第一個重要的算法。

我們舉一個示例來說明這個思想。

假設要將一個長為1000，寬為800的矩形分成均勻的正方形，并保證這些正方形盡可能的大。

我們應該如何做呢？

我們可以使用D&C策略來實現,D&C算法是遞歸的。要解決這個問題，我們需要將過程分為兩個步驟。如下:

找出D&C算法的基線條件，條件要盡可能的簡單。

不斷將問題分解，直到滿足基線條件為止。

我們知道如果將長1000，寬800的長方形分成最大的正方形應該是800x800。然后余下200X800的長方形。按照相同的分法，我們又可以將其分為200X200正方形與200X600的長方形，然后再分為200X200與200X400的正方形與長方形，最后實際上最大的并且均勻的正方形就是200X200的正方形。

第一次講到的二分查找其實也是一種分而治之的思想。我們再來看一個例子:

假設有一個[2,4,6]的數組。你需要將這些數字相加，并返回結果。使用循環可能很容易解決這個問題，如下:

var arr = [2,4,6],total = 0;
for(var i = 0;i < arr.length;i++){
    total += arr[i];
}

但如何使用遞歸算法來實現呢？

首先，我們需要找出這個問題的基線條件。我們知道如果數組中沒有元素，那就代表總和為0，如果有一個元素，那么總和就是這個元素的值。因此基線條件就出來了。

每次遞歸調用，我們都會減少一個元素，并且離空數組或者只包含一個元素的數組很近。如下:

sum([2,4,5]) => 2 + sum([4,6]) => 2 + 4 + sum([6]) => 2 + 4 + 6 = 12

因此，我們可以編寫如下的代碼:

//基線條件
if(arr.length <= 1){
    //求和
}else{
    //遞歸
}

現在，讓我們來看完整的代碼吧:

function sum(arr,res){
    if(arr.length <= 1){
        return res + arr[0];
    }else{
        res += arr.splice(0,1)[0];
        return total(arr,res);
    }
}
//測試sum([2,4,6],0)=>12

你可能會想，能夠使用循環輕易的解決問題的，干嘛還要使用遞歸。如果你能理解函數式編程，那么就明白了。因為函數式編程并沒有循環的說法，而實現求和的方式只能是使用遞歸算法。

前面之所以會提到分而治之思想,是因為接下來的快速排序算法需要按照這種思想去理解.快速排序算法比選擇排序算法(也被叫做冒泡排序算法)快的多.我們需要知道,什么樣的數組需要進行排序,什么樣的數組不需要進行排序.很顯然當數組沒有元素或者只有一個元素時,我們無需對數組進行排序.

空數組:[]
只有一個元素的數組:[2];

像如上的數組,我們沒必要排序,因此接下來的函數中,我們可以如此寫:

function quickSort(arr){
    if(arr.length < 2){
        return arr;
    }
}

當數組的元素超過兩個呢,比如[12,11].我們可能都會這樣想,檢查第一個元素是否比第二個元素大,然后確定是否交換位置.而如果是三個元素呢,甚至更多元素呢?我們是否還能這樣做呢?

我們可以采用分而治之的思想,即D&C策略.將數組分解.直到滿足基線條件.這也就是說,我們會采用遞歸原理來實現.快速排序算法的工作原理就是從數組當中選擇一個元素,這個元素也被叫做基準值.

然后我們就可以根據這個基準值找出比基準值大或者比基準值小的元素,這樣被稱作分區.進行分區之后,你將會得到:

一個比基準值小而組成的子數組.
一個包含基準值的數組.
一個比基準值大而組成的子數組.

當然這里得到的所有子數組都是無序的,因為如果得到的是有序的,那么排序將會比較容易.直接將分解后的數組利用concat()方法給合并,就能得出排序結果呢.

基準值的選擇是不確定的,這也就意味著你可以選擇最中間的數,也可以選擇第一個數,甚至是最后一個數都可以.比如一個數組[5,2,3,1,4];

數組當中的五個元素你都可以當作基準值,而每一個基準值所分區出來的子數組也會有所不同.

我們通過以上的多種類推和歸納就能得出最終的結果.而這種證明算法行之有效的方式就叫做歸納證明.歸納證明結合快速排序算法,可以讓我們的算法變得生動有趣.

現在,我們來實現快速排序的算法吧,代碼如下:

function quickSort(arr){
    //定義一個空數組接收排序后的數組
    var newArr = [];
    //當數組的長度小于2時,不需要進行排序
    if(arr.length < 2){
        return arr;
    }else{
        //定義一個基準值,這里就取中間值吧
        var standIndex = Math.floor(arr.length / 2);//由于可能數組長度不是偶數,所以,需要取整
        //使用基準值所對應的元素值,由于要最后合并三個數組所以這里采用splice()方法取得基準值所組成的數組
        var standNum = arr.splice(standIndex,1);
        //接下來,我們需要定義兩個空數組,用于保存以基準值作為分區的最小子數組和最大子數組
        var minArr = [],maxArr = [];
        //循環數組將每一個元素與基準值進行比較,小則添加到最小子數組中,大則添加到最大子數組中
        for(var i = 0,len = arr.length;i < len;i++){
                if(arr[i] < standNum){
                    minArr.push(arr[i]);
                }else{
                    maxArr.push(arr[i]);
                }
        }
        //循環完成之后合并三個子數組,當然這里需要遞歸合并,直到數組長度小于2為止
        newArr = quickSort(minArr).concat(standNum,quickSort(maxArr));
    }
    //返回合并后的新數組
    return newArr;
}
//測試
quickSort([1,3,2,4,5]);//[1,2,3,4,5]

快速排序算法的獨特之處在于，其速度取決于選取的基準值。在討論快速排序算法的運行時間之前，我們來大致討論一下常見算法的大O運行時間:

執行10次操作計算得到的，當然這些數據并不準確，之所以提供，只是讓我們對這些運行時間的差別有一個認識。事實上，計算機每秒執行的操作遠不止如此。(另外還要注意一下關于時間復雜度對數的底數，是不太確定的，比如二分法，底數有可能是2，也有可能是3，視情況而定)。

對于每種運行時間，都會有相關的算法。比如前面所說的選擇排序算法，它的運行時間就是O(n^2)，所以速度很慢。

當然還有一種合并排序算法，它的運行時間是O(nlogn),比選擇排序算法快的多，快速排序算法則比較棘手，因為快速排序算法是根據基準值來判定的，在最糟糕的情況下，快速排序算法的運行時間和選擇排序算法運行時間是一樣的，也是O(n^2)。

當然在平均情況下，快速排序算法又和合并排序算法的運行時間一樣，也是O(nlogn)。

到此為止，也許有人會有疑問？這里的最糟情況和平均情況究竟是什么呢？如果快速排序算法在平均情況下的運行時間是O(nlogn)，而合并排序算法的運行時間總是O(nlogn),這不就是說合并排序算法比快速排序算法快嗎？那為何不選合并排序算法呢？

當然我們在做合并排序于快速排序算法的比較之前，我們需要先來談談什么是合并排序算法。

合并排序算法也叫歸并排序算法。其核心也是分而治之的思想，與二分法有點類似，先將數組從中間分開，分成兩個數組，依次類推，直到數組的長度為1時停止。然后我們向上回溯，形成一個有序的數組，最后合并成一個有序的數組。

現在，來看歸并排序算法實現的代碼吧。

function mergeSort(arr) {
        // 如果數組只有一個元素或者無元素則無須排序
        if (arr.length <= 1) {
          return arr;
        }
        var mid = Math.floor(arr.length / 2), //取中間值，將數組截取成2個數組
          left = arr.slice(0, mid),
          right = arr.slice(mid);
        var newArr = [],
          leftArr = mergeSort(left), //這里是最關鍵的一步，將左右數組遞歸排序，直到長度為1時，然后合并.
          rightArr = mergeSort(right);
        //判斷如果兩個數組的長度都為1，則比較第一個元素的值，然后添加到新數組中去
        while (leftArr.length && rightArr.length) {
          if (leftArr[0] < rightArr[0]) {
            newArr.push(leftArr.shift());
          } else {
            newArr.push(rightArr.shift());
          }
        }
        return newArr.concat(leftArr, rightArr);
 }
//測試
console.log(mergeSort([1, 3, 2, 4, 6, 5, 7]));

理解了合并排序算法，現在我們就來比較一下快速排序算法和合并排序算法吧。

我們還是先來看一個示例，假設有如下一個函數:

var list = [1,2,3,4,5];
function printItem(list){
    list.forEach(function(item){
        console.log(item);
    })
}
printItem(list);

以上定義了一個函數，遍歷一個數組，然后將數組的每一項在控制臺打印出來。既然它迭代了數組列表每個數組項，那么運行時間就是O(n)。現在，我們假設每延遲1s再打印出數組每一項的值,如下:

var list = [1,2,3,4,5];
function printAfterItem(list){
    list.forEach(function(item){
        setTimeout(function(){
            console.log(item);
        },1000)
    })
}
printItem(list);

第一次，我們知道，打印1，2，3，4，5。而延遲1s打印了之后，則會延遲1s,1,延遲1s,2,延遲1s,3,延遲1s,4,延遲1s,5。這兩個函數都是迭代了一個數組，因此它們的運行時間都是O(n)。那么，很顯然printItem()函數更快，因為它沒有延遲，盡管大O表示法表示這兩者的速度相同，但實際上卻是printItem()更快，在大O表示法O(n)中的n實際上就是指這樣的忽略常量的運行時間。

在這里我們可以定義常量為c，c也就是算法當中的固定時間量，比如上例的1s就是固定的時間量，也被稱為是常量。當然第一個函數printItem()也有可能有一個時間常量，比如:10ms * n,而延遲1s之后的printAfterItem()則是:1s * n;

哪個函數的運行速度快自然一目了然。通常來說，是不會考慮這種常量的，因為對于兩種算法的大O運行時間不同，這種常量造成的影響無關緊要。就比如二分查找和簡單查找。假設二分查找有常量:n * 1s,而簡單查找有常量:10ms * n;好，如果根據這個常量來看，也許會認為簡單查找的常量是10ms就快得多，但事實上是這樣嗎?

比如在包含40億個元素列表中查找某個元素，對于二分查找和簡單查找所需時間如下:

簡單查找:10ms * 40億,大約463天。
二分查找:1s * log40億，大約是32秒。

正如你所看到的，二分查找還是快的多，常量幾乎可以忽略不計。

可是有的時候，常量又可能造成巨大的影響，對于快速排序算法和合并排序算法來說，就是如此。實際上快速排序算法的常量比合并排序算法的常量小，因此如果它們的運行時間都是O(nlogn)。那么很顯然快速排序算法要更快，盡管快速排序算法有平均情況和最糟情況之分，但實際上平均情況出現的概率要遠遠大于最糟情況。

到此為止，也許有人會有疑問，什么是平均情況?什么又是最糟情況?

快速排序算法的性能高度依賴于選擇的基準值，假設你選擇數組的第一個元素作為基準值，并且要處理的數組是有序的。由于快速排序算法并不檢查輸入的數組是否有序，它依然會嘗試進行排序。

[1,2,3,4,5,6,7,8]
   ↓
[](1)[2,3,4,5,6,7,8]
   ↓
[](2)[3,4,5,6,7,8]
   ↓
[](3)[4,5,6,7,8]
   ↓
[](4)[5,6,7,8]
   ↓
[](5)[6,7,8]
   ↓
[](6)[7,8]
   ↓
[](7)[8]

這樣一來，每次都會選擇第一個元素作為基準值，就會調用棧8次，最小子數組也始終是空數組，這就導致調用棧非常的長。再來看選擇中間元素作為基準值是什么情況呢?

[1,2,3,4,5,6,7,8]
   ↓
[1,2,3](4)[5,6,7,8]
   ↓          ↓
[1](2)[3]  (6)[7,8]
              ↓
           [](7)[8]

因為每次都將數組分成兩半，所以不需要那么多的遞歸調用。很快就達到了遞歸的基線條件，因此調用棧就短的多。

第一個示例就展示了最糟情況，而第二個示例則展示的是最佳情況。在最糟情況下，棧長為O(n),在最佳情況下，棧長就是O(logn)。

現在來看看棧的第一層，將一個元素作為基準值，并將其它元素劃分到兩個子數組中去，這就涉及到了數組的8個元素，因此該操作時間就是O(n)。實際上棧的每一層都涉及到了O(n)個元素，因此運行時間也是O(n)。即便是最佳情況選擇數組的中間值來劃分，棧的每一層也一樣涉及到O(n)個元素，因此完成每層所需時間都是O(n)。唯一不同的地方則是第一個示例調用棧的層數是O(n)[從技術術語來說，也就是調用棧的高度是O(n)],而第二個示例調用棧的高度則是O(logn),因此整個算法所需的時間就是O(n) * O(logn) = O(nlogn),而第一個示例所需的時間就是O(n)*O(n) = O(n^2)。這就是最佳情況與最糟情況所需的運行時間。

在這里，我們需要知道的就是最佳情況被看作是平均情況的一種，只要每次隨機的選擇一個元素作為基準值，那么快速排序的平均運行時間就是O(nlogn)。也正因為如此，快速排序算法在平均情況下，常量比合并排序算法小，也因此快速排序算法就是最快的排序算法之一，也是D&C典范。

鄙人創建了一個QQ群，供大家學習交流，希望和大家合作愉快，互相幫助，交流學習，以下為群二維碼：