希尔排序(Shell sort)

gaunthan Posted on Jan 5 2017

? Sorting ? ? Algorithm ?

## 思想
**希尔排序**（Shell sort）的名称源于它的发明者 Donald Shell，它通过比较相距一定间隔的元素来工作。各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。由于这个原因，希尔排序有时也叫做**缩小增量排序**（diminishing inc sort）。

希尔排序使用一个序列$h_1, h_2, . . ., h_t$，叫做**增量序列**（increment sequence）。在使用增量$h_k$的一趟排序之后，对于每一个$i$有$A[i] ≤ A[i+  h_k]$：所有相邻增量$h_k$的元素都被排序了。此时称该序为**$h_k$−排序**。

增量序列的一种流行的选择是使用Shell建议的序列：
$$ h_t = \lfloor {N \over 2} \rfloor 和 h_k = \lfloor {h_{k+1} \over 2} \rfloor$$

## 示意
下图展示了增量为3时的排序过程：
![](https://leanote.com/api/file/getImage?fileId=58c79a5fab64417e390024f4)

一个清晰的过程定义如下图所示：
![](https://leanote.com/api/file/getImage?fileId=58c79a5fab64417e390024f5)

## 实现
```
void ShellSort(ElemType a[], int n)
{
    int i, j, inc;
    ElemType key;
    for (inc = n / 2; inc > 0; inc /= 2) {
        // 相隔inc的元素进行直接插入排序
        for (i = inc; i < n; ++i) {
            key = a[i];
            for (j = i - inc; j >= 0 && a[j] > key; j -= inc)
                a[j + inc] = a[j];
            a[j + inc] = key;
        }
    }
}
```

## 好的增量序列的共同特征

* 最后一个增量必须为1，以保证算法的正确性。
* 尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。假设某趟操作增量为4，其下一趟操作增量为2，则该趟操作是不必要的，因为下一趟操作已经完成本趟的工作。

## 运行效率分析
在希尔排序开始时，增量较大、分组较多、每组的记录数目少，故各组内直接插入较快。后来增量$h_k$逐渐缩小、分组数逐渐减少，但由于已经按$h_k$距离排过序，使得文件接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。

希尔排序的平均时间效率与其增量序列有关，如使用Hibbard增量的希尔排序的时间复杂度为$O(n^{3 \over 2})$。对于中等大小规模的排序数据，希尔排序表现良好，但对规模较大的数据则不是最优选择。对于大规模数据排序，使用快速排序能够获得更好的效率。但是，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，而快速排序在最坏的情况下执行的效率会非常差。

## References

- MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010.