1、核心思想
希尔排序：在直接插入排序的基础上进行的优化，直接插入排序在n值小的时候效率比较高，在n很大的时候如果待排序序列基本有序，效率依然很高，时间效率可以提升为O(n)。希尔排序也称之为缩小增量排序。希尔排序就是用了直接插入排序的优点进行改进。刚开始排序n值小，等n值大了后，序列又已经基本有序了。
2、例子
初始数组：[18, 24, 12, 15 , 1 , 27, 17 ,19]
第一趟
增量 = 数组长度/2 = 4。
按步长为4对数组划分，得到[18，1]、[24，27]、[12，17]、[15，19]
将各组按直接插入排序方法排序得到
[1，24，12，15，18，27，17，19]
第二趟
增量 = 增量/2 = 2
按步长为2对数组划分[1，12，18，17]、[24，15，27，19]
将各组按直接插入排序方法排序得到
[1，15，12，19，17，24，18，27]
第三趟
增量 = 增量/2 = 1
因为步长已经为1了，执行直接插入排序，现在序列已经基本有序，所以效率高了很多。
[1，12，15，17，18，19，24，27]
image.png
网友评论