【数据结构】希尔排序

大家好，我是苏貝，本篇博客带大家了解希尔排序，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

一. 基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取gap=gap/2或者gap=gap/3+1（原因下面会说），重复上述分组和排序的工作。当到达gap=1时，所有记录已经排好序。

二. 实现希尔排序（以数组升序举例）

希尔排序可以分为2步：预排序和排序
预排序的目的是让数组接近有序
排序的目的是让数组有序

2.1 预排序

为了方便理解，我们先将gap置为3，即将数组分为3组。再将每一组都分别进行直接插入排序，最后数组就会接近有序
点击了解直接插入排序

下面代码中，第二个for循环就是每一组的直接插入排序，加入第一个for循环就是gap组的直接插入排序。因为相同组相邻的下标相差gap，所以将直接插入排序中的1全部替换成为gap。

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

上面代码也可以简写为下面这种形式，它的意思是多组并排，上面代码则是对每个组分别排序

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

2.2 排序

排序的目的是让数组从接近有序到有序。先让gap=n（数组大小）。当gap== 1时，就是对整个数组进行直接插入排序，直接插入排序后数组就有序。那如何让gap最后==1呢？我们可以将gap不断等于gap/2，这样不管n是奇数还是偶数，最后一定会等于1；也有人觉得不断将gap=gap/3+1更好，这样不管n是何值，最后也一定会等于1。

void ShellSort(int* a, int n)
{
	//1.预排序
	//2.排序
	int gap = n;
	//gap>1是预排序，gap==1是直接插入排序
	while (gap > 1)
	{
		gap = gap / 3 + 1;

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

希尔排序的特性总结：
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定
4.稳定性：不稳定

三. 对比直接插入排序和冒泡排序

在这里我们用一个函数来测试三个排序的性能。让三种排序都排列同样的100000个随机数字，比较3个排序的时间。rand函数用来生成随机值，clock函数用来返回程序运行的时间。因为排序用的时间可能比较长，所以在这里我们将Debug换成Release

void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	BubbleSort(a3, N);
	int end3 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("BubbleSort:%d\n", end3 - begin3);

	free(a1);
	free(a2);
	free(a3);
}

结果如下，我们发现希尔排序比直接插入排序要快速的多

好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞👍吗，感谢看到这里，我们下篇博客见❤️