插入排序—直接插入排序和希尔排序

目录

 一、直接插入排序

        直接插入排序特性总结 

 二、希尔排序

        希尔排序排序特性总结 

---

：直接插入排序与希尔排序都是我们最常用的排序算法，它们都归属于插入排序这一类别。本篇博文将详细介绍并分析这两类排序。

 一、直接插入排序

基本思想：

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

动态演示：

实现思路： 

任何的排序都是需要我们先了解其单趟排序原理然后再实现其整体排序。

单趟排序：

：现在我们有一串有序的数字{1，3，4，10，12}，现在我们要插入一个数字7使其仍然有序，该如何实现呢？

实现过程非常简单，我们只需要拿7和数组里面的元素从后向前比较。如果7小于所比较的数字，那么我们就把所比较数字往后挪，此时出现一个空位，继续比较继续挪，直到插入的数字7放到空位数组刚好有序为止。

整体排序：

整体排序是建立在单趟排序之上，假设我们给定无序数组arr[8]={3，5，2，7，4，9，1，8}，我们用直接插入排序对arr升序，我们只需要将第一个数字看成有序并用变量tmp保存起来，把第二个数字看成是插入进去的数字按照单趟排序的思路进行排序，按照这个思路，我们依次对数组的第3、4、5.....个元素进行排序。

代码展示：

//直接插入排序
void InsertSort(int* a, int n)
{
	//i的取值范围为[0,n-2]
	for (int i = 0; i < n - 1; i++)
	{
		//单趟排序
		int end = i;
		int tmp = a[end + 1]; 
		while (end >= 0)
		{
			if (tmp < a[end]) //插入数字小于所比较数字
			{
				a[end + 1] = a[end];//将所比较数字往后挪
				end--;
			}
			else
			{
				break;
			}
		}
       a[end + 1] = tmp;
	}
}

直接插入排序特性总结 

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

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

：空间复杂度：O(1)

：稳定性：稳定

 二、希尔排序

基本思想：

希尔排序实质上是直接插入排序的进一步优化。希尔排序法又称为缩小增量法。希尔排序算法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离一样的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达距离=1时，所有记录在统一组内排好序。

实现思路： 

希尔排序可以细分为以下两个操作部分—预排序和直接插入排序

假设我们给定数组：arr[10]={9，1，2，5，7，4，8，6，3，5}

预排序：

希尔排序的预排序就是想让大的数尽快到后面，小的数尽快到前面，以达到接近有序目的。

预排序就是将数组中的元素进行分组排，比如我们给定间隔gap=3，那么数组arr中的数据就会被分为三组，其分别是{ 9，5，8，5}、{1，7，6}、{2，4，3}。gap为几数据就被分为几组。分完组后如下图所示：

 直接插入排序排序：

接下来我们分别对gap组数据进行插入排序。

动态演示：

 代码展示：

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = 3;
	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;
		}
	}
}

我们可以看到上述预排套了三层循环，看起来相对比较繁琐，接下来我们给它优化一下。

优化预排序—多组并列预排序：

我们上面实现的是分组排序，每一组排完后才进入下一组。现在我们要实现的是并列预排序，我们去掉第一层循环并将j+=gap改为j++就能实现多组并列预排序。

动态演示：

代码展示:

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = 3;
	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;
	}
}

优化预排序—gap最优解：

对于数组arr我们用gap=3可以，如果我们对数据量比较大或者比较小的数组进行排序，用gap=3合适吗？我们知道当gap=1时它就是直接插入排序，gap越小越接近有序，那么对于一个不知数据量多少的数组，如何规定gap更合适？看下列程序：

//1.gap>1 预排序
	//2.gap==1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1; //+1为了保证最后一次gap必定为1
		//预排序.......
	}

上述代码实现了根据数组的数据量取gap值最优解。当gap>1就进行预排序，gap==1进行直接插入排序。

代码展示:

//希尔排序
void ShellSort(int* a, int n)
{
	//1.gap>1 预排序
	//2.gap==1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1; //+1为了保证最后一次gap必定为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;
		}
	}
}

排序结果：

希尔排序排序特性总结 

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

：当gap>1都是预排序，其目的就是为了使数组更加接近有序。当gap==1数组已接近有序，再用直接插入排序会很快，这样整体而言就达到了优化效果。

时间复杂度分析：

：空间复杂度：O(1)

：稳定性：不稳定