数据结构与算法——希尔排序（引例、希尔增量序列、原始希尔排序、代码、时间复杂度、Hibbard增量序列、Sedgewick增量序列）

希尔排序（by Donald Shell）

引例

给以下序列进行排序：

先以5的间隔进行插入排序：

再以3的间隔进行插入排序：

最后再以1为间隔做插入排序，即常规插入排序 ，得到排序完成的序列：

希尔增量序列

• 定义增量序列
• 对每个 进行“ -间隔”排序（ ）

注意：“ -间隔”有序的序列，在执行“ -间隔”排序后，仍然是“ -间隔”有序的。

原始希尔排序

代码（C语言）

希尔排序在插入排序的基础上进行改进

void Shell_Sort(ElementType A[], int N)
{
    for(D = N / 2; D > 0; D /= 2 )  //原始希尔增量序列
    {
        for(P = D; P < N; P++)   //插入排序
        {
            Tmp = A[P];
            for(i = P; i >= D && A[i-D] > Tmp; i -= D)
                A[i] = A[i-D];
            A[i] = Tmp;
        }
    }
}

时间复杂度

最坏情况：

（ 表示上界， 表示下界， 即表示上界也表示下界，为正常值。）

原始希尔序列并不好用，我们举下面的例子：

可以发现，8、4、2间隔的插入排序并没有给序列成功排序，最后还是通过间隔1来完成排序的功能。

有结论：

增量元素不互质，则小增量可能根本不起作用。

更多增量序列

Hibbard增量序列

• ——相邻元素互质
• 最坏情况：
• 猜想：

Sedgewick增量序列

• { 1,5,19,41,109,...}—— 或
• 猜想：

void ShellSort( ElementType A[], int N )
{ /* 希尔排序 - 用Sedgewick增量序列 */
     int Si, D, P, i;
     ElementType Tmp;
     /* 这里只列出一小部分增量 */
     int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
     
     for ( Si=0; Sedgewick[Si]>=N; Si++ ) 
         ; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
 
     for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] )
         for ( P=D; P<N; P++ ) { /* 插入排序*/
             Tmp = A[P];
             for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
                 A[i] = A[i-D];
             A[i] = Tmp;
         }
}

end