思想：把n個待排序的元素看成一個有序表和一個無序表，開始時，有序表只包含一個元素無序表包含n-1個元素，排序過程中每次從無序表中取出一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表的適當位置，使之成為新的有序表

public class InsertSorting {

    public static int[] instertSort(){
        int[] arr = {101,34,39,1,-1,1,90,123};

        for (int i =1; i<arr.length; i++) {
          int insertVal = arr[i];   //要插入的值
          int insertIndex = i-1;    //要插入的前一個位置
          while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
              arr[insertIndex+1] = arr[insertIndex];
              insertIndex--;
          }
          arr[insertIndex+1] = insertVal;
        }
        return arr;

    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(instertSort()));
    }
}