1. 圖示過程

插入排序圖示

2. 動圖展示

3. 文字敘述過程

• 第1趟插入：將第2個元素插入前面的有序子序列，此時前面只有一個元素，當然是有序的
• 第2趟比較：將第3個元素插入前面的有序子序列，前面的2個元素是有序的
• ......
• 第n-1趟比較：將第n個元素插入前面的有序子序列，前面n-1個元素是有序的

4. Java代碼實現(xiàn)

public static void insertionSort(int[] nums) {

    if (nums == null || nums.length < 2) {
        return;
    }

    for(int i = 1; i < nums.length; i++) {
        for(int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
            ArrayUtils.swap(nums, j, j + 1);
        }
    }

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

5. 復(fù)雜度

• 時間復(fù)雜度：O(n2)
• 空間復(fù)雜度：O(1)，只需要一個額外空間用于交換
• 穩(wěn)定性：插入排序是穩(wěn)定的排序算法，滿足條件nums[j] > nums[j + 1]才發(fā)生交換，這個條件可以保證值相等的元素的相對位置不變。

6. 優(yōu)化

上面的算法的缺點：在第i-1趟插入時，需要把第i個元素插入到前面的i-1個元素中，該算法總是從i-1個元素開始逐個比較之前的每個元素，直到找到第i個元素的插入位置，這顯然沒有利用前面0~i-1個元素已經(jīng)有序的特點

優(yōu)化：在0~i-1個有序元素給第i個元素尋找插入的位置時，使用二分查找法可以有效提高查找插入位置的時間效率，經(jīng)過優(yōu)化的插入排序稱為折半插入排序，折半插入排序的時間復(fù)雜度為O(n*logn)

/**
 * 折半插入排序
 */
public static void binaryInsertionSort(int[] nums) {

    if (nums == null || nums.length < 2) {
        return;
    }

    for(int i = 1; i < nums.length; i++) {
        int temp = nums[i];
        // 通過二分查找找到插入的位置
        int insertIndex = findInsertIndex(nums, 0, i - 1, nums[i]);
        // 插入位置之后的元素依次向后移動
        for(int j = i; j > insertIndex; j--) {
            nums[j] = nums[j - 1];
        }
        // 更新插入位置的值
        nums[insertIndex] = temp;
    }

}

/**
 * 在有序數(shù)組 nums 的[L, R]部分上，找到 value 的插入位置
 */
public static int findInsertIndex(int[] nums, int L, int R, int value) {

    while(L <= R) {
        int mid = L + ((R - L) / 2);
        if(value > nums[mid]) {
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }

    return L;

}