希尔排序法

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

 上面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=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);
}