前言

本文章是建立在插入排序的基础上写的喔，如果有对插入排序还有不懂的童鞋，可以看看这里。
❤❤❤ 直接/折半插入排序 2路插入排序 ❤❤❤

希尔排序解释

希尔排序 Shell Sort 又名"缩小增量排序"，是对直接插入排序更加高效的改进版本。它是由 Donald Shell 于1959年提出的一种排序算法。

希尔排序 其原理是设置一个增量incre，在原序列上每隔一个增量选取一个数据元素，将这些选取的元素构造成一个子序列。

每设一个增量，我们每次会得到一组子序列 (子序列个数和当前增量相等)，然后分别对这些子序列进行 直接插入排序 。

随着增量的减少，重复上述的操作，直到增量incre为 1 时，最后完成整个序列的排序。

希尔排序增量的选取

原始希尔增量

对于 希尔排序 的增量的选取，Donald Shell 一开始提出增量每次为上次的 1/2。

也就是说，若数组长度为n，一开始增量为 n/2，之后每次增量都取上次的 1/2。

Knuth序列

Knuth序列：以逆向形式从1开始，通过递归表达式 interval = 3 * interval + 1 来产生，以此来得到间隔大小。

由此我们可以得到如下的增量选取方式:

具体方法是若数组长度为n，一开始增量取 n/3 向下取整 + 1。然后每次都取上次的增量的 1/3向下取整 + 1。

当n足够大时，使用 Knuth序列 得到的增量选取方式，可以一定程度上提高希尔排序的效率。

(上面说的东西其实我也不知道对不对，至于为什么这样取，我也不知道哇哇哇