# 插入排序法(Insert Sort)

把 n 個待排序的元素看成為一個有序表和一個無序表，開始時有序表只包含一個元素，無序表中包含 n-1 個元素，排序過程中每次從無序表中取出第一個元素，把它依次與有序表元素的元素進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。

## 舉例說明

假設今天有一陣列為 17, 3, 25, 14, 20, 9 ，我們需要利用插入排序法將之排序為由小到大：

1. 我們先將 17 設為有序表的第一個元素 (17), 3, 25, 14, 20, 9
2. 接著在無序表中取出第一個值，與有序表中的元素做比較，放置到合適的位置。
比如：3 < 17，所以將 3 置於 17 前方
4. 接下來是將 25 插入到有序表中，25 > 17 所以置於 17 後方

以此類推...


## 程式碼實現

1. 需要進行 陣列大小-1 輪比較
2. 第 n 輪需比較 n 個數

直接上程式碼更容易理解：

package Sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int []arr = {17, 3, 25, 14, 20, 9};
        insertSort(arr);
    }

    public static void insertSort(int [] arr) {
        for(int i = 1; i < arr.length; i++) {
            // 定義待插入的數
            int insertVal = arr[i];
            int insertIndex = i-1; // 即 arr[i] 前面這個數的索引

            // 給insertVal找到插入的位置
            // 1.保證在insertVal找插入位置, 不越界
            // 2.insertVal < arr[insertIndex]待插入的數還沒找到插入位置
            // 3.就需要將arr[insertIndex] 後移
            while(insertIndex >= 0 && insertVal < arr[insertIndex]) { 
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            // 當退出while循環時,說明插入的位置找到,insertIndex + 1
            arr[insertIndex + 1] = insertVal;

            System.out.println("第"+(i+1)+"輪插入排序後 "+Arrays.toString(arr));
        } 
    }
}

output

第2輪插入排序後 [3, 17, 25, 14, 20, 9]
第3輪插入排序後 [3, 17, 25, 14, 20, 9]
第4輪插入排序後 [3, 14, 17, 25, 20, 9]
第5輪插入排序後 [3, 14, 17, 20, 25, 9]
第6輪插入排序後 [3, 9, 14, 17, 20, 25]

## 速度測試

一樣用八萬筆數據來做插入排序

public static void main(String[] args) {
    // int []arr = {17, 3, 25, 14, 20, 9};
    int arr[] = new int[80000];
    for(int i = 0; i < 80000; i++) {
        arr[i] = (int)(Math.random() * 80000);
    }
    Instant startTime = Instant.now();
    insertSort(arr);
    Instant endTime = Instant.now();
    System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}

output

共耗時：1400 毫秒
共耗時：1395 毫秒
共耗時：1404 毫秒
共耗時：1402 毫秒

測試了三遍之後大概都是 1.4 秒，相較於泡沫排序法較快，但是較選擇排序法慢了一點。

## 時間複雜度
假設今天要對一陣列使用插入排序法由小到大排序。

### 最佳：O(1)
當資料順序恰好為由小到大時，每輪只需比較 1 次。
### 平均：O(n^2^)
第 n 筆資料，平均需要比較 `n/2` 次。
### 最差：O(n^2^)
當資料順序恰好為由大到小時，第 k 回合需比 k 次。

## 存在的問題

此時有一個陣列 arr = {2,3,4,5,6,1}，這時需要插入的數 1 為陣列中最小值，它所需要進行的過程為：

{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}

也就是說，當需要插入的數是較小的數時，後移的次數明顯增多，對效率有影響。

針對這個問題，有了更高效的插入排序改進版本—**希爾排序法(Shell Sort)**