插入排序（直接插入排序与希尔排序）----数据结构-排序①

1、插入排序

1.1 插入排序的基本思想

将待排序的元素按其数值的大小逐个插入到一个已经排好序的有序序列中，直到所有的元素插入完为止，就可以得到一个新的有序序列。

实际上在我们的日常生活中，插入排序的应用是很广泛的，例如我们在玩扑克牌时，就利用了插入排序的思想，例如下图：

当我们手里已经具有 2、3、5、10 这样一个有序序列的扑克牌时，我们现在又出现一张 7 ，我们需要将其插入到我们已经有序的 2、3、5、10 序列中，我们先将需要插入的 7 与最后一张 10 进行大小比较，如果发现所插入的元素比 10 更小，就继续与前一个元素比较，直到发现所插入的元素大于该元素，就将其插入到该元素的后面即可。

1.2 直接插入排序

有了上面对插入排序的理解，下面我们一起来学习一下直接插入排序。

排序思想：当我们插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的数值与先后与array[i-1],array[i-2],…的数值进行比较，找到合适位置就将array[i]插入，该位置后的所有元素都需要依次往后移。

下面是示意图：

代码实现：

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;  // 这里我们认为 [ 0 , end] 是已经有序的

		int tmp = a[end + 1];   // 将 end+1 位置的元素与前面 [ 0 , end] 的元素进行比较
								// 找到合适的位置就插入
		while (end >= 0)
		{
			if (tmp < a[end]) // 如果前面的数据比 tmp 大就将该数据往后挪
			{                 // 并且比较 --end ，使tmp继续与前一个数据进行比较
				a[end + 1] = a[end];
				--end;
			}

				   // tmp >= a[end]
			else   // 遇到前面的数据比 tmp 小或相等就跳出循环
				break;

		}
		// 此时 end+1的位置是空出来的，即 tmp 所插入的位置
		a[end + 1] = tmp;
	}
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

1.3 希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数 gap（一组当中相邻元素的距离） ，把待排序文件中所有数分成个 gap (N是数据总个数)组，所有距离为 gap 的数分在同一组内，并分别对每一组内的数据进行一次插入排序。然后让 gap 不断的缩小，并重复上述分组和排序的工作。当到达 gap = 1 时，相当于进行了一次直接插入排序，这一次排序结束后，所有数在同一组内被排好序。

下面是希尔排序动图演示：

gap的取法：

gap的取法有很多种，但主流的两种取法是：①gap = gap/2；②gap = gap/3 +1。

下面我们以gap = gap/3 + 1 这种取法为例。

代码实现：

void ShellSort(int* a, int n)
{
	assert(a);

	int gap = n;

	//不能写成大于0,因为gap的值始终>=1
	while (gap > 1)
	{
		//只有gap最后为1，才能保证最后有序
		//所以这里要加1
		gap = gap / 3 + 1;

		//这里只是把插入排序的1换成gap即可
		//但是这里不是排序完一个分组，再去
		//排序另一个分组，而是整体只过一遍
		//这样每次对于每组数据只排一部分
		//整个循环结束之后，所有组的数据排序完成
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0 && a[end] > tmp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}

			a[end + gap] = tmp;
		}
	}
}

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定，一般认为希尔排序的时间复杂度是 $O(^{_{N^{1.3}}})$ 。