Question

希尔排序

Answer 1

希尔排序又称 缩小增量排序 ，其也属于插入排序类算法。相教于一般的插入算法、 折半插入 算法、 2-路插入 算法以及 表插入 算法，希尔排序在时间效率上更加优秀。

对于普通的插入算法，其时间复杂度为 ，且在序列有序时，可以达到最好的时间复杂度 ；而且当 较小时，由于移动的元素较少，插入排序效率也比较高。

因此，我们可以采用 分治 的思想，先将整个待排序序列分割成为若干个子序列分别进行插入排序，待整个序列「基本有序」时再对全体进行插入排序，即自底向上实现整个序列的排序。

【注】这里的子序列不是简单的逐段分割，而是将相隔某个 增量 的元素组成一个子序列，这样对子序列进行插入排序时，元素就不是一步一步移动，而是跳跃式地往前移。

其中，数组 D 为增量序列。常用的增量序列有：

希尔排序是 不稳定的、原址的 。不稳定原因在于希尔排序中不同段交换元素时会打乱相等元素初始的相对位置。