【圖解算法】排序算法——插入排序

插入排序（insertion sorting）

大體含義是這樣的，想我們在打撲克牌理牌時的思路一樣，來一張撲克牌做一次插入操作。

下面我們給出普通版和優化版的插入排序

public int [] insertionSort(int [] arr){
        for (int i = ; i<arr.length;i++){
            for (int j = i; j> && arr[j] < arr[j-];j--){
                int temp = arr[j];//循環比較兩個相鄰的值，滿足排序條件做交換，不滿足跳出目前這層循環
                arr[j] = arr[j-];
                arr[j-] = temp;
            }
        }
        return arr;
    }

    public int [] insertionSortPlus(int [] arr){
        for (int i = ; i<arr.length;i++){
            int x = arr[i]; //記錄目前抽的數
            int j;          //記錄數的位置
            for (j = i; j> && arr[j-] >x;j--){
                arr[j] = arr[j-];//挪位置
            }
            arr[j] = x;     //最後處理目前抽的數的位置歸宿 需要注意的是這裡的 j 是上面 for 循環退出時的值
        }
        return arr;
    }
           

優化版的算法主要在于交換的次數上的優化，在數組本身的順序較為良好的情況下，這種插入排序的優勢可以展現出來，因為不用向冒泡或是選擇排序那樣必須走完内層循環，找到一個合适的時機可以提前跳出内層循環。

圖解算法目錄

【圖解算法】排序算法——冒泡排序、選擇排序

【圖解算法】排序算法——插入排序

【圖解算法】排序算法——歸并排序

【圖解算法】排序算法——快速排序

【圖解算法】Java GC算法

【圖解算法】排序算法——堆排序

【圖解算法】并查集 —— 聯合查找算法

【圖解算法】排序算法——計數排序

Gif Power By https://visualgo.net