準備

在實現(xiàn)排序算法之前俊马，先介紹將用到的幾個函數(shù)鹅颊。比如說為了將數(shù)組中數(shù)字的順序打亂敷存，我們可能需要一個洗牌函數(shù)，為了記錄代碼運行的時間堪伍，我們需要一個記錄時間的函數(shù)锚烦。下面來介紹這些函數(shù)的實現(xiàn)。

1. 洗牌方法

   function shuffle() {
      return Math.random() - 0.5;
   }
   

因為 Math.random() 方法產(chǎn)生的數(shù)值在 [0,1) 之間帝雇，所以這個方法可以確保返回的數(shù)值是隨機的涮俄。有了這個函數(shù)之后，只需要將其傳入數(shù)組的 sort() 方法作為參數(shù)即可打亂數(shù)組尸闸。這個方法借鑒自 《12 個 JavaScript 技巧》 一文彻亲。

2. 記錄時間

記錄時間其實很簡單，我們只需要在代碼執(zhí)行前獲取到時間吮廉，然后執(zhí)行完畢之后再獲取一次時間苞尝，取二者之間的差值即可，就像下面這樣宦芦。

    var Clock = {
         "time": function() {
            this.start = new Date().getTime();
        },

        "timeEnd": function() {
            this.end = new Date().getTime();
            return Math.floor(this.end - this.start);
        }
    }

如果你在 Java 中利用上面這個方面來計時宙址，那是合情合理的，不過我們這是在寫 JavaScript 代碼调卑，我們的宿主環(huán)境非常體貼抡砂，為我們提供了 console.time() 和 console.timeEnd() 方法來幫助我們計算 js 代碼執(zhí)行的時間。

不過值得一提的是恬涧，如果你利用 Clock 對象來計時會讓你感到失望注益，因為它計時不是太準確，我使用上面提到的方法對選擇排序進行了千數(shù)量級的計時溯捆， Clock 對象給我的結(jié)果使 8ms 左右聊浅，而 console.time() 和 console.timeEnd() 給出的結(jié)果卻是 4ms, 咋一看，好像時間長了兩倍现使，當我在進行萬數(shù)量級測驗時低匙，發(fā)現(xiàn)二者計時還是相差 4ms 左右，所以我的理解是碳锈，我們使用自定義計時方法是創(chuàng)建了一個對象顽冶，而這 4ms 使我們創(chuàng)建這個對象花費的時間。

好了售碳，說的已經(jīng)夠多了强重，下面開始進入正題绞呈。

選擇排序

選擇排序的思想非常簡單，首先间景，找到數(shù)組中最小的那個元素佃声，然后將它和數(shù)組的第一個元素交換位置。其次倘要，在剩下的元素中找到最小的元素圾亏，將它和數(shù)組的第二個元素位置交換。如此往復(fù)封拧，直到整個數(shù)組排序志鹃。

從算法的思想中我們可以得出結(jié)論，在最好的情況下泽西，也就是說數(shù)組元素全部有序的情況下曹铃，選擇排序需要經(jīng)歷 N^2 / 2 次比較，0 次位置變換捧杉。在最差的情況下陕见，也就是說所有數(shù)組元素一開始都不在最終位置上，需要經(jīng)歷 N^2 / 2 次比較和 N-1 次移位味抖。

