希尔排序，shell排序，缩小增量排序
1959年D·L·Shell，提出的这个算法。
名称：shell排序，希尔排序，缩小增量排序。
插入排序的升级写法，原则就是将整个数组进行几次大体排序，让各个元素处在其应该在的大致位置上，最后进行一次细致排序，从而提升效率。
大体排序的思路就是先把数据分成几个小组，让各小组各自进行插入排序。过程如下：不一定3个一组，8个也行，我这里以3个一组举例子。
第一次：3个一组（最后一组有可能不满3个，这个没有影响），将每一组的第一个数组作为一组数据，对他们进行插入排序。如下图：
10个数，每三个一组，就是分成4组，最后一组1个数。
先将每组的第一个数拿出来，也就是3 6 2 7进行插入排序，得到2 3 6 7。
然后将每组的第二个数拿出来，也就是4 9 6进行插入排序，得到4 6 9。
然后将每组的第三个数拿出来，也就是8 5 1进行插入排序，得到1 5 8。
最后三次小组排序后得到新数列2 4 1 3 6 5 6 9 8 7。
第二次2个数一组。第一次-1。执行第一次同样的逻辑，也就是一样的代码。过程如下图：
在上一次运行的结果基础上，再次以2个一组进行排序。
第一次拿出每组第一个。即2 1 6 6 8，排序后为1 2 6 6 8.
第二次拿出每组第二个。即4 3 5 9 7，排序后为3 4 5 7 9.
进行完结果为：1 3 2 4 6 5 6 7 8 9
最后再1个1组，1个一组就是挨个插入排序了。
这最后一次，从头到尾进行插入排序，我们发现仅需要进行；两次移动就成序了。
经过对比：
最原始的插入排序排好这串数需要22次移动元素。
shell排序排好这串数仅需要14次移动元素。
根据数据的大小位置不同，换一组数据，排序移动的次数也不同，也就是算法不稳定，比如换10个数，可能需要18次排序，也可能5次就排好。
#include <stdio.h>
void sort(int* p, int len)
{
for (int i = 3; i >= 1; i--) //分组 3个1组，2个1组，1个1组
{
for (int j = 0; j < len - i; j += i) //遍历组，一组遍历1个
{
int k = j + i; //插入排序核心算法，这段都是
int temp = p[k];
while (k >= i && temp < p[k - i]) //找位置
{
p[k] = p[k - i];
k -= i;
}
p[k] = temp;
}
}
}
int main(void)
{
int a[10] = { 3,4,8,6,9,5,2,6,1,7 };
sort(a, 10);
return 0;
}