Jimmy 的架站筆記

嗨~我是 Jimmy!我可能不是你認識的第 1 個 Jimmy,但一定是最帥的那個。


排序演算法筆記 3 - Insertion Sort (插入排序法)

By Jimmy 2022-04-16
發表於 演算法 資工
排序演算法筆記 3 - Insertion Sort (插入排序法)

Insertion Sort (插入排序法) 的原理也很直觀,將要排序的元素插入已經排列好的左側陣列:

1. Insertion Sort 原理解釋

Insertion Sort

Insertion Sort

▲ 將第一個元素視為已經排列好的陣列,因此第一輪從 i = 1 開始跑

Insertion Sort

▲ 如果待排序的元素比排列好陣列中的最後一個元素還小,代表需要將待排序元素插入已經排序好的陣列中

接著要判斷要插入到排列好陣列中的哪個位置:

Insertion Sort

Insertion Sort

第二輪 (i = 2):

Insertion Sort

Insertion Sort

Insertion Sort

Insertion Sort

第三輪 (i = 3)

Insertion Sort

Insertion Sort

Insertion Sort

Insertion Sort

Insertion Sort

Insertion Sort

2. JavaScript 實作

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    // 尚未排列的第一個元素
    const currElement = arr[i];
    // 已經排列好的陣列中最後元素的 index
    let j = i - 1;
    // 目標元素要小於已經排列好的陣列中最後的元素,才會進到此迴圈
    while (j >= 0 && currElement < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = currElement;
  }
  return arr;
}

概念圖:

Insertion Sort

3. Time Complexity

最佳:O(n)
最差:O(n2)
平均:O(n2)

4. 參考資料

大話資料結構(全新彩色版)
資料結構與演算法 (JavaScript)


你可能也會喜歡

演算法筆記 0 – 演算法定義與 Big O Notation

演算法筆記 0 – 演算法定義與 Big O Notation

1. 演算法定義 一般來說,符合以下這 5 種特性(Characteristics)就可以稱為演算法: 1.1 輸入(Input) An algorithm may have many inputs or no inputs at all. 演算法應該具有 0 個或多個輸入。 1.2 輸出(Output) An algorithm should result at least one outpu

Read More
資料結構筆記 4 - Binary Tree (二元樹)

資料結構筆記 4 - Binary Tree (二元樹)

1. Binary Tree 定義 Binary tree 是定義更狹窄的 tree,一棵 binary tree 的定義如下: - 每個 node 最多有兩個 subTree (也就是最多有兩個 child node) - Left subTree (左子樹) 和 right subTree (右子樹) 是有順序的,順序不能任意顛倒 - 即使某個 node 只有一個 subTree,也必須區分

Read More