DIV CSS 佈局教程網

六種經典排序算法的 JavaScript 實現
編輯:JavaScript基礎知識     

排序演算法是資料結構的入門必修。以下以 JavaScript 實作六種經典排序,並在每段程式碼後附上執行過程的觀察輸出,方便對照理解每一步的變化。

一、氣泡排序 Bubble Sort

反覆比較相鄰元素並交換,每一輪把當前最大值送到末端,因此得名。

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

  // 每一輪縮小一次範圍
  for (var i = length - 1; i > 0; i--) {
    // 在範圍內進行冒泡,此範圍內最大者將浮到最後
    for (var j = 0; j < i; j++) {
      if (array[j] > array[j + 1]) {
        var temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
    console.log(array);
    console.log("-----------------------------");
  }
  return array;
}

var arr = [10, 9, 8, 7, 7, 6, 5, 11, 3];
var result = BubbleSort(arr);
console.log(result);

/*
[ 9, 8, 7, 7, 6, 5, 10, 3, 11 ]
[ 8, 7, 7, 6, 5, 9, 3, 10, 11 ]
[ 7, 7, 6, 5, 8, 3, 9, 10, 11 ]
[ 7, 6, 5, 7, 3, 8, 9, 10, 11 ]
[ 6, 5, 7, 3, 7, 8, 9, 10, 11 ]
[ 5, 6, 3, 7, 7, 8, 9, 10, 11 ]
[ 5, 3, 6, 7, 7, 8, 9, 10, 11 ]
[ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
[ 3, 5, 6, 7, 7, 8, 9, 10, 11 ]
*/

時間複雜度 O(n²),空間 O(1),穩定。實作時可加上「本輪是否發生交換」的旗標提前結束。

二、選擇排序 Selection Sort

每一輪從未排序區中找出最小值,與該區的第一個位置交換。

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

  for (var i = 0; i < length; i++) {
    var min = array[i];   // 假定範圍內第一個為最小
    var index = i;        // 記錄最小值的索引

    // 在範圍內挑選真正的最小值
    for (var j = i + 1; j < length; j++) {
      if (array[j] < min) {
        min = array[j];
        index = j;
      }
    }

    // 把最小值交換到範圍首位
    if (index != i) {
      var temp = array[i];
      array[i] = array[index];
      array[index] = temp;
    }
    console.log(array);
    console.log("---------------------");
  }
  return array;
}

var arr = [1, 10, 100, 90, 65, 5, 4, 10, 2, 4];
var result = SelectionSort(arr);
console.log(result);

/*
[ 1, 10, 100, 90, 65, 5, 4, 10, 2, 4 ]
[ 1, 2, 100, 90, 65, 5, 4, 10, 10, 4 ]
[ 1, 2, 4, 90, 65, 5, 100, 10, 10, 4 ]
[ 1, 2, 4, 4, 65, 5, 100, 10, 10, 90 ]
[ 1, 2, 4, 4, 5, 65, 100, 10, 10, 90 ]
[ 1, 2, 4, 4, 5, 10, 100, 65, 10, 90 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 100, 90 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
[ 1, 2, 4, 4, 5, 10, 10, 65, 90, 100 ]
*/

交換次數最少(至多 n-1 次),但比較次數恆為 O(n²),且不穩定。

三、插入排序 Insertion Sort

把待插入元素插入到已排序序列的正確位置,模仿打牌的整理過程。

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

  for (var i = 0; i < length - 1; i++) {
    // i 代表已排序序列的最後一項索引
    var insert = array[i + 1];
    var index = i + 1;   // 記錄待插入的位置

    // 從右向左找出插入點,順便往後搬移
    for (var j = i; j >= 0; j--) {
      if (insert < array[j]) {
        array[j + 1] = array[j];
        index = j;
      }
    }
    array[index] = insert;

    console.log(array);
    console.log("-----------------------");
  }
  return array;
}

var arr = [100, 90, 80, 62, 80, 8, 1, 2, 39];
var result = InsertionSort(arr);
console.log(result);

/*
[ 90, 100, 80, 62, 80, 8, 1, 2, 39 ]
[ 80, 90, 100, 62, 80, 8, 1, 2, 39 ]
[ 62, 80, 90, 100, 80, 8, 1, 2, 39 ]
[ 62, 80, 80, 90, 100, 8, 1, 2, 39 ]
[ 8, 62, 80, 80, 90, 100, 1, 2, 39 ]
[ 1, 8, 62, 80, 80, 90, 100, 2, 39 ]
[ 1, 2, 8, 62, 80, 80, 90, 100, 39 ]
[ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
[ 1, 2, 8, 39, 62, 80, 80, 90, 100 ]
*/

資料近乎有序時接近 O(n),是少數能在小規模或近乎有序資料上打敗 O(n log n) 演算法的排序,且穩定。

四、希爾排序 Shell Sort

插入排序的改良版:以遞減的間隔(gap)先做粗粒度排序,讓元素能長距離移動,最後以 gap=1 收尾。

function ShellSort(array) {
  var length = array.length;
  var gap = Math.round(length / 2);

  while (gap > 0) {
    for (var i = gap; i < length; i++) {
      var insert = array[i];
      var index = i;

      for (var j = i; j >= 0; j -= gap) {
        if (insert < array[j]) {
          array[j + gap] = array[j];
          index = j;
        }
      }
      array[index] = insert;
    }

    console.log(array);
    console.log("-----------------------");
    gap = Math.round(gap / 2 - 0.1);
  }
  return array;
}