function selectionSort(array) {
    var length = array.length,
        min,
        temp;

    for(var i = 0; i < length; i++) {
        min = i;

        for(var j = i; j < length;j++) {
            if (array[min] > array[j]) {
                min = j;
            }
        }

        if (min !== i) {
            temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

可見评甜，這種算法實現(xiàn)起來十分簡單，不過遺憾的是這種排序算法用于處理小數(shù)組的排序尚能稱職非竿，對于比較多的數(shù)據(jù)卻是無力回天蜕着，這也正是我們探索其他方法的動力所在谋竖，下面來講一個同樣簡單但是性能優(yōu)于選擇排序的算法 —— 插入排序红柱。

插入排序

插入排序的思想就是從第二個元素開始，與前面的元素進行比較蓖乘，直到找到比當前元素還要小的元素之后锤悄，將元素放下來，然后將后面的元素依次后移嘉抒，騰出位置零聚。

舉個例子來說，對于數(shù)組 [2些侍， 1隶症，0， 4]岗宣，首先從 1 也就是第二個元素開始蚂会，與前面的 2 進行對比，發(fā)現(xiàn) 1 比 2 小耗式，而且 2 前面也沒有元素了胁住，所以要將 1 放置在 2 的前面趁猴，這個時候 2 就需要后移為 1 騰出位置，這個時候數(shù)組元素就變成了 [1, 2, 0, 4]彪见。然后 0 與 2 比較儡司，發(fā)現(xiàn) 0 比 2 小，這個時候交換 0 與 2 的位置余指，再 與 1 進行比較捕犬，發(fā)現(xiàn) 0 還是比 1 小，所以交換 1 與 0 的位置浪规，這個時候數(shù)組就變成了 [0, 1, 2, 4]或听。4 與 2 比較，比 2 大笋婿，保持原位置不變誉裆。

那么，插入排序與選擇排序的差別在哪里呢缸濒？選擇排序會對余下的所有元素進行大小比較足丢，而插入排序則不是這樣，對位于 i 下標的元素來說庇配，只要它在 （i-1） - 0 的路徑中找到比 i 小的元素斩跌，它就會終止比較，這對于一個已經(jīng)基本排序的數(shù)組來說捞慌，是一個非常大的優(yōu)化耀鸦。不過，有利也有弊啸澡，插入排序相對于選擇排序的缺點就是它移動次數(shù)會顯著增加袖订。

在最佳情況下，也就是說對于一個有序數(shù)組嗅虏，插入排序只需要 N-1 次比較和 0 次交換洛姑。在最差情況下，也就是對于一個逆序數(shù)組皮服，它需要 N^2 / 2 次比較和 N^2 /2 次交換楞艾。

function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

function insertionSort(array) {
    var length = array.length,
        temp;

    for(var i = 1; i < length; i++) {
        for(var j = i; j > 0 && array[j] < array[j - 1]; j--) {
            swap(array, j, j-1);
        }
    }
}

插入排序平均情況下會比選擇排序快一倍左右，我以萬級數(shù)量級數(shù)據(jù)對這兩個算法進行了比較龄广，選擇排序耗時 120 ms 左右硫眯， 插入排序在 65ms 左右。當然择同，這只是在我電腦上的數(shù)據(jù)两入，根據(jù)電腦配置的不同得出的結(jié)果會有所不同。

還有一點值得提及奠衔，對于一個基本有序的數(shù)據(jù)來說谆刨，插入排序可能比任何排序算法都要快塘娶，也就是說它可能比歸并排序和快速排序還要快。那么該怎么定義基本有序呢痊夭？滿足下面三個條件之一就可以了刁岸。

1. 數(shù)組中的每個元素距離它的最終位置都不遠。
2. 一個有序的大數(shù)組接一個小數(shù)組她我。
3. 數(shù)組中只有幾個元素的位置不正確虹曙。

希爾排序

希爾排序其實就是對插入排序進行改進，讓其適應(yīng)大數(shù)組排序番舆≡吞迹看了插入排序的代碼你可能也發(fā)現(xiàn)了一個問題，如果一個非常大的數(shù)組恨狈，比如千萬數(shù)量級的數(shù)組疏哗，它是逆序的，使用插入排序的話禾怠，那么我們不得不將最后一個元素一步步的移動到第一位返奉，將倒數(shù)第二個元素一步步的移動到第二位，這樣的話真的是拖垮了這個算法的性能吗氏，也就是插入排序的最壞情況芽偏。

希爾排序只是對插入排序進行了一點點修改，卻將這個算法的性能提升了一大截弦讽，將細節(jié)的作用展現(xiàn)的淋漓盡致污尉。簡單地說，希爾排序的思想就是使數(shù)組中任意間隔 h 的元素都是有序的往产，這樣的數(shù)組被稱為 h 有序數(shù)組被碗。如果 h 很大，那么我們一次就可以將一個元素移動到很遠的位置捂齐，這樣就彌補了插入排序的缺陷蛮放。

所以缩抡，關(guān)鍵的就是這個 h 的值該如何選擇呢奠宜？事實上算法的性能和 h 的大小是有關(guān)系的，不過到目前為止并不知道 h 選取什么值是最好的瞻想，所以我一般選擇數(shù)組長度的 1/3 左右 压真。

function shellSort(array) {
    var length = array.length,
        temp,
        h = 1;

    while (h < length / 3) {
        h = 3 * h;
    }

    while (h >= 1) {
        for (var i = h; i < length; i++) {
            for (var j = i; j >= h && array[j] < array[j - h]; j -= h) {
                swap(array, j, j - h);
            }
        }

        h = h / 3;
    }
}

關(guān)于希爾排序的運行時間具體是多少，目前尚不清楚蘑险，只能說它的運行時間達不到平方級別滴肿，最壞情況下的比較次數(shù)與 N^（3/2） 成正比。

對于萬級數(shù)量級數(shù)組佃迄，我用希爾排序只花了 8ms 的時間泼差，相比于插入排序和選擇排序贵少，這種算法真是快了不知多少倍！

冒泡排序

對于冒泡排序是真的沒什么好講的了堆缘，它和選擇排序一樣滔灶，是各教科書介紹的重點，它的思想就是每次迭代將最大的元素排到末尾吼肥。我感覺這種算法在比較次數(shù)上和選擇排序相同录平，而移動次數(shù)卻又和插入排序差不多，所以性能比較差缀皱，是理論上的排序算法斗这，并不實用。

function bubleSort(array) {
    var length = array.length;

    for (var i = 0; i < length; i++) {
        for (var j = 0; j < length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
}