原文地址 分类目录——数据结构笔记 理论 每隔一个gap取一个值构成一个子序列,比如一个含9个值的序列,gap=4,这就获得了四个序列(i1, i5, i9), (i2, i6), (i3, i7), (i4, i8),这种分子序列是在逻辑上进行的,并不改变原序列的结构 在每个子序列内进行插入排序 排序完一轮后将gap减半,再次进行按gap分子序列插入排序 gap选取是一个值的研究的地方 实现 在描述原理时把整个序列分成若干子序列,每个子序列进行插入排序。 在实现的时候,为了实现方便,采用一种每个子序列批量插入排序的方式(有些串行的感觉),而不是一个子序列排序完成后再排序下一个子序列,大概是