希尔排序

2016-03-16 20:54:27   2  举报





希尔排序是插入排序的一种优化版本，也称为缩小增量排序。该方法的基本思想是将待排序的数组按照一定的间隔分组，对每组进行插入排序，然后逐渐缩小间隔，再对整个数组进行插入排序。这样可以提高插入排序的效率，特别是对于近乎有序的数组，效果更加明显。希尔排序的时间复杂度为O(n^1.3)，比插入排序的时间复杂度要低很多。

作者其他创作

大纲/内容

增量increment=3时，数组下标为0、3、6、9组成一个子序列，下标为1、4、7组成一个子序列、下标2、5、8组成一个子序列