摘要：因?yàn)槭窃谝呀?jīng)分組排序過(guò)的基礎(chǔ)上進(jìn)行插入排序，所以效率高。本質(zhì)上來(lái)看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。形成左右兩個(gè)分區(qū)，再遞歸按之前的步驟排序。

不是科班生的我，第一次看見時(shí)間復(fù)雜度之類的名詞表示很懵逼，所以就找了網(wǎng)上的資料補(bǔ)習(xí)了下：

時(shí)間復(fù)雜度：是指執(zhí)行算法所需要的計(jì)算工作量

空間復(fù)雜度：是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量

排序算法穩(wěn)定性： 假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

這里不詳細(xì)說(shuō)

參考：算法的時(shí)間復(fù)雜度和空間復(fù)雜度-總結(jié)、理解排序算法的穩(wěn)定性、算法和算法的復(fù)雜度

名詞解釋：

n：數(shù)據(jù)規(guī)模

k：“桶”的個(gè)數(shù)

In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存

Out-place：占用額外內(nèi)存

下面的算法實(shí)現(xiàn)升序

顧名思義，從第一個(gè)開始比較相鄰的兩個(gè)，小的數(shù)網(wǎng)上冒。

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
}

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

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;
}

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

實(shí)現(xiàn)

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
}

實(shí)質(zhì)為分組插入排序。為了方便理解，借用網(wǎng)上某哥的圖，參考鏈接在下文。

因?yàn)槭窃谝呀?jīng)分組排序過(guò)的基礎(chǔ)上進(jìn)行插入排序，所以效率高。

實(shí)現(xiàn)

//因?yàn)楹诵氖遣迦肱判?，所以我們改造直接插入排?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;
}
//編寫希爾排序函數(shù)
function shellSort (arr) {
    var len = arr.length;
    var gap = 1;
    //設(shè)置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;
}

遇見的問(wèn)題，關(guān)于參數(shù)的傳遞：函數(shù)參數(shù)的傳遞可以分為按值傳遞和引用傳遞。
步長(zhǎng)序列可以看一下wiki

類似直接插入，后一個(gè)元素（拿來(lái)比較的元素）與已排序的中間值m = (i-1) >> 1(位移運(yùn)算，相當(dāng)于Math.floor((i-1)/2))進(jìn)行比較,如果i上的值大于m上的值，則與高半?yún)^(qū)折半比較,最終將比i上值高的區(qū)域往后移，將i上的值插入。如

arr = [2, 6, 7, 6, 8]   
//前三個(gè)是已經(jīng)排好的。
//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]
...
...

實(shí)現(xiàn)

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

采取分而治之的思想。遞歸分組、比較產(chǎn)生兩個(gè)已排序序列，再依次比較兩組開頭元素，較小的元素放入申請(qǐng)的新數(shù)組中。
歸并函數(shù)可以通過(guò)遞歸、迭代實(shí)現(xiàn)。

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

          [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]  

實(shí)現(xiàn)

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))
}

遞歸可能會(huì)造成堆棧溢出的問(wèn)題。

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

          [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] 

實(shí)現(xiàn)

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個(gè)元素
    for (var i=1; i<=len; i*=2) {
        //比較相鄰兩組，有一組剩余就退出
        for (var j=0; j+i
快速排序
快速排序是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來(lái)看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。  
步驟：選擇一個(gè)元素作為基準(zhǔn)，下面選擇第一個(gè)，依次比較后面的元素，將小于基準(zhǔn)的元素放在基準(zhǔn)的左邊，剩余放右邊。形成左右兩個(gè)分區(qū)，再遞歸按之前的步驟排序。
實(shí)現(xiàn)
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;
}
快速排序排序效率非常高. 雖然它運(yùn)行最糟糕時(shí)將達(dá)到O(n2)的時(shí)間復(fù)雜度, 但通常, 平均來(lái)看, 它的時(shí)間復(fù)雜為O(nlogn), 比同樣為O(nlogn)時(shí)間復(fù)雜度的歸并排序還要快. 快速排序似乎更偏愛亂序的數(shù)列, 越是亂序的數(shù)列, 它相比其他排序而言, 相對(duì)效率更高.
Chrome的v8引擎為了高效排序, 在排序數(shù)據(jù)超過(guò)了10條時(shí), 便會(huì)采用快速排序. 對(duì)于10條及以下的數(shù)據(jù)采用的便是插入排序.
參考
十大經(jīng)典排序算法   
JS中可能用得到的全部的排序算法