希尔排序

希尔排序

希尔排序是基于插入排序的一个演进

插入排序很大一部分开销在于插入这个操作上，后面所有的数据都需要移动。

分割

我们先按N为步进来分割数组，如下为N=4

1       5       9 ……
  2       6       10 ……
    3       7       11 ……
      4       8       12 ……

对每个子数组进行排序

合并

实际上就是不分割数组，进行插入排序。

优点

分割之后，每个数组较小，能减少移动次数。

合并时，整个数组都是部分有序的，也能减少移动次数。