JavaScript 排序算法

排序算法是將一系列的值按照順序進行排列的方法。

冒泡排序

簡介

冒泡排序（Bubble Sort）是最易懂的排序算法，但是效率較低，生產(chǎn)環(huán)境中很少使用。

它的基本思想是：

1. 依次比較相鄰的兩個數(shù)，如果不符合排序規(guī)則，則調(diào)換兩個數(shù)的位置。這樣一遍比較下來，能夠保證最大（或最?。┑臄?shù)排在最后一位。

2. 再對最后一位以外的數(shù)組，重復前面的過程，直至全部排序完成。

由于每進行一次這個過程，在該次比較的最后一個位置上，正確的數(shù)會自己冒出來，就好像“冒泡”一樣，這種算法因此得名。

以對數(shù)組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

1. 第一位的“3”與第二位的“2”進行比較，3大于2，互換位置，數(shù)組變成[2, 3, 4, 5, 1] 。

2. 第二位的“3”與第三位的“4”進行比較，3小于4，數(shù)組不變。

3. 第三位的“4”與第四位的“5”進行比較，4小于5，數(shù)組不變。

4. 第四位的“5”與第五位的“1”進行比較，5大于1，互換位置，數(shù)組變成[2, 3, 4, 1, 5] 。

第一輪排序完成，可以看到最后一位的5，已經(jīng)是正確的數(shù)了。然后，再對剩下的數(shù)[2, 3, 4, 1] 重復這個過程，每一輪都會在本輪最后一位上出現(xiàn)正確的數(shù)。直至剩下最后一個位置，所有排序結束。

算法實現(xiàn)

先定義一個交換函數(shù)，作用是交換兩個位置的值。

function swap(myArray, p1, p2){
    var temp = myArray[p1];
    myArray[p1] = myArray[p2];
    myArray[p2] = temp;
}

然后定義主函數(shù)。

function bubbleSort(myArray){

    var len = myArray.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (myArray[j] > myArray[j+1]){
                swap(myArray, j, j+1);
            }
        }
    }

    return myArray;
}

選擇排序

簡介

選擇排序（Selection Sort）與冒泡排序類似，也是依次對相鄰的數(shù)進行兩兩比較。不同之處在于，它不是每比較一次就調(diào)換位置，而是一輪比較完畢，找到最大值（或最小值）之后，將其放在正確的位置，其他數(shù)的位置不變。

以對數(shù)組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

1. 假定第一位的“3”是最小值。

2. 最小值“3”與第二位的“2”進行比較，2小于3，所以新的最小值是第二位的“2”。

3. 最小值“2”與第三位的“4”進行比較，2小于4，最小值不變。

4. 最小值“2”與第四位的“5”進行比較，2小于5，最小值不變。

5. 最小值“2”與第五位的“1”進行比較，1小于2，所以新的最小值是第五位的“1”。

6. 第五位的“1”與第一位的“3”互換位置，數(shù)組變?yōu)閇1, 2, 4, 5, 3]。

這一輪比較結束后，最小值“1”已經(jīng)排到正確的位置了，然后對剩下的[2, 4, 5, 3]重復上面的過程。每一輪排序都會將該輪的最小值排到正確的位置，直至剩下最后一個位置，所有排序結束。

算法實現(xiàn)

先定義一個交換函數(shù)。

function swap(myArray, p1, p2){
    var temp = myArray[p1];
    myArray[p1] = myArray[p2];
    myArray[p2] = temp;
}

然后定義主函數(shù)。

function selectionSort(myArray){

    var len = myArray.length,
        min;

    for (i=0; i < len; i++){

        // 將當前位置設為最小值
        min = i;

        // 檢查數(shù)組其余部分是否更小
        for (j=i+1; j < len; j++){
            if (myArray[j] < myArray[min]){
                min = j;
            }
        }

        // 如果當前位置不是最小值，將其換為最小值
        if (i != min){
            swap(myArray, i, min);
        }
    }

    return myArray;
}

插入排序

簡介

插入排序（insertion sort）比前面兩種排序方法都更有效率。它將數(shù)組分成“已排序”和“未排序”兩部分，一開始的時候，“已排序”的部分只有一個元素，然后將它后面一個元素從“未排序”部分插入“已排序”部分，從而“已排序”部分增加一個元素，“未排序”部分減少一個元素。以此類推，完成全部排序。

以對數(shù)組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

