插入排序

思想：把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()));
    }
}