希尔排序(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时的排序过程:  一个清晰的过程定义如下图所示:  ## 实现 ``` 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. 赏 Wechat Pay Alipay GDB 新手指南 Python 2.7 + SQLite3 编码问题