希尔排序（Shellsort）的名称源于它的发明者 Donald Shell，该算法是冲破二次时间屏障的第一批算法之一，不过，从它的发现之日起，又过了若干年后才证明它的亚二次时间界。它通过比较相距一定间隔的元素来工作，各躺比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。由于这个原因，希尔排序有时也叫作缩小增量排序（diminishing increment sort）。
希尔排序使用一个序列 ，叫作增量序列（increment sequence）。在使用增量
的一趟排序之后，对于每一个
就有
（这里它是有意义的），所有相隔
的元素都被排序。
排序的一般做法是，对于
中每一个位置
，把其上的元素放到
中间的正确位置上。增量序列的一种流行（但是不好）的选择是使用 Shell 建议的序列：
和
。
希尔排序的运行时间依赖于增量序列的选择，而证明可能相当复杂。希尔排序的平均情形分析，除最平凡的一些增量序列外，是一个长期未解决的问题。
定理一：使用希尔增量时希尔排序的最坏情形运行时间为 。
定理二：使用 Hibbard 增量的希尔排序的最坏情形运行时间为 。
网友评论