[Thm]使用 Hibbard 增量的谢尔排序的最坏情形运行时间是 $\Theta(N^{3/2})$.
Introduction.
谢尔排序(Shellsort) 的名称源于它的发明者 Donald Shell. 该算法是冲破二次时间屏障的第一批算法之一.
谢尔排序最核心的东西是其采用的增量序列(increment sequence) $1=h_1, h_2,\ldots, h_t$. 一般 $h_t < N/2$. （当然也可以认为是递减序列 $h_t, h_{t-1},\ldots,h_2,h_1=1$.）
依次按 $k=t,t-1,\ldots,2,1$ 的次序, 将要排序的序列 $a_1,a_2,\ldots, a_N$ 中间隔为 $h_k$ 的子序列（共有 $h_k$ 个）进行插入排序.
不同的增量序列, 对于排序的性能有着明显的影响.
一些常见及常用的序列有:
Shell 增量序列(并不好): $h_t=[N/2]$, $h_k=[h_{k+1}/2]$. （此时 $t$ 约为 $[\log N]-1$）
Hibbard 增量序列: $1,3,7,15,31,\ldots,2^t-1$.
Sedgewick 提出了几种增量序列, 其中最好的是 $\{1,5,19,41,109,\ldots\}$, 该序列中的项或者是 $9\times 4^i-9\times 2^i+1$, 或者是 $4^i-3\times 2^i+1$. 确切地,
| $i$ | 0 | 1 | 2 | 3 | 4 |
| $9\times 4^i-9\times 2^i+1$ | 1 | 19 | 109 | 505 | 2161 |
| $4^i-3\times 2^i+1$ | -1 | -1 | 5 | 41 | 209 |
Remark:
使用 Hibbard 增量序列的谢尔排序的平均情形运行时间基于模拟的结果被认为是 $O(N^{5/4})$, 但是没有人能够证明该结果.
Pratt 已经证明, $\Theta(N^{3/2})$ 的界适用于广泛的增量序列.
谢尔排序的性能在实践中是完全可以接受的, 即使是对于数以万计的 $N$ 仍是如此. 编程的简单特点使得它成为对适度的大量输入数据经常选用的算法. 不过相较于快速排序, 谢尔排序仍有不足. 具体参见下面wiki上的描述.
References:
Mark Allen Weiss, 数据结构与算法分析 C++描述（第三版），张怀勇等译.