在直接插入排序中,若待排序列为“正序”,则时间复杂度可提高至O(n),同时直接插入排序更适合数据量较少的排序。

希尔排序依据此,对直接插入排序进行了改进。

基本思想是:将待排序列划分成几组,减少参与直接插入排序的数据量,当经过几次分组排序后,待排序列已基本有序,这是再对所有的记录实施直接插入排序。

具体步骤为:取步长d(一般d=n/2),将所有距离为d的记录构成一组,从而将整个待排序列分割成d个子序列,再对每个子序列分别做直接插入排序,然后缩小d直到d=1。

/* 希尔排序 */
void ShellSort(int a[], int n)
{
    // 步长选法:d1 = n/2, di+1 = di/2
    int d;
    int i, j, tmp;
    for (d=n/2; d>0; d=d/2)
    {
        // 使用直接插入排序的方法
        // 将此for中的d换成1,即为直接插入排序算法
        for (i=d; i -1 && tmp < a[j])
            {
                a[j+d] = a[j];
                j = j - d;
            }
            a[j+d] = tmp;
        }
    }
}

希尔排序同直接插入排序一样,只需一个辅助空间。

希尔排序的时间复杂度约为O(n1.3)。

关于步长,到目前为止,还没有人找到一种最好的步长序列。

直接插入排序相当于希尔排序d=1的情况。