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

2、希尔排序及算法实现

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

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

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

下面是直接插入排序的算法实现代码。

InsertSort.java

测试结果：

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

ShellSort.java 

测试结果：

既然希尔排序是直接插入排序的改进版，我们就来测试一下希尔排序是否真的比直接插入排序更快？ 

代码：

InsertSortPkShellSort.java

测试结果：

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