shell-sort 简易理解

一个更好理解的希尔排序实现:将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i += step_size而不是i++)。

例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10


然后我们对每列进行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45


将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45


排序之后变为:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94


最后以1步长进行排序(此时就是简单的插入排序了)。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 我发现我自己最近进步特别大,呵呵有点自恋了,但事实就是这样。 就像昨晚,婆婆半夜把果果抱来找我,我当时很生气。 这...
    疯疯之内阅读 3,122评论 0 2
  • 有些很难抉择的决定可能只在一瞬间便有了答案。也会在一瞬间便看清楚不是所有的事情都可以按照你所想所计划的进行,顺其自...
    糖小猫阅读 1,183评论 0 1