插入排序

直接插入排序的基本思想：每次将一个待排序的记录，按其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代码：

java

iOS代码：

iOS