发布网友 发布时间:2022-04-24 02:34
共2个回答
热心网友 时间:2022-06-13 03:10
1、首先希尔排序是一种递减增量的排序算法,下面使用大小为9的数组:54、26、93、17、31、44、55、20。
2、令数据间隔为3,将该数组分成三个子数组,如下图所示,为下图中灰色的部分。
3、对每一个子数组都进行插入排序操作,将排序好的子数组合并到一个数组当中。这个时候,会发现,每个数字都会务必接近他应该存在的位置。
4、这是间隔为3的子数组排序后的结果,发现该排序后的数列非常接近我们需要的递减或者递增序列。下一步只需要,缩小间隔进行重复性操作即可
5、最后改变间隔,使间隔变成4,这个时候子数组反而有4组。这个说明希尔排序(shell sort)是一个不稳定的排序。
热心网友 时间:2022-06-13 04:28
希尔排序时间复杂度的指数具体数值目前是比较模糊的,并没有一个统一的取值,它取决于增量。但已知的就是指数不是平方级的,即不是O(n^2),而是O(n^m(m>1<2))也就是说指数m不会大于等于2是介于[1,2)半闭半开区间。