算法03 七大排序之：直接插入排序和希尔排序

作者：nnngu
GitHub：https://github.com/nnngu
博客园：http://www.cnblogs.com/nnngu
简书：https://www.jianshu.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts

---

上一篇总结了直接选择排序和堆排序，这一篇要总结的是插入排序中的直接插入排序和希尔排序，我们主要从以下几点进行总结。

1、直接插入排序及算法实现

2、希尔排序及算法实现

3、直接插入排序PK希尔排序

1、直接插入排序及算法实现

什么是直接插入排序呢？直接插入排序的基本思想是：每次从无序序列中取出第一个元素插入到已经排好序的有序序列中，从而得到一个新的，数量加1的有序序列。

1-1、示意图

下面是直接插入排序的图解说明。

2、希尔排序及算法实现

希尔排序是直接插入排序的一种更高效的改进版本，又称为“缩小增量排序”。

2-1、示意图

从测试结果可以看出，希尔排序比直接插入排序更快。