1.插入排序

一般分两种 

直接插入排序和希尔排序

直接插入排序：

（1）对于一个有序的数组插入元素i，先把i和数组[end]比较，如果大于，直接加入到最后，如果小于

则于数组[end-1]进行比较，类比同理，知道找到大于的end的值。

 (2)对于一个没有或者说不知道有没有排序的数组，我们需要怎么办？

首先我们可以把这个数组看成很多的小的。

代码解析：用intsertValue来记录要插入的值，两个for，第一个for来遍历一遍数组，第二个for来做判断，判断要插入的数是不是比前一个要小，如果小

就需要把插入的数向前移动，即把前面的数赋值给右边，arr[j+1] = arr[j]，一直到比插入的数要大的时候停止，并把缺失的insertVallue值赋值给arr[j+1]

    public static int[] insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i];
            int j = i - 1;
            //从右向左比较元素的同时，进行元素复制
            for(; j >=0 && insertValue < arr[j]; j--){//如果右边的比要插入的值小，把左边的赋值给右边
                arr[j+1] = arr[j];
            }
            //insertValue的值插入适当位置
            arr[j+1] = insertValue;
        }
        return arr;
    }}