* 插入排序
* 通过构建有序序列，对于未排序数据，在已经排序的序列中从后向前扫描，找到相应的位置并插入。
* 步骤：
* 1, 从第一个元素开始，该元素可以被认为已经被排序
* 2, 取出下一个元素，在已经排序的元素中从后向前扫描
* 3, 如果该元素（已经排序的）大于新元素，将该元素移至下一个位置
* 4, 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
* 5, 将该元素插入到该位置中
* 6, 重复步骤2
*使用场景：部分有序
* 时间复杂度O(n^2)
public static void main(String[] args){Integer[] a = { 23, 21, 4, 6, 7, 5, 11, 1};show(a);insertionSort(a);System.out.println(isSorted(a));show(a);}//普通插入排序public static void insertionSort(Comparable[] array){int length = array.length;for(int i = 1; i < length; i++){//将a[i]插入到a[i - 1]、a【i -2】。。。之中for(int j = i; j > 0 && less(array[j], array[j - 1]); j--){//在排序好的里面，找到比 j 大的就交换，直到j - 1小于0终止exch(array, j, j - 1);//交换//show(array);}// System.out.println();}}//比较函数，v小于w就返回真public static boolean less(Comparable v, Comparable w){return v.compareTo(w) < 0;}//交换函数public static void exch(Comparable[] array, int i, int j){Comparable temp = array[i];array[i] = array[j];array[j] = temp;}//打印函数public static void show(Comparable[] array){for(int i = 0; i < array.length; i++){System.out.print(array[i] +" ");}System.out.println();}//测试元素是否有序public static boolean isSorted(Comparable[] a) {//测试元素是否有序for (int i = 1; i < a.length; i++) {if (less(a[i], a[i - 1])) {return false;}}return true;}开始：23 21 4 6 7 5 11 1
第一个元素开始：21 23 4 6 7 5 11 1
第二个元素：21 4 23 6 7 5 11 1
4 21 23 6 7 5 11 1
三：4 21 6 23 7 5 11 1
4 6 21 23 7 5 11 1
4 6 21 7 23 5 11 1
4 6 7 21 23 5 11 1
4 6 7 21 5 23 11 1
4 6 7 5 21 23 11 1
4 6 5 7 21 23 11 1
4 5 6 7 21 23 11 1
4 5 6 7 21 11 23 1
4 5 6 7 11 21 23 1
4 5 6 7 11 21 1 23
4 5 6 7 11 1 21 23
4 5 6 7 1 11 21 23
4 5 6 1 7 11 21 23
4 5 1 6 7 11 21 23
4 1 5 6 7 11 21 23
1 4 5 6 7 11 21 23
true
1 4 5 6 7 11 21 23
插入排序优化
避免边界检测
在插入排序的实现中先找到最小的元素，将其置于数组的第一位置，可以省掉循环内的判断条件 j < 0;能够省略判断条件的元素称为哨兵
public static void insertionSortY(Comparable[] array){int length = array.length;for(int i = length - 1; i > 0; i--){//找到最小元素，置于数组的第一个位置if(less(array[i],array[i - 1]))exch(array, i, i - 1);}for(int i = 1; i < length; i++){for(int j = i; less(array[j], array[j - 1]); j--){exch(array, j, j - 1);}}}不需要每次都交换的插入排序
将当前的需要插入的值temp暂时性保存起来，如果在已经排好序中的数字里面，当前temp比排好顺序中的 小，将排好序的右移
public static void insertionSortX(Comparable[] array){int length = array.length;for(int i = 1; i < length; i++){Comparable temp = array[i];//暂时当前需要插入的值int j = i;暂时当前需要插入的值的索引for(; j > 0 && less(temp,array[j - 1]); j--){//在已经排好序中的数组里，如果当前temp比排好序中的小，排好序的j - 1就右移一位。array[j] = array[j - 1];//大的右移//show(array);}array[j] = temp;//show(array);}}