数据结构——希尔排序（详解）

呀哈喽，我是结衣
不知不觉，我们的数据结构之路已经来到了，排序这个新的领域，虽然你会说我们还学过冒泡排序。但是冒泡排序的性能不高，今天我们要学习的希尔排序可就比冒泡快的多了。

希尔排序的前身是插入排序，可以说希尔排序就是插入排序的优化。并且优化了很多。所以在讲希尔排序前我们要先学会插入排序，不然在后续学习希尔排序会比较的吃力。那么让我们先进入插入排序的教学吧。

直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际上我们玩扑克的时候就运用了插入排序的思想
在这里插入图片描述
本来想放张插入排序动图的，可是放进来后它就不动了。。。
下面我们来讲解插入排序的特点：

了解完了，我们就要开始代码讲解了：

void InsertSort(int* a, int n)
{
	for(int i = 0;i&lt;n-1;i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end&gt;=0)
		{
			if (a[end] &gt; tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = tmp;
		}
	}
}

思路：
在待排序的元素中，假设前end个元素已有序，现将第end+1个元素插入到前面已经排好的序列中，使得前end个元素有序。按照此法对所有元素进行插入，直到整个序列有序。但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止
在这里插入图片描述
红色竖杆表示已经排好序列，绿色圈住的数字表示要插入到前面序列的数字。

讲完插入排序，接下来就到了我们的重点了——希尔排序

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

void ShellSort(int* a, int n)
{
	int gap = n;
	// gap > 1时是预排序，目的让他接近有序
	// gap == 1是直接插入排序，目的是让他有序
	while (gap>1)
	{
		gap = gap / 3 + 1;//也可以写成gap/2.目的都是为了最后一次gap一定要为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;
			}
		}
	}
	
}