排序算法 -- JavaScript 標準參考教程

kuailezhok 7年前發布 | 10K 次閱讀排序算法 JavaScript開發 JavaScript

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

冒泡排序

簡介

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

它的基本思想是：

依次比較相鄰的兩個數，如果不符合排序規則，則調換兩個數的位置。這樣一遍比較下來，能夠保證最大（或最小）的數排在最后一位。
再對最后一位以外的數組，重復前面的過程，直至全部排序完成。

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

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

第一位的“3”與第二位的“2”進行比較，3大于2，互換位置，數組變成 [2, 3, 4, 5, 1] 。
第二位的“3”與第三位的“4”進行比較，3小于4，數組不變。
第三位的“4”與第四位的“5”進行比較，4小于5，數組不變。
第四位的“5”與第五位的“1”進行比較，5大于1，互換位置，數組變成 [2, 3, 4, 1, 5] 。

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

算法實現

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

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

然后定義主函數。

function bubbleSort(myArray){
  var len = myArray.length;
  var i;
  var j;
  var stop;

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

  return myArray;
}

選擇排序

簡介

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

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

假定第一位的“3”是最小值。
最小值“3”與第二位的“2”進行比較，2小于3，所以新的最小值是第二位的“2”。
最小值“2”與第三位的“4”進行比較，2小于4，最小值不變。
最小值“2”與第四位的“5”進行比較，2小于5，最小值不變。
最小值“2”與第五位的“1”進行比較，1小于2，所以新的最小值是第五位的“1”。
第五位的“1”與第一位的“3”互換位置，數組變為[1, 2, 4, 5, 3]。

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

算法實現

先定義一個交換函數。

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

然后定義主函數。

function selectionSort(myArray){

    var len = myArray.length,
        min;

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

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

        // 檢查數組其余部分是否更小
        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）比前面兩種排序方法都更有效率。它將數組分成“已排序”和“未排序”兩部分，一開始的時候，“已排序”的部分只有一個元素，然后將它后面一個元素從“未排序”部分插入“已排序”部分，從而“已排序”部分增加一個元素，“未排序”部分減少一個元素。以此類推，完成全部排序。

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

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

算法實現

算法的實現如下：

function insertionSort(myArray) {

    var len     = myArray.length,     // 數組的長度
        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）則是一種被廣泛使用的排序方法。

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

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

將數組分成[3, 2, 4]和[5, 1]兩部分。
將[3, 2, 4]分成[3, 2]和[4]兩部分。
將[3, 2]分成[3]和[2]兩部分，然后合并成[2, 3]。
將[2, 3]和[4]合并成[2, 3, 4]。
將[5, 1]分成[5]和[1]兩部分，然后合并成[1, 5]。
將[2, 3, 4]和[1, 5]合并成[1, 2, 3, 4, 5]。

算法實現

這里的關鍵是如何合并兩個已經排序的數組。具體實現請看下面的函數。

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

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

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

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

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

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

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

    // 返回排序后的數組
    return myArray;
}

快速排序

簡介

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

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

具體做法是：

確定“支點”（pivot）。雖然數組中任意一個值都能作為“支點”，但通常是取數組的中間值。
建立兩端的指針。左側的指針指向數組的第一個元素，右側的指針指向數組的最后一個元素。
左側指針的當前值與“支點”進行比較，如果小于“支點”則指針向后移動一位，否則指針停在原地。
右側指針的當前值與“支點”進行比較，如果大于“支點”則指針向前移動一位，否則指針停在原地。
左側指針的位置與右側指針的位置進行比較，如果前者大于等于后者，則本次排序結束；否則，左側指針的值與右側指針的值相交換。
對左右兩側重復第2至5步。

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

選擇中間值“4”作為“支點”。
第一個元素3小于4，左側指針向后移動一位；第二個元素2小于4，左側指針向后移動一位；第三個元素4等于4，左側指針停在這個位置（數組的第2位）。
倒數第一個元素1小于4，右側指針停在這個位置（數組的第4位）。
左側指針的位置（2）小于右側指針的位置（4），兩個位置的值互換，數組變成[3, 2, 1, 5, 4]。
左側指針向后移動一位，第四個元素5大于4，左側指針停在這個位置（數組的第3位）。
右側指針向前移動一位，第四個元素5大于4，右側指針移動向前移動一位，第三個元素1小于4，右側指針停在這個位置（數組的第3位）。
左側指針的位置（3）大于右側指針的位置（2），本次排序結束。
對 [3, 2, 1]和[5, 4]兩部分各自不斷重復上述步驟，直到排序完成。

算法實現

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

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

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

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

來自：http://javascript.ruanyifeng.com/library/sorting.html

本文由用戶 kuailezhok 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1488254629635.html

排序算法 JavaScript開發 JavaScript

排序算法 -- JavaScript 標準參考教程

冒泡排序

簡介

算法實現

選擇排序

簡介

算法實現

插入排序

簡介

算法實現

合并排序

簡介

算法實現

快速排序

簡介

算法實現

參考鏈接

相關經驗

相關資訊

相關文檔

目錄