vlambda博客
学习文章列表

背景

      希尔排序(Shell's Sort)本质是插入排序，是一种改进版本的高效插入排序，又称“缩小增量排序”（Diminishing Increment Sort）。

思想

       希尔排序的基本思想就是：将需要排序的序列先划分为若干个较小的序列，然后对这些小的序列进行直接插入排序，通过这样的操作可使需要排序的数列基本有序，最后再使用一次直接插入排序。这种将大量数据分割成小块，然后再利用简单排序方法分而治之的思想，其实可以应用到各种类型的排序算法上。因此，在希尔排序中首先要解决的就是如何划分序列，对于子序列的构成不是简单地分段，而是采取将相隔某个增量的数据组成一个序列。关于增量的选择有人专门做过研究，不过通常选择增量的规则是：第一次取序列全长的一半，然后每轮都取上一个增量的一半，如下图：

Scratch代码