插入排序

什么是插入排序？
通俗理解就是，把n个待排序的元素看成一个有序表和无序表，有序表最开始为1，无序表为n-1，
每进行一轮排序，从无序表中取出第一个元素，将其与有序表元素进行比较，将其放入一个合适的位置。
最后形成的一个完整有序表。

时间复杂度：O(n^2)
稳定度：稳定

代码实现

 public static void insertSort2(int[] arr) {
       int value;//从无序表中取出来要进行插入的值
       int index;//被插入的索引位置
       for (int i = 1; i < arr.length; i++) {
           //打印
           System.out.println("第" + (i - 1) + "轮" + Arrays.toString(arr));
           //取出插入值
           value = arr[i];
           //index设置为value的初始位置
           index = i;
           //index必须 >= 1 防止溢出，与index的前一个元素进行比较
           while (index >= 1 && value < arr[index - 1]) {
               //元素后移一位
               arr[index] = arr[index - 1];
               index--;
           }
           //insertIndex变化则进行插入
           if (index != i) {
               arr[index] = value;
           }
       }
   }

@Test
   public void insertSort2Test() {
   	//随便测试
       int[] arr = {101, 34, 119, 1, -1, 98,3,5,323,125,743};
       insertSort2(arr);
   }