希尔排序和插入排序的关系

希尔排序是在插入排序的基础上进行的一中改进的算法，希尔排序是将一个原序列分成几个子序列，对于每个子序列来所都进行一次插入排序，而依据不同的子序列划分大小，最后子序列为1时，进行的那一次插入排序跟原来的插入排序就是一模一样的了，只不过现在的队列比原来的要有序的多。

所以希尔排序就是将原序列进行了一些整理，将其变得有序一些，而我们都知道，对于插入排序这个O（N2）级别的算法来说，越是有序的序列，它所需要的时间越少，甚至在某些情况下可以逼近O（N），这就是希尔排序对于插入排序的改良。