数据结构初阶--希尔排序

希尔排序又称缩小增量法。基本思想是先选定一个整数，把待排序的数据分成几个组，对每一组的记录进行排序。重复分组和排序的工作，直到所有数据在一组内排好序。

• 希尔排序是对直接插入排序的优化
• 当gap > 1时是预排序，使数组更接近有序。当GAP == 1时，数组已经接近有序，此时相当于直接插入排序。
• 希尔的时间复杂度难以计算。当增量序列为时，希尔排序的时间复杂度为，其中t为排序趟数，.
• 当n在特定范围内时，希尔排序所用的次数约为，当时，可以减少到

void ShellSort(int* a, int n)
{
	//gap > 1时预排序，使数组接近有序
	//gap为1时，直接插入排序
	int gap = n;


	while (gap > 1)
	{
		gap = gap / 3 + 1;


		for (int i = gap; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[gap + end];


			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}