希尔排序

希尔排序（Shellsort）的名称源于它的发明者 Donald Shell，该算法是冲破二次时间屏障的第一批算法之一，不过，从它的发现之日起，又过了若干年后才证明它的亚二次时间界。它通过比较相距一定间隔的元素来工作，各躺比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。由于这个原因，希尔排序有时也叫作缩小增量排序（diminishing increment sort）。

希尔排序使用一个序列 ，叫作增量序列（increment sequence）。在使用增量 的一趟排序之后，对于每一个 就有 （这里它是有意义的），所有相隔 的元素都被排序。

排序的一般做法是，对于 中每一个位置 ，把其上的元素放到 中间的正确位置上。增量序列的一种流行（但是不好）的选择是使用 Shell 建议的序列：和。

希尔排序的运行时间依赖于增量序列的选择，而证明可能相当复杂。希尔排序的平均情形分析，除最平凡的一些增量序列外，是一个长期未解决的问题。

定理一：使用希尔增量时希尔排序的最坏情形运行时间为 。

定理二：使用 Hibbard 增量的希尔排序的最坏情形运行时间为 。