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

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

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

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

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

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

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

插入排序
大白話：首先對(duì)前兩個(gè)數(shù)據(jù)從小到大比較。接著將第三個(gè)數(shù)據(jù)與排好的前兩個(gè)數(shù)據(jù)比較，將第三個(gè)數(shù)據(jù)插入合適的位置。以此類推。(插入排序有兩個(gè)循環(huán)，外循環(huán)將數(shù)組挨個(gè)移動(dòng)，內(nèi)循環(huán)將對(duì)外循環(huán)選中的元素及他前面的數(shù)進(jìn)行比較。)
時(shí)間復(fù)雜度：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
分析
(插入排序有兩個(gè)循環(huán)，外循環(huán)將數(shù)組挨個(gè)移動(dòng)，內(nèi)循環(huán)將對(duì)外循環(huán)選中的元素及他前面的數(shù)進(jìn)行比較。)
插入排序的思路很簡單，很清晰，是一種最常見最簡單的排序方法,。但是可以看出，由于需要兩層循環(huán)，外層循環(huán)n-1次，內(nèi)層循環(huán)每次遞增一次。當(dāng)輸入完全從小到大有序時(shí)，只需要常數(shù)的時(shí)間，這當(dāng)然是最好的情況。但是我們不能期望輸入，當(dāng)輸入完全逆序時(shí)，最壞的情況就出現(xiàn)了，顯然時(shí)間復(fù)雜度是O(n*n)的。我們都很清楚，這個(gè)時(shí)間復(fù)雜度在排序中并不能算好的。這也是為什么插入排序雖然簡單，但并沒有被廣泛應(yīng)用的原因所在。

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

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

參考資料：
1.算法的時(shí)間復(fù)雜度
2.算法的時(shí)間復(fù)雜度分析
3.如何計(jì)算時(shí)間復(fù)雜度
4.js算法之最常用的排序
5.快速排序（Quicksort）的Javascript實(shí)現(xiàn)
6.排序算法——快速排序