【数据结构】排序：插入排序与希尔排序详解_数据结构输入一组数据使用直接插入算法进行排序,输出排序结果

本章开始就要分享一些常用的排序方法，我们的日常生活中很多地方都要使用排序，比如电商平台可以按照你的需求进行排序，或者是你想了解大学的综合排名时

 

 我们之前也学到过一些简单的排序比如冒泡排序，虽然他在时间复杂度上可以说是依托答辩，但是作为排序算法来讲还是非常有教学意义的，让更多的人可以了解到排序。

那首先分享两种排序算法，简单了解一下排序，以下是本章目录；

目录

1.直接插入排序

2.希尔排序

2.1对gap的解释

---

1.直接插入排序

玩儿斗地主时，我们需要将我们的牌排成有序的，例如对子、顺子，以便于我们出牌。

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

用上面这副图说就是我们手里已经有了2、4、5、10，当我们拿到7的时候我们需要对他的前后进行对比并且找到合适的位置进行插入。

为了便于理解以下先是单趟的插入排序

void InserSort(int* a, int n)
{
	//[0,end]有序，插入tmp后依然有序
	int tmp;
	int end;
	while (end >= 0)
	{
		if (a[end] > tmp)
		{
			a[end + 1] = a[end];
			--end;
		}
		else
		{
			break;
		}
	}
	a[end + 1] = tmp;
}

以上代码中tmp可以理解为我们插入的数据，大致意思就是当我们想要插入的数比最后一个数小的时候，就放在最后一个数的前面，并且将数组中的数字整体向后移动；但是当其他情况的时就可以直接插入。

下图是当我们插入1的时候要和数组内容进行比较，最后将1插入到了最前面，图示方便大家理解。

注意将a[end+1]=tmp;写在括号外是为了避免数组为空的问题；

以上是单趟排序的理解，我们加上for语句来规定他的循环次数即可完成多趟排序

void InserSort(int* a, int n)
{
	//[0,end]有序，插入tmp后依然有序
	for (int i = 1; i <= n; i++)
	{
		int tmp = a[i];
		int end = i - 1;
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
} 

所所以不难看出他最坏的情况下的时间复杂度为O(N^2) 

那不就和我们之前所学的冒泡排序的时间复杂度一样了吗？并不是这样。

冒泡排序的思想是相邻两个元素进行比较在进行交换，而且一趟排序只能确定一个数的位置，所以无论是否有序，他的时间复杂度都是O(n^2);

而插入排序在最好的情况下，也就是数组为升序的情况下时间复杂度为O(n),省去了两两交换的过程，当然前提是数组为升序

以上就是插入排序的内容

2.希尔排序
 

希尔排序其实是对插入排序的一种优化，大体思想就是在插入排序之前加上了与排序的步骤，所以他的思路就是1.预排序，使这个数组接近有序（注意是接近有序而不是有序）2.插入排序。

这个预排序的意思就是先将数组分组，固定一个gap，使数组间隔为gap分成一组，总共有gap组。

我们用一段数组来举例

我们假设gap为3

 如上图就分成了一组，接下来继续分组

 

 

 

可以看到gap为三时，红色线标注的9，6，3，1为一组数；蓝色线标注的8，5，3，0为一组数，最后用绿色线标注的7，4，2为一组数；

接下来就要对gap组的数据分别插入排序(升序)；

首先是对第一组的数据插入排序成升序，如下图；后面几组数据以此类推

红色组的数据

蓝色组的数据

 

 

绿色组的数据 

 

 到这里我们会发现这样预排序之后让数组接近有序，这样就达到了预排序的效果；

最后我们再对预排序后的数据进行插入排序，这样效率就会提高很多。

回头再看这组数据，如果想让他排成升序，但是这组数据确实降序，无疑在时间复杂度上一定是最坏的结果，所以时间复杂的度为O(n^2);

但是使用了希尔排序的预处理之后，让数组接近升序，这样就会在时间复杂度上回优化不少；

为了方便理解，我们先排列第一组数据（以下代码为错误代码示范）；

void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int i = 0; i < n; i += gap)
	{
		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;
	}
	
}

以上就是排完一个gap组的数据 

看完以上代码不知到是否想到了插入排序的思想

 是的，预处理只是将数组之间比较的间隔拉大了一些，插入排序是后一个数向前插入，和自己的前一个数进行比较；而希尔排序的预处理阶段也是后一个数向前插入，只不过是和自己的前gap个数进行比较；简单来说就是插入排序只走一步，而希尔排序走的是规定的gap步。

但是观察上面的代码我们会发现当i走到end的位置时，继续往下走就会越界

 所以我们还需要将for循环中的循环条件改为i<n-gap;

void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int i = 0; i < n-gap; i += gap)
	{
		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;
	}
	
}

这样才算是真正的将第一组的数据，也就是红色的线连接的9，6，3，1排成有序的1，3，6，9；

排完一组数据我们还需要将第二组蓝色线的数据和第三组绿色线数据都排成有序；

上面的思想我们也讲过只需控制下标end就可以达到排序不同组数据的效果，所以我们不妨再套一个for循环来解决问题；

void ShellSort(int* a, int n)
{
	int gap = 3;
	for (int j = 0; j < gap; j++)//循环插入每组
	{
		for (int i = j; i < n; i += gap)//每组数据排序（升序）
		{
			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;
		}
	}
	
	
}

这样以来我们就解决了要排列多组数据的问题；

ok说了那么多我们写个测试样例验证一下我们的结果

 可以看到我们的降序数组在希尔的预处理中已经变得近似有序

接下来要说是到现在位置已经有了三层循环，所以我们可以对其进行优化，以下是优化的代码

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

首先我们对比两种写法

 

 其实对比两种写法，第一种会更利于理解一些，因为第一种的思路是一组一排，就是第一组数据排完排第二组，第二组排完派第三组以此类推，按照图示来说就是先排红色在排蓝色在排绿色的数据。

 

而第二种写法的思路是多组并排，也就是控制通过控制  i 来控制end， 也就是分别将每一组的第一个数据排好再去排每组的第二个数据，再去排每组的第三个数据以此类推，照图示来说就是先排1，再排0，再排2，在排3，3，4，6，5…………

 其实两者的时间复杂度是一样的，效率上并没有提升，只是在理解上更巧一点。

2.1对gap的解释

在上面的代码中为了测试方便一些于是自己写了一个简单的测试用例，并规定了gap为3；

那gap一定为3吗？其实根据上面的希尔排序对比插入排序中，希尔排序跳的更快了，当后一个数比前一个数小的时候，他不是像插入排序一样向前一位交换数据，而是向前gap位交换数据；

他的目的是在预处理中，将小的数更快的放到数组的前面，大的数更快的放到数组的后面而使数组尽量有序。

当然gap也并非越大越好，因为gap越大，越不接近有序

当我们将gap改成5时，我们会发现没有gap=3时有序；

 我们再将gap换成1

 我们就会发现数组就会排成升序了，这就和之前的插入排序一样了

所以我们总结出

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

gap越小，大的数和小的数移动越慢，但是会更接近有序；

gap==1时，就会直接变成插入排序；

 所以我们规定在使用希尔排序时将他的gap设置为  gap/3+1 ,因为要保证gap在数据很少的情况下也是int类型。

以下是规定gap后的代码

void ShellSort(int* a, int n)
{
		int gap = n;
		while (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;
			}
		}
		
}

 接下来在对他进行一次插入排序就可以使数组有序了。

以上就是有关插入排序和希尔排序内容的分享，如果对你有所帮助还请三连支持，感谢您的阅读。