排序算法2：插入排序

一、直接插入排序

1.算法思想及图解

（1）算法的思想

当对位置 i 处的元素进行排序时，[0,i-1]上的元素一定是已经有序的了，然后将i出的元素，和i-1处元素开始到0处元素截止依次进行比较，如果[i-1,0]处的元素大于i处元素，则将大于i处的元素依次右移一个位置，直到找到比i处小的位置，然后在这个比i处小的位置的后面以为将i处的元素放置上去。

（2）图解

image

2.算法代码实现（java）

image

3.复杂度

按照最坏的情况考虑，如果提供的数组刚好是逆序的话，那么i处的元素插入时就需要比较i-1次，这样总共需要比较的次数就是1+2+3+...+N次，所以时间复杂度就是O(N^2);算法中仅仅用了一个临时变量，所以空间复杂度是O(1).

二、二分法插入排序

二分法插入排序是在直接插入排序的基础上对元素的比较采用了二分查找法进行优化，加快了查找的速度。

1.算法思想

二分插入排序在直接插入排序基础上使用二分查找快速找到需要向右移动的元素的开始的图标，然后将i处的元素插入到相应的位置。

2.算法代码实现

image

三、希尔排序

1.算法思想

    希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。

以下为图解：

image

2.算法代码实现

image