在计算机科学中,希尔排序(Shell Sort)是一种基于插入排序的快速的排序算法,它的目标是使数组中任意间隔 h 的元素都是有序的。
该算法由 Donald Shell 于 1959 年发明,并且在许多计算机编程教科书中作为排序算法的一个例子。它不仅速度比较稳定,而且思想简单,代码也不难。
如图所示,首先将待排序数组按一定间隔分为若干子序列,对子序列进行直接插入排序;然后缩小间隔,重新分组,对子序列进行直接插入排序;重复以上操作直至间隔为1。
希尔排序时间复杂度为 $O(n^{3/2})$,但对于大部分数据效率要优于 $O(n^2)$ 的排序,相比直接排序,希尔排序具有许多优点,例如不需要额外的空间,具有更快的排序速度。