---
# System prepended metadata

title: 演算法
tags: [LeetCode]

---

# 演算法
###### tags: `LeetCode`


:::info
:pushpin: 插入排序法是將陣列中未排序的元素，逐一與排序好的資料作比較。它的時間複雜度是 $O(n^2)$。
:::
---

{%youtube OGzPmgsI-pQ %}

## 一、步驟觀察
* 標記第一個元素作為已排序的部分
* 遍歷未排序的部分，作以下動作
    * 取第一個未排序的元素
    * ==與已排序的元素作比較==
        * 移動出正確位置，然後插入未排序的元素
    * 向右移動標記

![](https://i.imgur.com/jQExUWy.gif)
( 圖片來源 wiki )

## 二、實際操作
### 使用哪種資料結構：
* 

**邏輯：**
```1
  arr <- an array of integers
  let len be the length of arr
  
  for i (1 t0 len-1) do
    key = arr[i]
    j = i-1
    while j>=0 && key<arr[j]
      arr[j+1] = arr[j]
      j--
    end while
    arr[j+1] = key
  end for
```

**程式碼實作：**
```javascript=1
debugger
function insertionSort(arr) {

  for (let i = 1; i < arr.length; i++) {
    let key = arr[i] // 第一個未排序的元素
    let j = i-1 // 已排序元素的控制器
    console.log(key)

    while (j>=0 && key<arr[j]) { // 移動出正確位置
      arr[j+1] = arr[j]
      console.log(arr)
      j--
    }
    arr[j+1] = key // 插入未排序元素
    console.log(arr)
  }
}

insertionSort([8, 9, 2, 5, 1])
```

<!-- ## 四、優化改善
內容 -->

## 三、時間複雜度 Big O
* 總共比較了 1+2+3+...+(n-1)
* 也就是 n*(n-1)/2
* 時間複雜度會忽略係數，所以為 $O(n^2)$