摘要：因為是在已經分組排序過的基礎上進行插入排序，所以效率高。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。形成左右兩個分區，再遞歸按之前的步驟排序。

不是科班生的我，第一次看見時間復雜度之類的名詞表示很懵逼，所以就找了網上的資料補習了下：

時間復雜度：是指執行算法所需要的計算工作量

空間復雜度：是指算法在計算機內執行時所需存儲空間的度量

排序算法穩定性： 假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩定的；否則稱為不穩定的。

這里不詳細說

參考：算法的時間復雜度和空間復雜度-總結、理解排序算法的穩定性、算法和算法的復雜度

名詞解釋：

n：數據規模

k：“桶”的個數

In-place：占用常數內存，不占用額外內存

Out-place：占用額外內存

下面的算法實現升序

顧名思義，從第一個開始比較相鄰的兩個，小的數網上冒。

function bubleSort (arr) {
    var len = arr.length;
    var temp;
    for (var i=0; i arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr
}

假設第一個最小， 往后尋找比它小的，記下其index，一輪結束后將index上的數與開始假定的數交換位置。

function selectionSort (arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i=0; i arr[j]) {
                minIndex = j
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

打撲克的同志應該比較好理解。假設第一個元素是已經排序好的，將后一個元素提取出來，往前依次比較，比自己大的數往后挪，插入到第一次遇見比自己小的元素后面，組成一個新的序列。

實現

function insertionSort (arr) {
    var len = arr.length;
    var current, preIndex;
    for (var i=1; i=0 && current < arr[preIndex]) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr
}

實質為分組插入排序。為了方便理解，借用網上某哥的圖，參考鏈接在下文。

因為是在已經分組排序過的基礎上進行插入排序，所以效率高。

實現

//因為核心是插入排序，所以我們改造直接插入排序
function directInsertionSort(arr, gap) {
    var len = arr.length;
    var current, preIndex;
    for (var i=gap; i=0 && arr[preIndex] > current) {
            arr[preIndex+gap] = arr[preIndex];
            preIndex -= gap;
        }
        arr[preIndex+gap] = current;
    }
    return arr;
}
//編寫希爾排序函數
function shellSort (arr) {
    var len = arr.length;
    var gap = 1;
    //設置gap（希爾增量），這里我們給出比較常用的h值為h = 3 * h + 1
    while (gap < len/3) {
        gap = gap * 3 + 1;
    }
    for (gap; gap>0; gap = Math.floor(gap/3)) {
        directInsertSort(arr, gap);
    }
    return arr;
}

遇見的問題，關于參數的傳遞：函數參數的傳遞可以分為按值傳遞和引用傳遞。
步長序列可以看一下wiki

類似直接插入，后一個元素（拿來比較的元素）與已排序的中間值m = (i-1) >> 1(位移運算，相當于Math.floor((i-1)/2))進行比較,如果i上的值大于m上的值，則與高半區折半比較,最終將比i上值高的區域往后移，將i上的值插入。如

arr = [2, 6, 7, 6, 8]   
//前三個是已經排好的。
//range = [low, high] = [0, 2], i = 3, current = arr[i]
// m = 1, arr[i] >= arr[m], rang = [2, 2]
// m = 2, arr[i] < arr[m]
// 變換位置 ==> arr = [2, 6, 6, 7, 8]
...
...

實現

function binaryInsertionSort (arr) {
    var len = arr.length;
    var low, height, current, m;
    for (var i=1; i> 1;
            if (current >= arr[m]) {// = 是為了保證穩定性
                low = m + 1;
            }else {
                height = m - 1;
            }
        }
        for (var j=i; j>low; j--) {
            arr[j] = arr[j-1];
        }
        arr[low] = current;
    }
    return arr;
}

采取分而治之的思想。遞歸分組、比較產生兩個已排序序列，再依次比較兩組開頭元素，較小的元素放入申請的新數組中。
歸并函數可以通過遞歸、迭代實現。

主要做的兩件事就是分解、合并(下面并不是按照執行順序，只是思路)：

          [3, 5, 6, 2, 9]
--------------------------------------
分：   [3, 5]         [6, 2, 9]  
     [3]  [5]      [6]   [2, 9]
                        [2]  [9] 
--------------------------------------
合：                      [2, 9]
       [3, 5]         [2, 6, 9]   
          [2, 3, 5, 6, 9]  

實現

function merge (left, right) {
    var result = [];
    while (left.length && right.length) {
        var item = left[0] <= right[0] ? left.shift() : right.shift();
        result.push(item);
    }
    return result.concat(left.length ? left : right);
}
function mergeSort (arr) {
    var len = arr.length;
    if (len === 1) {
        return arr;
    }
    var m = len >> 1;
    var left = arr.slice(0, m);
    var right = arr.slice(m);
    return merge(mergeSort(left), mergeSort(right))
}

遞歸可能會造成堆棧溢出的問題。

主要做的兩件事就是分解、合并(下面并不是按照執行順序，只是思路)：

          [3, 5, 6, 2, 9]
--------------------------------------
分：  [3]  [5]  [6]  [2]  [9] 
--------------------------------------
合：     [3, 5]  [2, 6]  [9]
           [2, 3, 5, 6] [9]
           [2, 3, 5, 6, 9] 

實現

function merge (left, right) {
    var result = [];
    while (left.length && right.length) {
        var item = left[0] <= right[0] ? left.shift() : right.shift();
        result.push(item);
    }
    return result.concat(left.length ? left : right);
}
function mergeSort (arr) {
    var len = arr.length;
    var result = [];
    //分組，每組有i個元素
    for (var i=1; i<=len; i*=2) {
        //比較相鄰兩組，有一組剩余就退出
        for (var j=0; j+i
快速排序
快速排序是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。  
步驟：選擇一個元素作為基準，下面選擇第一個，依次比較后面的元素，將小于基準的元素放在基準的左邊，剩余放右邊。形成左右兩個分區，再遞歸按之前的步驟排序。
實現
function swap (arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function partition (arr, left, right) {
    var pivot = left;
    var index = left + 1;
    for (var i=index; i<=right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, index, i);
            index++;
        }
    }
    swap(arr, index-1, pivot);
    return index-1
}
function quickSort (arr, left, right) {
    var len = arr.length;
    var partitionIndex;
    left = typeof left === "number" ? left : 0;
    right = typeof right === "number" ? right : len-1;
    if (left < right) {
        partitionIndex = partition (arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}
快速排序排序效率非常高. 雖然它運行最糟糕時將達到O(n2)的時間復雜度, 但通常, 平均來看, 它的時間復雜為O(nlogn), 比同樣為O(nlogn)時間復雜度的歸并排序還要快. 快速排序似乎更偏愛亂序的數列, 越是亂序的數列, 它相比其他排序而言, 相對效率更高.
Chrome的v8引擎為了高效排序, 在排序數據超過了10條時, 便會采用快速排序. 對于10條及以下的數據采用的便是插入排序.
參考
十大經典排序算法   
JS中可能用得到的全部的排序算法