原理：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
排序过程:
有一组数 {5 , 9 , 2 , 6 , 4 , 1 , 8 , 7}
把上述数组看为有序数组和无序数组,那这组数据中有序数组是什么呢？何不把数组的第一个数 {5}看成一个有序 其余的{9 , 2 , 6 , 4 , 8 , 7}作为无序部分。
有序部分 ： {5}
无序部分 : {9 , 2 , 6 , 4 , 1 ,8 , 7}
第二次插入: 从无序部分拿出 9 , 5> 9? 否 不需要插入到有序。
此时有序无序无变化
第三次插入:从无序部分拿出 2 ， 5 > 2 ? 是 插入到有序
有序部分:{2,5}
无序部分:{9,6,4,1,8,7}
第四次插入:从无序部分拿出6， 5 >6 ？否,再比较 2 >6 ? 否 ,有序无序无变化
第五次插入:从无序部分难处4， 5 >4 ? 是,将 4 插入到 有序{2,4,5} 再比较 2 > 4？否,不需要调换位置
。。。。。
。。。。。
代码实现
时间复杂度:插入排序的时间复杂度分析。在最坏情况下，数组完全逆序，插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，……，插入第N个元素，要考虑前N - 1个元素。因此，最坏情况下的比较次数是1 + 2 + 3 + ... + (N - 1)，等差数列求和，结果为N^2 / 2，所以最坏情况下的复杂度为O(N^2)。
最好情况下，数组已经是有序的，每插入一个元素，只需要考查前一个元素，因此最好情况下，插入排序的时间复杂度为O(N)。
