摘要：算法之最常用的排序參加百度前端的課程真的是好多知識點不知道。快速排序也是在實際中最常用的一種排序算法，速度快，效率高。插入排序的思路很簡單，很清晰，是一種最常見最簡單的排序方法。

參加百度前端的課程真的是好多知識點不知道。邊學邊做題，在問題中學習，知識點從點到面，但是要善于總結記錄才行。加油吧，騷年！

時間復雜度是衡量一個算法效率的基本方法
我們把它記作：O(n)

大白話介紹：比較相鄰的兩個數，如果后面的比前面的小，把小的放在前面。
時間復雜度: O(n2)
動畫演示:冒泡算法
實際代碼：

（優化算法:如果數組已經是有序了，就沒必要再比較了）：
var arr=[5,3,2,4,1,0];
function bubbleSort(arr){
    var flag = false;  // 定義一個變量為false，未交換位置
    for(var i=0;i
優化方法設置一個中斷標志位，在條件測試中如果發生了交換就將中斷位屏蔽，然后在外層循環中檢查中斷位，如果中斷位沒有被屏蔽，將結束循環。每次開始內層循環之前重置中斷位。這樣就可以在已經是正序排列時不繼續進行循環，達到最優的復雜度.
計算時間復雜度主要是看這幾個指標：
1 input size(輸入)
2 basic operation/most costly operation(基本操作)
3 determine average cases(決定最壞和平均的時間)
4 sove it(計算)
在冒泡排序中的核心部分是
for(i=0;ifor(j=0;jif(a[j+1]
根據上面的步驟
1 size = n
2 basic operation = key comparison(比較)
因為比較是每次都要做的，而交換不一定每次都要做
3 average case = worst case
4 solve it
就是計算一共進行多少次比較這里就是用數學里的求和公式sigma求出來
最內層循環key comparison的次數是從0到n-i-1，外層循環i從0到n-1
所以總數是對(n-1-i)求和，i從0到n-1
(n-1)*n - （1+2+3+4+…+n-1）= n(n-1)/2 = O(n^2)
所以時間復雜度是n的平方

選擇排序
大白話介紹：先從原始數組中選擇一個最小的數據，和第一個位置1的數據交換。再從剩下的n-1個數據中選擇次小的數據，將其和第二個位置的數據交換。不斷重復，知道最后兩個數據完成交換。可以很清楚的發現，選擇排序是固定位置，找元素.
時間復雜度：O(n2)
動畫演示:選擇排序
實際代碼：
var arr=[5,3,2,4,1,0];
function selectionSort(array){
    var min,temp;
    for(var i=0; i
分析:
從選擇排序的思想或者是上面的代碼中，我們都不難看出，尋找最小的元素需要一個循環的過程，而排序又是需要一個循環的過程。因此顯而易見，這個算法的時間復雜度也是O(n*n)的。這就意味值在n比較小的情況下，算法可以保證一定的速度，當n足夠大時，算法的效率會降低。并且隨著n的增大，算法的時間增長很快。因此使用時需要特別注意。

快速排序
也是在實際中最常用的一種排序算法，速度快，效率高。就像名字一樣，快速排序是最優秀的一種排序算法。
大白話：
（1）在數據集之中，選擇一個元素作為"基準"（pivot）。
（2）所有小于"基準"的元素，都移到"基準"的左邊；所有大于"基準"的元素，都移到"基準"的右邊。
  （3）對"基準"左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。 
代碼：
 var arr=[77,-33,22,32,0,2,11];
    function quickSort(arr){
        if(arr.length<=1){ //如果數組中只有一位數，返回數組
            return arr;
        }
        var mNumIndex = Math.floor(arr.length/2); //取基準值的下標
        var mNum = arr.splice([mNumIndex],1)[0];  //取基準值
        var left = [];  //左邊數組
        var right = []; //右邊數組
        
        for(var i=0;i
分析
快速排序的時間主要耗費在劃分操作上，對長度為k的區間進行劃分，共需k-1次關鍵字的比較。
最壞情況是每次劃分選取的基準都是當前無序區中關鍵字最小(或最大)的記錄，劃分的結果是基準左邊的子區間為空(或右邊的子區間為空)，而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。時間復雜度為O(n*n)
在最好情況下，每次劃分所取的基準都是當前無序區的"中值"記錄，劃分的結果是基準的左、右兩個無序子區間的長度大致相等。總的關鍵字比較次數：O(nlgn)
盡管快速排序的最壞時間為O(n2)，但就平均性能而言，它是基于關鍵字比較的內部排序算法中速度最快者，快速排序亦因此而得名。它的平均時間復雜度為O(nlgn)。

插入排序
大白話：首先對前兩個數據從小到大比較。接著將第三個數據與排好的前兩個數據比較，將第三個數據插入合適的位置。以此類推。(插入排序有兩個循環，外循環將數組挨個移動，內循環將對外循環選中的元素及他前面的數進行比較。)
時間復雜度：O(n^2) 
代碼：
var arr=[5,3,2,4,1,0];
function insertSort(arr){
    var temp, j;
    for(var i=1; i0 && arr[j-1]>temp){
            arr[j]=arr[j-1];
            j--;
        }
        arr[j]=temp;

    }
    return arr;
}
document.write(insertSort(arr));  //0,1,2,3,4,5
分析
(插入排序有兩個循環，外循環將數組挨個移動，內循環將對外循環選中的元素及他前面的數進行比較。)
插入排序的思路很簡單，很清晰，是一種最常見最簡單的排序方法,。但是可以看出，由于需要兩層循環，外層循環n-1次，內層循環每次遞增一次。當輸入完全從小到大有序時，只需要常數的時間，這當然是最好的情況。但是我們不能期望輸入，當輸入完全逆序時，最壞的情況就出現了，顯然時間復雜度是O(n*n)的。我們都很清楚，這個時間復雜度在排序中并不能算好的。這也是為什么插入排序雖然簡單，但并沒有被廣泛應用的原因所在。

歸并排序（mergeSort）
大白話介紹：   把一個數組分為兩個數組，左邊排好序，右邊排好序，然后合并到一起排序
專業性介紹：   歸并排序是分治法的典型實例，指的是將兩個已經排序的序列合并成一個序列的操作
時間復雜度：   O(nlogn)
實際代碼：
   var arr=[-11,17,12,19,0,-222];
     function mergeSort(arr,s,e){
         if(s>e){   //起始位置大于終點位置，返回空數組
             return [];
         }else if(s==e){
             return [arr[s]]; //起始位置等于終點位置，說明數組里只有一個數字，返回只含一個數字的數組    
         }

         var mIndex = Math.floor((s+e)/2); //中間位置的Index
         var arrL = mergeSort(arr,s,mIndex); //將左邊的數組排序
         var arrR = mergeSort(arr,mIndex+1,e); //將右邊的數組排序
         
         var resultArr = []; //結果數組
         while(arrL.length>0 || arrR.length>0){ //當左右兩個數組都不為空時
             if(arrL[0]

參考資料：
1.算法的時間復雜度
2.算法的時間復雜度分析
3.如何計算時間復雜度
4.js算法之最常用的排序
5.快速排序（Quicksort）的Javascript實現
6.排序算法——快速排序