【数据结构 | 希尔排序法】

思路

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

所以，由上述我们可知：希尔排序，是多组的直接插入排序，如果不了解直接插入排序，可参考这篇文章：直接插入排序

所以，先选定一个gap值，让其分组，再排序。
但是，最后gap的值总归会等于1，完成最后的排序，只不过此时的数组基本趋近于有序，此时的直接插入的时间复杂度就比较低。

但是要实现希尔排序，gap应该怎么设定呢？

首先要确保，最后一组的gap必须是1，所以我们这样规定：gap = gap / 3 + 1

这样就可以保证最后一个的gap总是1

ShellSort

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	//预排序
	while (gap > 1)
	{
		//单趟排序
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
	//直接插入排序
	//InsertSort(a, n);
}