希尔排序是插入排序的扩展。希尔排序的一个特点是：子序列的构成不是简单的逐段分割，而是将相隔某个增量的记录组成一个子序列。希尔排序的一个关键是：其步长（也就是增量）的取法，通常认为步长序列中的数字互质很重要。

希尔排序的C/C++代码实现：

void shell_insert(int sort_array[], int length, int h)
{
    int i, j, tmp;
    for (i = h; i < length; ++i)
        if (sort_array[i] < sort_array[i-h]) {
            tmp = sort_array[i];
            sort_array[i] = sort_array[i-h];
            for (j=i-h*2; j>=0 && tmp<sort_array[j]; j-=h)
                sort_array[j+h] = sort_array[j];
            sort_array[j+h] = tmp;
        }
}

void shell_sort(int sort_array[], int length)
{
    int h;
    for (h = 1; h < (length - 1) / 9; h = h * 3 + 1);
    while (h >= 1) {
        shell_insert(sort_array, length, h);
        h /= 3;
    }
}

和直接插入排序相比，这里的shell_insert只做了两处修改：
1. 前后记录位置的增量不再是1，而是h；
2. sort_array[0]已不能再作为监视哨，而只能作为一个暂存单元，因为式子j -= h并不一定能使j值到达0。因此，这里干脆用一个temp来代替sort_array[0]做为暂存单元，而让sort_array[0]也加入排序，这样的做法也更通用。
继续阅读 →