十大排序——希尔排序
希尔排序是一种特殊的插入排序，是对直接插入排序的升级改进。所以在学习希尔排序之前，一定要先弄清楚直接插入排序算法。
基本思路：
设一个序列里有n个待排序的元素，将间隔相同距离的元素分为一组进行比较，这里的间隔称之为增量，增量（gap）通常为n/2（奇数偶数都可以），随着算法的进行增量慢慢缩小，直到相邻的元素比较完，结束排序。
详细步骤:
首先，列出一组待排序的元素组成一个数组（如图1-1所示），数组长度len为8，增量gap可为4,2,1（每结束一轮排序，增量减半），首先增量为4时，将间隔相同距离的元素分为一组进行比较
图1-1
相同颜色的元素即为一组进行比较（如图1-2所示）
图1-2
第一组：8和6进行比较，8 > 6两个元素交换位置（进行升序排序，小元素在前，大元素在后），如图1-3所示：
图1-3
第二组：1和2进行比较，1 < 2两个元素位置不变
第三组：5和3进行比较，5 > 3两个元素交换位置
第四组：4和7进行比较，4 < 7两个元素位置不变
第一轮比较结束，结果如图1-4所示：
图1-4
接下来增量为2重新对数组进行分组排序，共分为两组，如图1-5所示：
图1-5
第一组：6、3、8、5进行比较，小的元素在前，大的元素在后，结果为3、5、6、8。
第一组：1、4、2、7进行比较，小的元素在前，大的元素在后，结果为1、2、4、7。
第二轮比较结束，结果如图1-6所示：
图1-6
接下来继续缩小增量，当增量为1时，就是直接插入排序，如果不太清楚的同学可以看看之前插入排序算法的文章，最后一轮排序结束后就可以得到一个完整的升序数组（如图1-7所示）。
图1-7
代码实现：
#include <stdio.h>
void shellSort(int *a, int len)
{
int i, j, k, temp, gap; // gap 为增量
for (gap = len / 2; gap > 0; gap /= 2) // 增量初始化为数组长度的一半，每次遍历后增量减半
{
for (i = 0; i < gap; ++i) // 变量 i 为每次分组的第一个元素下标
{
for (j = i + gap; j < len; j += gap) //对增量为gap的元素进行直插排序，当gap为1时，就是直插排序
{
temp = a[j]; // 备份a[j]的值
k = j - gap; // j初始化为i的前一个元素（与i相差gap长度）
while (k >= 0 && a[k] > tmp)
{
a[k + gap] = a[k]; // 将在a[i]前且比temp的值大的元素向后移动一位
k -= gap;
}
a[k + gap] = temp;
}
}
}
}
int main( )
{
int i;
int a[8]={8,1,5,4,6,2,3,7};
int len = 8;
shellSort(a, len); // 调用希尔排序函数
printf("希尔升序排列后结果为：\n");
for (i = 0; i < len; i++)
{
printf("%d\t",a[i]); // 排序后的结果的输出
}
printf("\n");
return 0;
}
