Question

希尔排序时间复杂度O(n¹.³)中的1.3是怎么来的？

Answer 1

1、首先希尔排序是一种递减增量的排序算法，下面使用大小为9的数组：54、26、93、17、31、44、55、20。

2、令数据间隔为3，将该数组分成三个子数组，如下图所示，为下图中灰色的部分。

3、对每一个子数组都进行插入排序操作，将排序好的子数组合并到一个数组当中。这个时候，会发现，每个数字都会务必接近他应该存在的位置。

4、这是间隔为3的子数组排序后的结果，发现该排序后的数列非常接近我们需要的递减或者递增序列。下一步只需要，缩小间隔进行重复性操作即可

5、最后改变间隔，使间隔变成4，这个时候子数组反而有4组。这个说明希尔排序（shell sort）是一个不稳定的排序。

Answer 2

希尔排序时间复杂度的指数具体数值目前是比较模糊的，并没有一个统一的取值，它取决于增量。但已知的就是指数不是平方级的，即不是O(n^2)，而是O(n^m(m>1<2))也就是说指数m不会大于等于2是介于[1,2)半闭半开区间。