DIV CSS 佈局教程網

用 JavaScript 實作插入排序
編輯:關於JavaScript     

插入排序是所有排序演算法裡最適合當作入門的一個,因為它的運作方式就是人類整理撲克牌的方式。

演算法思路

  1. 新建一個空列表,用來保存已排序的「有序序列」。
  2. 從原序列取出一個數,插入到有序序列中,插入後仍須保持有序。
  3. 重複步驟 2,直到原序列為空。

插入排序的平均時間複雜度是平方級的,效率不高,但非常容易實作。它借助的是「逐步擴大成果」的思想,讓有序列表的長度慢慢增加,最後等於原列表的長度。

JavaScript 實作

<script type="text/javascript">
var org = [5, 4, 3, 2, 1, 6, 7, 9, 8, 10];
var tempArr = new Array();

for (var i = 0; i < org.length; i++) {
  if (i == 0) {
    tempArr[0] = org[0];        // 第一個元素直接放進新序列
  } else {
    for (var j = 0; j < tempArr.length; j++) {
      if (org[i] > tempArr[j]) {
        // 如果是新序列的最後一個元素,直接附加
        if (j == tempArr.length - 1) {
          tempArr[j + 1] = org[i];
          break;
        } else {
          continue;             // 否則繼續往後找插入點
        }
      } else {
        // 找到插入點:把後面的元素全部往後移一格
        for (var k = tempArr.length - 1; k >= j; k--) {
          tempArr[k + 1] = tempArr[k];
        }
        tempArr[j] = org[i];
        break;
      }
    }
  }
}
alert(tempArr);
</script>

程式碼在說什麼

外層迴圈每次從 org 取一張牌,內層迴圈在 tempArr 裡從頭比較,找出「第一個比它大的位置」。找到之後,把該位置到尾端的所有元素往後挪一格(k 迴圈),空出來的洞就放進新元素。如果一直比較到最後都沒找到更大的(代表它是目前最大的),就直接附加在尾端。

複雜度分析

  • 最佳情況 O(n):輸入已排序時,每個元素只需比較一次。
  • 最壞與平均情況 O(n²):需要大量搬移。
  • 空間 O(n):這個版本另外開了 tempArr,原版插入排序是原地排序,只需 O(1)。
  • 穩定性 穩定排序——相等元素的相對順序不會改變。

原地排序的標準寫法

實務上不開新陣列,而是在原陣列上「從右往左挪」:

function insertionSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    var current = arr[i];
    var j = i - 1;
    // 把比 current 大的元素全部往後移
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

這個版本更短、不需要額外記憶體,而且內層迴圈同時完成「比較」與「搬移」兩件事,沒有原版那個 break / continue 的分支迷宮。

什麼時候該用插入排序

雖然是 O(n²),它在實務上仍有一席之地:

  • 資料量小(幾十筆以內)時,插入排序常比 quicksort 快,因為沒有遞迴呼叫與分割 overhead。多數標準函式庫的排序實作都會在小区間時切換成插入排序。
  • 資料接近已排序時接近 O(n),非常適合「增量資料」場景,例如即時資料流持續插入。
  • 需要穩定排序時,它是簡單可靠的選擇。

最後補充:真正要排序時請直接用 arr.sort(),但記得數字排序必須傳比較函式 arr.sort((a, b) => a - b),否則會以字串順序排序,[10, 9, 1] 會變成 [1, 10, 9]。

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