算法（一）之排序算法（三）——直接插入排序（InsertSort

直接插入排序也是八大排序算法之一，它还是希尔排序的前身。其排序原理是：

通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。我们假设第一个数是排好的，之后的数对排好的部分从后向前比较并逐一移动。

看了这个原理其实我还是不太懂，那我们就用实际操作流程来进行说明。

如现在有一组数据：[3, 1, 8, 6, 2, 5, 9, 4, 7]

使用插入排序对这组数据进行排序，具体流程：

      3    1    8    6    2    5    9    4    7

第一趟排序：假设3是排好的，现在我要把第二个数放进来构成一个有序序列。因为1<3所以只能插入到3的前面，所以就变成了：

      1    3    8    6    2    5    9    4    7

第二趟排序：现在1和3已经构成了有序序列，接着把下一个数继续插入到有序序列中重新变成一个新的有序序列。因为8>3所以只能插入到3的前面，所以就变成了：

      1    3    8    6    2    5    9    4    7

继续这种操作下去最后我们就可以得到一个有序序列，现在有张图更能体现插入排序。

思路很简单，现在直接上代码：

      public static void inserSort(int[] array){
            for(int i = 1;i < array.length; i++){
                 int j = i;
                 int target = array[i];  //要插入的数据
                 while( j > 0 && target < array[j-1] ){  
                      array[j] = array[j-1];    //把当前位置的数据变成上一个数据，因为插入了后前面一个数据往后面移动了一位
                      j--;    //继续向前寻找看看要插入的数是不是比前面的数小
                 }
                 array[j] = target;    //最后还要把插入的数据放到指定的位置上去
            }
      }

直接插入排序的应用场景： 适用于3到7个数据的排序。