插入排序过程是从待排序集合中每次选择一个元素,通过不断比较和交换位置,移动到已排序集合的适当位置上。...算法步骤:
根据增量
值大小,将序列拆分为
个分组
对每个分组执行插入排序算法,并对
值按指定规则调整大小
重复步骤 1, 2,直到
值为 0
示例
当初始序列为:[5, 3, 4,...step 1
序列为:[5, 3, 4, 0, 2, 1, 8, 6, 9, 7]
因为
为 10,
,所以
初始值为 3,
,
初始值为 7
因为
值为 7,所以序列被拆分为 7...9],可以发现一个很明显的事实,在这个分组里,4 和 1 位置相差一,即只需要比较和交换一次即可确定这个元素的,而且这个顺序很可能在后续的排序过程中不会变化,相对于直接对原始序列执行插入排序算法,两个元素位置相差...但是观察示例过程中 step 1 和 step 3 的序列,经过两轮排序后,step 3 的序列已经较 step 1 显得更为有序,所以从大方向看,每一轮的排序对下一轮的排序是有序辅助效果的。