<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** 張牌是已經完成排序的。動作完成後，即可獲得前ｉ張牌都整理好的組合。

示意圖如下所示：
圖(一)

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

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

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

### 程式碼

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