通过希尔增量将待排序数组划分为若干个分组,然后分组内进行插入排序,随后逐步缩小增量,继续分组进行插入排序操作,直至增量为1. 整个待排序数组划分为一组, 完成排序
希尔增量: gap=length/2 缩小增量继续以 gap=gap/2的方式 N/2 N/4 N/8 直至 间隙(gap)为1
原始数组: 3 8 2 7 9 1 4 5 0
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 3 | 8 | 2 | 7 | 9 | 1 | 4 | 5 | 0 |
初始增量: gap=length/2=9/2=4 划分为4个分组 下标每4个间隔取一个数,组成 [3,9,0][8,1][2,4][7,5]
对4个分组进行直接插入排序: [0,3,9][1,8], [2,4], [5,7] 依次循环取每个分组的首元素隔插入到表格中
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 0 | 1 | 2 | 5 | 3 | 8 | 4 | 7 | 9 |
第一趟排序后的数组: 0 1 2 5 3 8 4 7 9
第二轮: 希尔增量: gap=gap/2=4/2=2 划分为2个分组 下标index每隔2个间隙取一个数,加入数组
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 0 | 1 | 2 | 5 | 3 | 8 | 4 | 7 | 9 |
[0,2,3,4,9][1,5,8,7] 对这两个分组进行直接插入排序 [0,2,3,4,9][1,5,7,8] ,依次循环取每个分组首元素加入表格
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| value | 0 | 1 | 2 | 5 | 3 | 7 | 4 | 8 | 9 |
第二趟排序后的结果为: 0 1 2 5 3 7 4 8 9
此时 gap=gap/2=1 将第二趟排序结果划分为1个分组 进行直接插入排序
得到最终排序结果:
0 1 2 3 4 5 7 8 9