插入排序
直接插入排序的基本思想：每次将一个待排序的记录，按其keyword的大小插入到前面已经排好的子序列中的适当位置，直到所有记录插入完毕为止。
假设数组为A[0...n-1]
1.初始时，A[0]自成1个有序区,无序区为A[1....n-1]。令i = 1；
2.将A[i]并入当前的有序区A[0...i-1]中形成A[0...i]的有序区间
3.i++并反复第二步直到i == n-1
至此排序完毕
代码实现如图:
效率分析：
稳定
空间复杂度O(1)
时间复杂度O(n2)
最差情况：反序。须要移动n*(n-1)/2个元素
最好情况：正序，不须要移动元素
数组已是排序或者接近顺序。插入排序的效率最好的情况是O(n)，最坏的情况执行时间和平均情况执行时间均为O(n2)
通常插入排序呈现出二次排序算法中的最佳性能。
插入算法进阶---->希尔排序
希尔排序是根据插入排序来实现的。
希尔排序根据插入排序的以下两点性质而提出的改进方法：
1.插入排序在对几乎已经顺序排列的数据操作时，效率高，即可以达到线性排序的效率。
2.插入排序一般说来是低效的。因为插入排序没次数据只能移动一位。
希尔排序算法利用了插入排序的简单，同时又避免了插入排序每次交换数据只能消除一个逆序的缺点。所以希尔排序一般不是交换相邻的元素，而是跳跃一段距离进行交换。
算法思想：
希尔排序通过将整个待排序元素序列分成若干个子序列（由相隔某个“增量”的元素组成）分别直接进行插入排序。然后依次缩减增量再次进行排序，待整个序列中的元素基本有序，即增量足够小时，再对全体进行元素进行一次直接插入排序。因为最后一次插入排序是基于有序序列的插入排序，效率是很高的。因此希尔排序在时间上是优于直接插入排序的。
步长序列：
步长序列是希尔排序的核心部分。只要最终步长为1，任何步长序列都可以工作。算法最开始以一定的步长进行排序。初次排序完毕之后，再次根据既定步长进行排序。最终算法是以步长为1进行排序。当步长为1的时候，算法演变为插入排序。
最优时间为O（n），不稳定
java代码：
iOS代码：
