本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.希尔排序
希尔排序（Shell Sort）属于插入排序的一种。它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序（Diminishing Increment Sort）。
通过一个简单的例子来理解希尔排序。假设有如下待排序数列：
我们设置增量gap=length/2。length为待排序数列的长度，本例中length=10。缩小增量采用gap=gap/2的方式。因此，我们可以得到增量序列为：{gap,gap/2,(gap/2)/2,…,1}。
除法都只取整数部分。
👉第一趟排序：gap=10/2=5。整个数列被分为5组：[8,3]、[9,5]、[1,4]、[7,6]、[2,0]。对这5组分别使用插入排序：
👉第二趟排序：gap=5/2=2。整个数列被分为2组：[3,1,0,9,7]、[5,6,8,4,2]。对这2组分别使用插入排序：
👉第三趟排序：gap=2/1=1。整个数列为1组。对其进行插入排序：
总的来说，希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
