時間復雜度：O(N^2)
額外空間復雜度：O(1)
是否可實現(xiàn)穩(wěn)定性：是
思路：
插入排序的過程類似于打撲克牌抓牌的過程茬缩，每次把抓到小的排插到前面
插入排序的外層循環(huán)蝇庭，用來控制數(shù)組的下標i從1開始；內(nèi)層循環(huán)郎嫁，從j=i-1開始秉继，比較j和j+1的大小，然后依次向前兩兩比較泽铛，每次把當前傳入的數(shù)的最小值放到最前面
例子：
比如一組數(shù)字 {2,1,1,6,8}
第一次比較1<2 所以交換2和1的位置尚辑，此時排序的順序是1 2 1 6 8
第二次傳入1 首先比較 2>1 所以交換2和1的位置，然后比較 1 = 1 所以不交換盔腔，這一輪比較的排序結果是1 1 2 6 8
依次類推
代碼：
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
/*
* 相當于打牌 抓牌的過程 小的插前面
* 外層循環(huán) 初始化i = 1
* 內(nèi)循環(huán) j = i-1 當j>=0并且arr[j]>arr[j+1] 交換位置 j--繼續(xù)循環(huán)杠茬，往前找
* 直到循環(huán)到下標0
* 把每次內(nèi)循環(huán)找的的最小的數(shù)放到最前面
* */
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[]arr,int i ,int j){
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
在這里還可以幫助理解插入排序是否穩(wěn)定，如我剛才舉的例子弛随，當1=1時瓢喉，不叫喚位置，所以兩個1在排序前后相對順序沒有變舀透，印證了插入排序是穩(wěn)定的栓票。
