直接插入排序，時間復(fù)雜度為O(n^2)

分析：假設(shè)是從小到大排序曲初，將數(shù)組分為已經(jīng)排序的與未排序的囚玫，將未排序的元素逐一插入有序的那部分坑雅，直至所有的元素都在有序的部分。

• 將長度為n的第一個元素視作有序的那部分S，取無序的那部分的第一個元素按声，即是數(shù)組的第二個元素插入S膳犹；
• 將第三個元素插入S；
  .....
• 第n個元素插入S签则，排序完成须床；

將元素T插入有序數(shù)組S的方法：從尾到頭取S的元素S[i]，若S[i]>T渐裂，將S[i]向右移動一位豺旬，如此繼續(xù)比較S[i-1]、S[i-2]...柒凉，直到出現(xiàn)不比T小的元素族阅，結(jié)束移動并插入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--;//索引移動
            }

            //移動結(jié)束，新人填坑
            arr[j + 1] = tmp;
        }
    }

折半插入排序林艘，其實是在有序組做查找時用了“二分法查找”盖奈，提高效率

/**
     * 折半插入排序法，直接插入排序的改進版狐援，
     * 采用二分查找法钢坦，減少比較次數(shù)
     *
     */
    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;
        }
    }