当前位置:   article > 正文

【数据结构】-插入排序家族(直接插入排序、希尔排序)_数据结构插入排序

数据结构插入排序

作者:小树苗渴望变成参天大树
作者宣言:认真写好每一篇博客
作者gitee:gitee
在这里插入图片描述
如 果 你 喜 欢 作 者 的 文 章 ,就 给 作 者 点 点 关 注 吧!


前言

今天我们介绍关于插入排序,插入排序分为两种,一个是直接插入排序,一个是希尔排序,这两种排序是由相同之处的,那我们接下来介绍一下这两种排序。(以升序进行讲解)


一、直接插入排序

我们先来看看动图演示:
在这里插入图片描述
我们是一步一步往后面走,遇到大的就往后面移一位,知道碰到一个小的,就把数据往小的后面进行插入。我们先来看看单趟排序:

	int end = 9;
		int key = a[end];//先把要插入的数据保存起来,方便和其他数进行比较
		while (end >= 0)
		{
			if (key < a[end - 1])//可以小于前面的数,就把数往后面移一位
			{
				a[end] = a[end - 1];//
				  end--;
			}
			else//比前面a[end-1]的这位大就退出,把数据放到它后面,就是a[end]的位置
			{
				break;
			}
		}
		a[end] = key;//把要插入的数放到这个位置
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

单趟排序结果:
在这里插入图片描述

我们看画图:
在这里插入图片描述

在实际排序中,开始排最后一位数的时候,前面应该是有序的了,我们都市从前面往后面选出key进行插入,但是每一趟的思想是样的。

我们来看看完整的排序:

void insertsort(int* a, int n)
{
	for (int i = 1; i <= n-1; i++)//i从1开始就可以了,没必要从0开始
	{
		int end = i;
		int key = a[end];//先把要插入的数据保存起来,方便和其他数进行比较
		while (end > 0)//因为都是和前面的数进行,加等于就跳到前面的位置,越界了,
		{
			if (key < a[end - 1])//可以小于前面的数,就把数往后面移一位
			{
				a[end] = a[end - 1];//把前面大的数移到后一位
			   end--;
			}
			else//比前面a[end-1]的这位大就退出,把数据放到它后面,就是a[end]的位置
			{
				break;
			}
		}
		a[end] = key;//把要插入的数放到这个位置
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

大家掌握这个思想之后我们开始进行希尔排序的讲解

二、希尔排序

希尔排序是在直接插入排序的基础上先进行分组,然后预排序,增加分组,在排序,最后就排序成功,我们来看看图:
在这里插入图片描述
对分组的元素进行直接插入排序,我一开始先以三个为一组距离为二的gap给大家画图演示一下,更加的直观一些
在这里插入图片描述
这就是希尔的一趟排序,但实际代码是一个一个的往后面走的,我知识把距离为gap的分开画图让大家看到更加直观些,我们来看看这一趟排序的代码,再来看看整体的:

int gap = 2;
	for (int i = gap; i <=n - gap; i++)
	{
		int end = i;
		int key = a[end];
		while (end > 0)
		{
			if (key < a[end - gap])
			{
				a[end] = a[end - gap];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end] = key;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

我们针对直接插入排序仅仅就做了很小的变化,把gap变成1就是直接插入排序。

单趟排序的结果:
在这里插入图片描述

对于希尔排序,就是想把最大的数尽快跳到最后面,最小的数尽快跳到最前面,所以才有了分组的思想,但最后都是要回归到直接插入排序,也就是gap=1,那我们一开始的gap怎么选呢?一般都是选择数组元素个数的一半,因为越到后来数组月接近有序,大部分想要的数据都道理对应的范围,所以要缩小gap的范围,一次除以2,任何数除以2,最后都会是1,我们来看看最终的排序

我们只要保证最后一次gap=1就行了,所以我们还有一种写法
gap=gap/3+1;
这是我们给gap初始值的方法

void shellsort(int* a, int n)
{
	int gap=n;
	while (gap > 0)
	{
	   gap = gap/2;
	   gap=gap/3+1;
		for (int i = gap; i <= n - gap; i++)
		{
			int end = i;
			int key = a[end];
			while (end > 0)//因为都是和前面的数进行,加等于就跳到前面的位置,越界了,
			{
				if (key < a[end - gap])
				{
					a[end] = a[end - gap];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end] = key;
		}
		gap/=2;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

对于希尔排序,为什么效率比直接插入排序好,原因是gap>1的时候,都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。

希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定

我们来看看其他书中是怎么介绍希尔排序的时间复杂度:
《数据结构(C语言版)》— 严蔚敏

在这里插入图片描述
《数据结构-用面相对象方法与C++描述》— 殷人昆
在这里插入图片描述
这个我们能记住结论更好,不能记住了解一下也可以,我们先要掌握每一趟的排序,在对整体进行排序,这样即使忘记了,画画图也很快就能掌握了。

三、总结

今天我讲的两种排序都是插入排序家族的,两种有相似之处,也有不同之处,两者的性能差距,我会再更新所有排序的文章之后再进行测试,那今天的排序就先将到这里了,大家下来自己去画画图理解一下,我们下篇讲选择排序家族的
在这里插入图片描述

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号