var arr = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10];
var result = ShellSort(arr);
console.log(result);

/*
[ 13, 14, 45, 27, 73, 25, 39, 10, 65, 23, 94, 33, 82, 25, 59, 94 ]
[ 13, 14, 39, 10, 65, 23, 45, 27, 73, 25, 59, 33, 82, 25, 94, 94 ]
[ 13, 10, 39, 14, 45, 23, 59, 25, 65, 25, 73, 27, 82, 33, 94, 94 ]
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
[ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
*/

時間複雜度依間隔序列而異,通常在 O(n^1.3) 上下;不穩定。它是第一個實用化的超越 O(n²) 的排序演算法。

五、合併排序 Merge Sort

典型的分治法:把陣列對半拆分直到只剩單一元素,再逐層合併。

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

  if (length <= 1) {
    return array;
  } else {
    var num = Math.ceil(length / 2);
    var left = MergeSort(array.slice(0, num));
    var right = MergeSort(array.slice(num, length));
    return merge(left, right);
  }
}

function merge(left, right) {
  console.log(left);
  console.log(right);

  var a = new Array();

  while (left.length > 0 && right.length > 0) {
    if (left[0] <= right[0]) {
      a.push(left.shift());
    } else {
      a.push(right.shift());
    }
  }

  if (left.length > 0) a = a.concat(left);
  if (right.length > 0) a = a.concat(right);

  console.log(a);
  console.log("-----------------------------");
  return a;
}

var arr = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10];
var result = MergeSort(arr);
console.log(result);

/*
[ 13 ] [ 14 ] → [ 13, 14 ]
[ 94 ] [ 33 ] → [ 33, 94 ]
[ 13, 14 ] [ 33, 94 ] → [ 13, 14, 33, 94 ]
[ 82 ] [ 25 ] → [ 25, 82 ]
[ 59 ] [ 94 ] → [ 59, 94 ]
[ 25, 82 ] [ 59, 94 ] → [ 25, 59, 82, 94 ]
[ 13, 14, 33, 94 ] [ 25, 59, 82, 94 ] → [ 13, 14, 25, 33, 59, 82, 94, 94 ]
[ 65 ] [ 23 ] → [ 23, 65 ]
[ 45 ] [ 27 ] → [ 27, 45 ]
[ 23, 65 ] [ 27, 45 ] → [ 23, 27, 45, 65 ]
[ 73 ] [ 25 ] → [ 25, 73 ]
[ 39 ] [ 10 ] → [ 10, 39 ]
[ 25, 73 ] [ 10, 39 ] → [ 10, 25, 39, 73 ]
[ 23, 27, 45, 65 ] [ 10, 25, 39, 73 ] → [ 10, 23, 25, 27, 39, 45, 65, 73 ]
[ 13, 14, 25, 33, 59, 82, 94, 94 ] [ 10, 23, 25, 27, 39, 45, 65, 73 ]
→ [ 10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94 ]
*/

時間複雜度穩定為 O(n log n),穩定,但需要 O(n) 的額外空間。上述實作用 shift() 取值,每次都是 O(n) 操作,實務上建議改用索引游標以提升效能。

六、快速排序 Quick Sort

選一個基準值,把陣列分成「不大於基準」與「大於基準」兩半,再分別遞歸排序。

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

  if (length <= 1) {
    return array;
  } else {
    var smaller = [];
    var bigger = [];
    var base = [array[0]];

    for (var i = 1; i < length; i++) {
      if (array[i] <= base[0]) {
        smaller.push(array[i]);
      } else {
        bigger.push(array[i]);
      }
    }

    console.log(smaller.concat(base.concat(bigger)));
    console.log("-----------------------");

    return QuickSort(smaller).concat(base.concat(QuickSort(bigger)));
  }
}

var arr = [8, 10, 100, 90, 65, 5, 4, 10, 2, 4];
var result = QuickSort(arr);
console.log(result);

/*
[ 5, 4, 2, 4, 8, 10, 100, 90, 65, 10 ]
[ 4, 2, 4, 5 ]
[ 2, 4, 4 ]
[ 2, 4 ]
[ 10, 10, 100, 90, 65 ]
[ 90, 65, 100 ]
[ 65, 90 ]
[ 2, 4, 4, 5, 8, 10, 10, 65, 90, 100 ]
*/

平均 O(n log n),不穩定。上述寫法以首元素為基準,在已排序或逆序資料上會退化為 O(n²);實務上可改用隨機基準或三數取中法,並在小区間時遞 cutover 到插入排序。

七、綜合比較

  • 穩定性:氣泡、插入、合併為穩定排序;選擇、希爾、快速為不穩定排序。
  • 時間複雜度:氣泡與選擇為 O(n²);插入平均 O(n²)、近乎有序時接近 O(n);希爾約 O(n^1.3);合併與快速平均 O(n log n),快速排序最壞退化至 O(n²)。
  • 空間:氣泡、選擇、插入、希爾為 O(1);合併需 O(n);快速約 O(log n)(遞歸堆疊)。
  • 選型建議:需要穩定且效能可預期選合併排序;追求平均效能與較小常數選快速排序;資料量很小或近乎有序,插入排序往往最快;只求前 k 大,用堆排序。

另外提醒:現代 JavaScript 引擎(V8 等)已為 Array.prototype.sort 做了高度優化,一般只需傳入比較函數即可,無需自行實作;上述程式碼的價值在於理解原理與取捨。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved