---
# System prepended metadata

title: Insertion Sort
tags: [Sort, Comparison Sort]

---

<style>

html, body, .ui-content {
    background-color: #333;
    color: #ddd;
}

body > .ui-infobar {
    display: none;
}

.ui-view-area > .ui-infobar {
    display: block;
}

.markdown-body h1,
.markdown-body h2,
.markdown-body h3,
.markdown-body h4,
.markdown-body h5,
.markdown-body h6 {
    color: #ddd;
}

.markdown-body h1,
.markdown-body h2 {
    border-bottom-color: #ffffff69;
}

.markdown-body h1 .octicon-link,
.markdown-body h2 .octicon-link,
.markdown-body h3 .octicon-link,
.markdown-body h4 .octicon-link,
.markdown-body h5 .octicon-link,
.markdown-body h6 .octicon-link {
    color: #fff;
}

.markdown-body img {
    background-color: transparent;
}

.ui-toc-dropdown .nav>.active:focus>a, .ui-toc-dropdown .nav>.active:hover>a, .ui-toc-dropdown .nav>.active>a {
    color: white;
    border-left: 2px solid white;
}

.expand-toggle:hover, 
.expand-toggle:focus, 
.back-to-top:hover, 
.back-to-top:focus, 
.go-to-bottom:hover, 
.go-to-bottom:focus {
    color: white;
}


.ui-toc-dropdown {
    background-color: #333;
}

.ui-toc-label.btn {
    background-color: #191919;
    color: white;
}

.ui-toc-dropdown .nav>li>a:focus, 
.ui-toc-dropdown .nav>li>a:hover {
    color: white;
    border-left: 1px solid white;
}

.markdown-body blockquote {
    color: #bcbcbc;
}

.markdown-body table tr {
    background-color: #5f5f5f;
}

.markdown-body table tr:nth-child(2n) {
    background-color: #4f4f4f;
}

.markdown-body code,
.markdown-body tt {
    color: #eee;
    background-color: rgba(230, 230, 230, 0.36);
}

a,
.open-files-container li.selected a {
    color: #5EB7E0;
}

</style>

# Insertion Sort
###### tags: `Sort`,`Comparison Sort`
### 介紹
想像手中有一副撲克牌，且我們想要讓這副牌以 **2 , 3 , 4 , ... , J , Q , K , A** 的方式排列。

Insertion Sort的想法是：每當我要對第 **i** 個位置的牌進行至整理時，前 **i-1** 張牌是已經完成排序的。動作完成後，即可獲得前ｉ張牌都整理好的組合。

示意圖如下所示：
![](https://i.imgur.com/3mughJN.gif)
圖(一)

從上圖可以發現，在排序 **N** 筆資料時，第一個元素不需要進行排序，其本身就是有序的。所以在 **N** 筆資料下，需要進行比較的輪數為 **N-1** 輪。

在排序第 **i** 個元素時，需要依次和前 **i-1** 個元素進行比較，比較結束後才能得到前 **i** 個元素為有序的數列。

在實作上，可以採取雙層 for loop 來處理，外圈負責處理比較輪數，內圈則負責將該輪要插入的值，與前面已經排序的值依次進行比較。

### 程式碼
```java=
public static void insertionSort(int[] arr){
    if(arr.length < 2){
        return;
    }
    for(int i = 1; i <arr.length; i++){
        for(int j = i - 1; j >= 0; j--){
            if(arr[j] > arr[j - 1]){
                swap(arr, j, j + 1);
            }
        }
    }
}

public static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
```

### 參考資料
1. 圖(一)：[VisuAlgo](https://visualgo.net/zh/sorting)
2. [算法大神左神（左程云）带你一周刷爆LeetCode，数据结构算法-leetcode真题解析](https://www.bilibili.com/video/BV1kQ4y1h7ok?p=1)

<hr style="height:1px;border:none;border-top:1px dashed #0066CC;">

[資料結構與演算法](/FP0Vd0lqQM2gDIadctxk2Q)\
[Sorting 簡介][0]

[0]:https://hackmd.io/7Mo3SJ1wQ5G8s9PIsu9u_w