时间复杂度：O(N^2)
额外空间复杂度：O(1)
是否可实现稳定性：是
思路：
插入排序的过程类似于打扑克牌抓牌的过程，每次把抓到小的排插到前面
插入排序的外层循环，用来控制数组的下标i从1开始；内层循环，从j=i-1开始，比较j和j+1的大小，然后依次向前两两比较，每次把当前传入的数的最小值放到最前面
例子：
比如一组数字 {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;
}
/*
* 相当于打牌 抓牌的过程 小的插前面
* 外层循环 初始化i = 1
* 内循环 j = i-1 当j>=0并且arr[j]>arr[j+1] 交换位置 j--继续循环，往前找
* 直到循环到下标0
* 把每次内循环找的的最小的数放到最前面
* */
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];
}
在这里还可以帮助理解插入排序是否稳定，如我刚才举的例子，当1=1时，不叫唤位置，所以两个1在排序前后相对顺序没有变，印证了插入排序是稳定的。