1. 將數(shù)組分成[3]和[2, 4, 5, 1]兩部分，前者是已排序的，后者是未排序的。

2. 取出未排序部分的第一個元素“2”，與已排序部分最后一個元素“3”比較，因為2小于3，所以2排在3前面，整個數(shù)組變成[2, 3]和[4, 5, 1]兩部分。

3. 取出未排序部分的第一個元素“4”，與已排序部分最后一個元素“3”比較，因為4大于3，所以4排在3后面，整個數(shù)組變成[2, 3, 4]和[5, 1]兩部分。

4. 取出未排序部分的第一個元素“5”，與已排序部分最后一個元素“4”比較，因為5大于4，所以5排在4后面，整個數(shù)組變成[2, 3, 4, 5]和[1]兩部分。

5. 取出未排序部分的第一個元素“1”，與已排序部分最后一個元素“5”比較，因為1小于5，所以再與前一個元素“4”比較；因為1小于4，再與前一個元素“3”比較；因為1小于3，再與前一個元素“2”比較；因為小于1小于2，所以“1”排在2的前面，整個數(shù)組變成[1, 2, 3, 4, 5]。

算法實現(xiàn)

算法的實現(xiàn)如下：

function insertionSort(myArray) {

    var len     = myArray.length,     // 數(shù)組的長度
        value,                      // 當前比較的值
        i,                          // 未排序部分的當前位置
        j;                          // 已排序部分的當前位置

    for (i=0; i < len; i++) {

        // 儲存當前位置的值
        value = myArray[i];

        /*
         * 當已排序部分的當前元素大于value，
         * 就將當前元素向后移一位，再將前一位與value比較
         */
        for (j=i-1; j > -1 && myArray[j] > value; j--) {
            myArray[j+1] = myArray[j];
        }

        myArray[j+1] = value;
    }

    return myArray;
}

合并排序

簡介

前面三種排序算法只有教學價值，因為效率低，很少實際使用。合并排序（Merge sort）則是一種被廣泛使用的排序方法。

它的基本思想是，將兩個已經(jīng)排序的數(shù)組合并，要比從頭開始排序所有元素來得快。因此，可以將數(shù)組拆開，分成n個只有一個元素的數(shù)組，然后不斷地兩兩合并，直到全部排序完成。

以對數(shù)組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

1. 將數(shù)組分成[3, 2, 4]和[5, 1]兩部分。

2. 將[3, 2, 4]分成[3, 2]和[4]兩部分。

3. 將[3, 2]分成[3]和[2]兩部分，然后合并成[2, 3]。

4. 將[2, 3]和[4]合并成[2, 3, 4]。

5. 將[5, 1]分成[5]和[1]兩部分，然后合并成[1, 5]。

6. 將[2, 3, 4]和[1, 5]合并成[1, 2, 3, 4, 5]。

算法實現(xiàn)

這里的關鍵是如何合并兩個已經(jīng)排序的數(shù)組。具體實現(xiàn)請看下面的函數(shù)。

function merge(left, right){
    var result  = [],
        il      = 0,
        ir      = 0;

    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }

    return result.concat(left.slice(il)).concat(right.slice(ir));
}

上面的merge函數(shù)，合并兩個已經(jīng)按升序排好序的數(shù)組。首先，比較兩個數(shù)組的第一個元素，將其中較小的一個放入result數(shù)組；然后，將其中較大的一個與另一個數(shù)組的第二個元素進行比較，再將其中較小的一個放入result數(shù)組的第二個位置。以此類推，直到一個數(shù)組的所有元素都進入result數(shù)組為止，再將另一個數(shù)組剩下的元素接著result數(shù)組后面返回（使用concat方法）。

有了merge函數(shù)，就可以對任意數(shù)組排序了。基本方法是將數(shù)組不斷地拆成兩半，直到每一半只包含零個元素或一個元素為止，然后就用merge函數(shù)，將拆成兩半的數(shù)組不斷合并，直到合并成一整個排序完成的數(shù)組。

