---
tags: 演算法, LeetCode
disqus: HackMD
---

# 插入排序(Insertion Sort)

## 介紹

插入排序是從數列最左邊開始，往右依序排序下去，在過程中，由左至右，先將最左邊的數值設定成已排序，再往右取一個未排序數值，插入已排序中的適當位置，依此類推完成排序。在最糟的情況下，數列從大排到小，每 `n` 回合就必須進行 `n-1` 次比較和對調，在第一回合需要一次，第二回合兩次....到第 `n` 回合發生 `n - 1` 次，大約等於`n^2/2`，所以時間複雜度跟氣泡排序還有選擇排序一樣是`O(n^2)`。

優點:
1. 只需要固定數量的 O(1) 內存空間
2. 在實踐中比大多數其他簡單的二次方算法（如選擇排序或冒泡排序）更有效

([圖片來源](https://www.pinterest.com/pin/algorithms-for-beginners-bubble-sort-insertion-sort-merge-sort-in-2022--680113981240308504/))

## 虛擬碼

為甚麼迴圈從 `1` 開始 ?

因為最左邊的數列一開始會被當作是已排序的

function insertion_sort (array) {
    for(j from 1 to length-1){
        key = array[j]
        i = j - 1
        while i >= 0 and array[i] > key:
            array[i + 1] = array[i]
            i = i - 1
        array[i + 1] = key
    }
}

## 複雜度

### 時間複雜度

$O(n^2)$

### 空間複雜度

$O(1)$

## 實戰

[75. Sort Colors](https://leetcode.com/problems/sort-colors/)

### 題目說明

給定一個數組 `nums`，其中有 `n` 個對象，顏色為紅色、白色或藍色，並對它們進行排序，顏色按紅色、白色和藍色的順序排列。 將使用整數 0、1 和 2 分別表示紅色、白色和藍色。 必須在不使用`library`的排序功能的情況下解決此問題。


### 解法

**Javascript**

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    for(let i = 1; i <= nums.length - 1; i++){
        key = nums[i];
        j = i - 1;
        while(j >= 0 && nums[j] > key){
            nums[j + 1] = nums[j];
            j = j - 1;
        }
        nums[j + 1] = key
    }
    return nums
};

## 圖解

以此範例為例子

Input: nums = [2,0,1]
Output: [0,1,2]


> [name=@joe94113] [time=Wed, Oct 26, 2022 10:26 PM] [color=#907bf7]