希尔排序

        希尔排序是插入排序的一种，又称缩小增量排序，是直接插入排序的一种更高效改进版本，要知道什么是希尔排序首先要理解直接插入排序。

插入排序

        直接插入排序，有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。 

    举个例子：是把第一个数看成有序的，然后第二个数跟第一个数比较，比第一个数小则交换位置（插入到第一个数前面），然后前两个是有序的，如果第三个数比第二个数小，就和第二数交换，交换和后再和第一个数交换，如果比第一个小，就和第一个数交换，否则就不动了，后面再有数就还是按照这种方法，如果比他前一个数大就放这儿不动了，如果比前一个数小，就和前一个换位置，再往前比，直到不比前一个数小就停。

插入排序基思想 插入排序

希尔排序基本思想：

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

        简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

希尔排序基本思想 希尔排序