希尔排序法

希尔排序为插入排序的优化，即将数组分组，将每一组进行插入排序，每一组排成有序后，最后整体就变有序了。

 上面gap=2，即5，14，18，27，68为一组；13，20，36，39，51为一组。

gap=2，从a[2]开始，a[2]和a[0]进行插入排序，a[3]和a[1]插入排序，a[4]和a[2]、a[0]插入排序......

为什么 要采取上面分组的方法呢（gap），换一种方法也可以吗？

例如：

相邻元素分为一组

相邻分组排序之后

按gap分组

gap分组排序之后

 可以发现左边都是较小的数据，右边都是较大的数据，更方便把分成的每一个组进行插入排序。

思想：当数据很大的时候，数据的gap设的很大，小的数据会往前放，大的数据会往后放，然后gap逐渐缩小，间隔也会逐渐缩小，整体数据会更加趋于有序，最后用gap=1，此时退化成直接插入排序，这个时候使用直接插入排序效率也会更高。

void Shell(int* arr, int size, int gap)
{for (int i = gap; i < size; i++) {int tmp = arr[i];int j = i - gap;for (; j >= 0; j -= gap) {if (tmp < arr[j]) {arr[j + gap] = arr[j];}else {break;}}arr[j + gap] = tmp;}
}
void ShellSort(int* arr, int size)
{int gap = size;while (gap > 1) {// gap组数变换比较随意，gap /= 3也可以gap /= 2;Shell(arr, size, gap);}// 最后让gap=1再排序一次，即直接插入排序Shell(arr, size, 1);
}