【排序算法】希尔排序

前言：学习希尔排序前最好先掌握插入排序，在进行；不会的可以点击——>【排序算法】插入排序-CSDN博客

一、希尔排序：

        希尔排序，也称为缩小增量排序，是一种基于插入排序的快速改进算法。由Donald Shell于1959年提出。 它的基本思想是将待排序的元素按照一定的增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序在一般用于处理大量数据！！

二、思路：

分成2个阶段：

1、预排序：这个阶段将待排序的数据分成gap组，对每组数据进行插入排序。

2、插入排序：gap==1时，也就是只有1组的情况，这个数组就变成有序数组了。

 具体详情：

1、将一个小于n（元素个数的）的整数作为gap增量，所有距离为gap的元素作为一组数据（也就是我们说的将数组分成gap组）然后对每一组数据进行插入排序，排好后，取一个比第一增量小的整数（比原gap小的组数）重新将新的gap距离的元素作为一组数据，接着上述操作；重复这些操作

2、当gap不断细分到了gap==1即将所有元素分为一组时，进行插入排序，数据变成有序！

下面的动图，我觉的比较直观的了？当然没看懂也没关系，下面会有讲解

 先分组，然后你会发现我们分了三组，我们以3个元素为一组分的，但是有的组元素个数未满三个，因为元素之间的距离和数组长度的差异，会有点不同，但是影响不大哈，值得注意的是距离差3，不是元素个数差3哈，个数是只差了2个元素，从图里也可以看出来

分为3个组：

第一组：8、7、5

第二组：9、2、4

第三组：1、3

 对第一组进行插入排序

 然后接下来是下标为0+gap+gap的位置来一次插入排序，该位置本来的元素是5，经过插入排序后，5到了这组数据的最前面；此时这一组的数据是不是变成有序了

当每组都进行完插入排序后，我们可以发现小的数几乎靠近左边，大的数几乎靠近右边。大致粗略有点顺序了 

 然后将gap==1，进行一次整体的插入排序；因为数据比较少 所以这里gap的分化次数也比较少

三、时间复杂度：(有点难证明，记住即可)

O（N^1.3）

四、实现：

先考虑一组的实现哈。发现了没？其实和插入排序实现很相似，这里如果gap==1就是插入排序了。我们用的gap为3，实现过程和插入排序的写法大差不差，就是end+1换成了end+gap

✨我们对于每一组元素都要进行插入排序，用到了for循环来保证每个组进行交换，外层的i控制的是你的每一轮的j开始时每个组的头位置，内层j是保证你遍历的都是自己组的成员，这个是以一组进行的排序，排完一组后再排另一组，直到gap组排完；不知道你发现了没有，先写底层逻辑再写真的会很清晰；我们会顺畅很多✨

但是🤔🤔🤔我不想要三层循环嵌套，可以修改一下，之前是一组一组的进行，就是说排好一组在进行另一组。现在我直接交错进行，先第一组的第一个元素，然后第二组的第一个元素，然后第三组的第一个元素，直到gap组的第一个元素都进行了一次插入排序，接下来再是第一组的第二个元素……以此类推；

为啥 🤔是 i；因为我们会抽处 end+gap 这张牌，所以当到了每个组倒数第二个元素就可以了也就是i只要到最后一组的倒数第二个元素空了，因为最后一个元素会和前一个元素比较的，不要越界访问

void ShellSort(int* a, int n)
{
	int gap = n;
	//gap的组数越大，数据可以更快的跳到后面，小的更快跳到前面，但是越不接近有序；反之，gap越接近有序
	while (gap > 1)
	{
		//巧妙的用的除法，/2 /3 /4都行，但是有人证明了/3更好，还要加1，因为gap小于3的话gap/3==0
		//最后一次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 (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
	
}