插入排序

直接插入排序的基本思想：每次将一个待排序的记录，按其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.插入排序一般说来是低效的。因为插入排序没次数据只能移动一位。

希尔排序算法利用了插入排序的简单，同时又避免了插入排序每次交换数据只能消除一个逆序的缺点。所以希尔排序一般不是交换相邻的元素，而是跳跃一段距离进行交换。

算法思想：

希尔排序通过将整个待排序元素序列分成若干个子序列（由相隔某个“增量”的元素组成）分别直接进行插入排序。然后依次缩减增量再次进行排序，待整个序列中的元素基本有序，即增量足够小时，再对全体进行元素进行一次直接插入排序。因为最后一次插入排序是基于有序序列的插入排序，效率是很高的。因此希尔排序在时间上是优于直接插入排序的。