直接插入排序，时间复杂度为O(n^2)

分析：假设是从小到大排序，将数组分为已经排序的与未排序的，将未排序的元素逐一插入有序的那部分，直至所有的元素都在有序的部分。

• 将长度为n的第一个元素视作有序的那部分S，取无序的那部分的第一个元素，即是数组的第二个元素插入S；
• 将第三个元素插入S；
  .....
• 第n个元素插入S，排序完成；

将元素T插入有序数组S的方法：从尾到头取S的元素S[i]，若S[i]>T，将S[i]向右移动一位，如此继续比较S[i-1]、S[i-2]...，直到出现不比T小的元素，结束移动并插入T。

public static void insertSort(int[] arr) {
        int len = arr.length;
        int tmp;
        for (int i = 1; i < len; i++) {
            tmp = arr[i];//用来比较的目标元素
            int j = i - 1;//取有序组的尾部索引

            //移动，只要比目标大，就往右移，给新人空出位置
            while (j >= 0 && tmp < arr[j]) {
                arr[j + 1] = arr[j];//有序组元素比目标元素大，说明目标元素需要放入其后，向右移动一位
                j--;//索引移动
            }

            //移动结束，新人填坑
            arr[j + 1] = tmp;
        }
    }

折半插入排序，其实是在有序组做查找时用了“二分法查找”，提高效率

/**
     * 折半插入排序法，直接插入排序的改进版，
     * 采用二分查找法，减少比较次数
     *
     */
    public static void insertHalfSort(int[] arr) {
        int Len = arr.length;
        int tmp,high,low,midle;
        for (int i = 1; i < Len ; i++) {
            tmp = arr[i];
            low = 0; high = i -1;
            
            //二分法查找目标元素的插入位置
            while(low <= high){
                midle = (low + high)/2;
                if(tmp > arr[midle]){
                    low = midle + 1;
                }else {
                    high = midle - 1;
                }
            }
            
            //有序组中目标位置及往后的元素，向后移动一位
            for(int j =i -1; j >= high +1;j --){
                System.out.println(j);
                arr[j + 1] = arr[j];
            }
            
            //插入目标元素
            arr[high + 1] = tmp;
        }
    }