function mergeSort(myArray){

    if (myArray.length < 2) {
        return myArray;
    }

    var middle = Math.floor(myArray.length / 2),
        left    = myArray.slice(0, middle),
        right   = myArray.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

上面的代碼有一個問題，就是返回的是一個全新的數(shù)組，會多占用空間。因此，修改上面的函數(shù)，使之在原地排序，不多占用空間。

function mergeSort(myArray){

    if (myArray.length < 2) {
        return myArray;
    }

    var middle = Math.floor(myArray.length / 2),
        left    = myArray.slice(0, middle),
        right   = myArray.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));

    // 在返回的數(shù)組頭部，添加兩個元素，第一個是0，第二個是返回的數(shù)組長度
    params.unshift(0, myArray.length);

    // splice用來替換數(shù)組元素，它接受多個參數(shù)，
    // 第一個是開始替換的位置，第二個是需要替換的個數(shù)，后面就是所有新加入的元素。
    // 因為splice不接受數(shù)組作為參數(shù)，所以采用apply的寫法。
    // 這一句的意思就是原來的myArray數(shù)組替換成排序后的myArray
    myArray.splice.apply(myArray, params);

    // 返回排序后的數(shù)組
    return myArray;
}

快速排序

簡介

快速排序（quick sort）是公認最快的排序算法之一，有著廣泛的應用。

它的基本思想很簡單：先確定一個“支點”（pivot），將所有小于“支點”的值都放在該點的左側，大于“支點”的值都放在該點的右側，然后對左右兩側不斷重復這個過程，直到所有排序完成。

具體做法是：

1. 確定“支點”（pivot）。雖然數(shù)組中任意一個值都能作為“支點”，但通常是取數(shù)組的中間值。

2. 建立兩端的指針。左側的指針指向數(shù)組的第一個元素，右側的指針指向數(shù)組的最后一個元素。

3. 左側指針的當前值與“支點”進行比較，如果小于“支點”則指針向后移動一位，否則指針停在原地。

4. 右側指針的當前值與“支點”進行比較，如果大于“支點”則指針向前移動一位，否則指針停在原地。

5. 左側指針的位置與右側指針的位置進行比較，如果前者大于等于后者，則本次排序結束；否則，左側指針的值與右側指針的值相交換。

6. 對左右兩側重復第2至5步。

以對數(shù)組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

1. 選擇中間值“4”作為“支點”。

2. 第一個元素3小于4，左側指針向后移動一位；第二個元素2小于4，左側指針向后移動一位；第三個元素4等于4，左側指針停在這個位置（數(shù)組的第2位）。

3. 倒數(shù)第一個元素1小于4，右側指針停在這個位置（數(shù)組的第4位）。

4. 左側指針的位置（2）小于右側指針的位置（4），兩個位置的值互換，數(shù)組變成[3, 2, 1, 5, 4]。

5. 左側指針向后移動一位，第四個元素5大于4，左側指針停在這個位置（數(shù)組的第3位）。

6. 右側指針向前移動一位，第四個元素5大于4，右側指針移動向前移動一位，第三個元素1小于4，右側指針停在這個位置（數(shù)組的第3位）。

7. 左側指針的位置（3）大于右側指針的位置（2），本次排序結束。

8. 對 [3, 2, 1]和[5, 4]兩部分各自不斷重復上述步驟，直到排序完成。

算法實現(xiàn)

首先部署一個swap函數(shù)，用于互換兩個位置的值。

function swap(myArray, firstIndex, secondIndex){
    var temp = myArray[firstIndex];
    myArray[firstIndex] = myArray[secondIndex];
    myArray[secondIndex] = temp;
}

然后，部署一個partition函數(shù)，用于完成一輪排序。

function partition(myArray, left, right) {

    var pivot   = myArray[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;

    while (i <= j) {

        while (myArray[i] < pivot) {
            i++;
        }

        while (myArray[j] > pivot) {
            j--;
        }

        if (i <= j) {
            swap(myArray, i, j);
            i++;
            j--;
        }
    }

    return i;
}

接下來，就是遞歸上面的過程，完成整個排序。

function quickSort(myArray, left, right) {

    if (myArray.length < 2) return myArray;

    left = (typeof left !== "number" ? 0 : left);

    right = (typeof right !== "number" ? myArray.length - 1 : right);

    var index  = partition(myArray, left, right);

     if (left < index - 1) {
            quickSort(myArray, left, index - 1);
     }

     if (index < right) {
            quickSort(myArray, index, right);
      }

     return myArray;

}

參考鏈接

• Nicholas C. Zakas, Computer science in JavaScript: Bubble sort
• Nicholas C. Zakas, Computer science in JavaScript: Selection sort
• Nicholas C. Zakas, Computer science in JavaScript: Insertion sort
• Nicholas C. Zakas, Computer science in JavaScript: Merge sort
• Nicholas C. Zakas, Computer science in JavaScript: Quicksort