希尔排序

Posted on | Post modified: | In
Words count in article: 392 | Reading time ≈ 1

-希尔排序算法思想

算法介绍

希尔排序又叫做缩小增量排序，其本质还是插入排序，只不过是将待排序序列按照某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量为1，就是直接排序。 增量是逐渐减小的。直接插入排序适合于序列基本有序的情况，希尔排序的每趟排序都会使整个序列变得更加有序，等整个序列基本又虚了，再进行一次直接插入排序，这样会使排序效率更高，这就是希尔排序的思想。 ---

时间复杂度

希尔排序的时间复杂度和增量选取有关，希尔排序的增量选取规则有很多，常见的增量选取规则有以下两个。
1.希尔自己提出的选取规则：
[n/2],[n/4],…,2,1
每次将增量除2向下取整，其中n为序列长度，此时时间复杂度为O（n2）

2.帕佩尔诺夫和斯塔舍维奇提出的选取规则：
2的k次方+1,…,65,33,17,9,5,3,1
其中，k为大于等于1的整数，2的k次方小于待排序列长度，增量序列末尾的1是额外添加的。此时时间复杂度为O(n1.5)

空间复杂度

希尔排序的空间复杂度同直接插入排序一样，为O（1）

Thanks for your reward！