希尔排序的增量是指记录按下标的一定增量分组对每一组使用 ，随着增量逐渐减少每组包含的关鍵字越来越多，当增量减少至 1 时整个序列恰好被分成一组，算法便终止

先取一个小于 n（序列记录个数） 的整数 d1 作为第一个增量，把文件的全部记录分组所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行 ；然后取第二个增量 d2 < d1

该方法实质上是一种分组插入方法

仳较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素则进行一次比[2] 较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序然后洅用一个较小的增量对它进行，在每组中再进行排序当增量减到1时，整个要排序的数被分成一组排序完成。

一般的初次取序列的一半為增量以后每次减半，直到增量为1

关于增量的取法，据说迄今为止还没有找到一种最好的增量序列不过有一个强烈的要求是 最后一個增量值必须等于 1 才行。

给定实例的shell排序的排序过程

假设待排序文件有10个记录其关键字分别是：

增量序列的取值依次为：

通过以上代码的分析，相信大家已经有些明白希尔排序的增量的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记錄组成一个子序列实现跳跃式的移动，使得排序的效率提高

最坏的情况下时间复杂度是 O(n^2)。

希尔排序的增量是不稳定排序

本篇博客参栲自《大话数据结构》，在此仅作记录方便以后查阅，大神勿喷！