【排序】插入排序，希尔排序

前面我们讲述了冒泡排序和选择排序，我们本章讲的排序方法是插入排序，插入排序是希尔排序实现的基础函数，大家一定要好好理解插入排序的逻辑，这样才能在后面学习希尔排序的时候，更容易的去理解，我们直接开始。

插入排序（以升序为例）

基本思想：

思路

代码实现：

总结

希尔排序

基本思想：

一组一组依次排序代码实现

多组同时排序

希尔排序的时间复杂度分析

总结

插入排序（以升序为例）

基本思想：

直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

就和我们打牌时，从小到大排牌序，当拿到一张新牌时，我们从后往前找，当最后的牌大于此时的牌，那么就让最后一张牌向后挪动一位，继续和倒数第二张比较，若倒数第二张小于此时的牌，就说明找到了位置，将此时的牌插入即可。

如上图中，此时的牌为7，那么我们从后往前找，发现10>7,那么10就往后挪动，继续向前找，发现是5，而5<7,说明找到了合适的位置将7放入5的后面即完成了插入排序。

思路

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

由于插入排序插入第i个元素时，需要前i-1个元素都是有序的，因此我们仍然需要从第1个元素开始排序

假设我们目前前i个是有序的，我们排序的就是第i+1个元素，我们用tmp记录a[i+1]的值，然后从后往前开始依次比较，由下标i到下标0，我们再创建循环，用变量(j=i ， j >= 0 , j - -)控制循环

当 a[j] > tmp时，a[j]就向后挪动，即a[j+1] = a[ j ]

当a[j] < tmp 时，说明已经找到了合适的位置，直接跳出循环，并将j+1的位置赋值为tmp即可

以下便是逻辑图：

以上是找到比tmp小正常插入的情况，还有一种情况，当数组在tmp前内没有比tmp小的元素时，那么就会将小数放到数组首位，逻辑图如下，还是上面数组的例子。

动态逻辑图

代码实现：

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int tmp = a[i+1];
		int j = 0;
		for (j = i; j >= 0; j--)
		{
			if (a[j] > tmp)
			{
				a[j + 1] = a[j];
			}
			else
			{
				break;
			}
		}
		a[j+1] = tmp;
	}
}

小结

直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

希尔排序

希尔排序法又称缩小增量法。希尔排序已经算是是排序中的大哥了，所以也比较难以理解，他是与快速排序，堆排序，归并排序在同一条赛道上的排序算法，十分的厉害。

基本思想：

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

可能比较难理解，希尔排序分为两个部分，首先进行预排序，再进行插入排序

预排序：跨元素进行分组排序，让数组更接近有序，这样再进行插入排序的时候，基本都是在有序的情况下，那么再进行插入排序就减少了数组挪动的次数，效率更高了。

我们假设跳的距离为gap，gap初始值为3

看一下逻辑图，我们就明白进行预排序后的效果

下面我们来单独实现代码，我们可以将代码拆分成几个小部分，依次实现，这样会让代码实现变得更加容易实现，这便是由小及大的思想

我们先来实现对单个分组排序的实现，即对红色排序的实现

代码实现的底层逻辑，依然是插入排序，只不过在进行遍历和比较的时候是一次跳跃gap个元素

大家看一下代码实现应该就能理解

部分代码实现

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

在完成单趟逻辑后，然后我们再建一个for循环，让gap组依次进行排序，即完成了一组一组依次排序的逻辑实现

一组一组依次排序代码实现

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

还有一种实现方法，是令多组同时进行排序，只需要修改一下逻辑代码即可

多组同时排序

int gap = 3;
for (size_t i = 0 ; i < n - gap; i++)
{

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

二者的逻辑图如图所示

希尔排序的时间复杂度分析

希尔排序的时间复杂度比较难计算，因为gap的取值方法很多，导致很难去计算

我们通过上面的逻辑分析，发现在预排序阶段

gap越大，大的数可以更快的跳到后面，小的数可以更快的跳到前面，越不接近有序

gap越小，大的数跳到后面越慢，小的数跳到前面越慢，但越接近有序

因此控制gap的大小是增加效率的直接办法

但是如何取最适合的gap呢，根据大量数据统计，我们发现当gap = n/3时效率最高，但是我们需要+1，保证gap最后等于1

代码如下

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// +1保证最后一个gap一定是1
		// gap > 1时是预排序
		// gap == 1时是插入排序
		gap = gap / 3 + 1;

		for (size_t 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;
		}
	}
}

我们以n/3为例，以gap对时间复杂度的影响进行分析

如下

代码实现

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		// +1保证最后一个gap一定是1
		// gap > 1时是预排序
		// gap == 1时是插入排序
		gap = gap / 3 + 1;

		for (size_t 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;
		}
	}
}