【数据结构与算法】:直接插入排序和希尔排序

1. 排序的概念及其意义

1.1 排序的概念

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

1.2 排序的稳定性

  • 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
  • 在排序算法中,稳定性是一个十分重要的评判标准。它在我们生活中的某些方面有着作用,比如一个有时间限制的竞赛项目,当两人分数相同时,先提交的选手的排名要比后提交的选手的排名高。这就必须使用具有稳定的排序了。

1.3 常见的排序算法

常见的排序有冒泡排序,插入排序,希尔排序,选择排序,堆排序,快速排序,归并排序,计数排序等,其中我们最常用的是快速排序
在这里插入图片描述

插入排序

基本思想:

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

实际中我们玩扑克牌时,就用了插入排序的思想
在这里插入图片描述

2. 直接插入排序

基本思路:

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

如下图所示:
假设我们要排升序5 2 4 6 1 3
在这里插入图片描述

  1. 把首元素5看成是有序的,我们用tmp保存下一个元素,即tmp = 2,再让tmp与前面已经有序的数据进行比较,此时tmp < 5,所以把5后挪,把tmp插入到5的前面,保持有序;
  2. 接着再让tmp保存第三个元素,即tmp = 4,再让tmp与前面已经有序的数据进行比较,此时tmp < 5但是tmp > 2,所以把5后挪,把tmp插入到5的前面,2的位置不动,保持有序;
  3. ……重复上述上述步骤,以此类推……
  • 先考虑单趟排序的实现,代码如下:
int end ;
int tmp = arr[end + 1];//保存下一个值

while (end >= 0)
{
	if (tmp < arr[end])
	{
		arr[end + 1] = arr[end];//把前面的数按顺序往后挪
		end--;
	}
	else
	{
		break; //比前一个数要大时,说明找到了位置
	}
}

arr[end+1] = tmp;//包含了两种情况:1是在比较的过程中比前一个数要大,就把tmp放进去
                     //2是把前面的数都比完了,此时end==-1了,就把tmp放到最前面

这里的跳出循环包括两种情况:

  1. 在tmp与前面的有序数据比较的过程中,tmp的值比最后一个有序数据大,进入了else语句,break直接跳出循环。例如上图中的第3次排序过程。
  2. tmp比前面的有序数据都要小,一直end–,直到end < 0时,不满足循环条件,跳出循环。例如上图中的第4次排序过程。

而把arr[end+1] = tmp放在循环外面也是由于这两种情况,无论是第1种情况还是第2种情况,在循环结束后都要把待排序的元素放到指定是位置上。所以抽离这条语句放在循环外。

  • 再考虑排序的整体过程,代码实现如下:

i是控制已经有序的数据的最后一个数据,是一个边界。

void InsertSort(int* arr, int sz)
{
	for (int i = 0; i < sz - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];//保存下一个值

		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];//把前面的数按顺序往后挪
				end--;
			}
			else
			{
				break; //比前一个数要大时,说明找到了位置
			}
		}
		arr[end+1] = tmp;
	}
}

void PrintArray(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[] = { 6,7,9,2,4,3,5,1,0,8,-1};
	int sz = sizeof(arr) / sizeof(int);

     InsertSort(arr, sz);
     PrintArray(arr, sz);
     
     return 0;
}

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

2.2 时间复杂度的分析

  1. 最好:当待排序的元素为顺序时,时间复杂度0(N)。
  2. 最坏:当待排序的元素为逆序时,时间复杂度0(N*N)。

所以,直接插入排序的时间复杂度是0(N*N)。

2.3 排序的稳定性分析

  • 在上述代码排序过程中,当遇到两个相同数据时,会进入else语句,直接跳出循环,不会发生位置的挪动,即两个相同数据的相对位置依旧保持不变,所以直接插入排序是稳定的。

3. 希尔排序(缩小增量排序)

希尔排序是一种基于插入排序的改进算法。通过引入间隔的概念来改进插入排序的性能。

3.1 基本思想:

通过设置间隔,而对于每个间隔上的元素再进行插入排序,一趟排序后,间隔变小,再继续对此次间隔上的元素进行插入排序,直到间隔为1,此时就是一次完整的直接插入排序

在这里插入图片描述

  • 下面的排序代码与图解都是降序。

希尔排序分为两个步骤:

  1. 预排序
    预排序是让数组接近有序,需要通过分组来排,间隔为gap的是一组。 间隔为3时的一组预排序图解:
    ![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-blog.csdnimg.cn/direct/f6fe8bbfab294df69ae114525b900e07.png
    所以要进行多组间隔为gap的预排序,gap由大变小。

  2. 直接插入排序
    当gap = 1时,就是一次直接插入排序。

3.2 对预排序的代码实现:

  • 首先考虑间隔gap = 3时的单趟排序
int gap = 3;
int end ;
int tmp = arr[end + gap];

while (end >= 0)
{
	if (tmp < arr[end + gap])
	{
		arr[end + gap] = arr[end];
		end -= gap;
	}
	else
	{
		break;
	}
}
arr[end + gap] = tmp;

这里跳出循环的情况与上文的直接插入排序的两种情况一模一样。

图解如下:
![![外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2Fimgblog.csdnimg.cn%2Fdirect%2F7ff366ecbedf469bb5eeb644b0598c93.png&pos_id=img-ahdsKvHT-1712387936626](https://img-blog.csdnimg.cn/direct/3afc22d489bf4076830300497b5d8ffa.png

  • 然后把间隔为gap = 3的多组数据同时排:

int gap = 3;
for (int i = 0; i < sz - gap; i++)
{
	int end = i;
	int tmp = arr[end + gap];

	while (end >= 0)
	{
		if (tmp > arr[end])
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	arr[end + gap] = tmp;
}

部分图解如下:
每趟都是间隔为3的元素之间的一次直接插入排序。其中 i 控制end的走法,endgap控制每次排序的走法。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  • 接下来考虑如何取gap的值,就是如何让gap的值由大变小:
    gap越大,小的数可以越快到后面,大的数可以越快到前面,同时,gap越大,相对于gap越小而言预排完后越不接近有序。
void ShellSort(int* arr, int sz)
{
	int gap = sz;
	while (gap > 1)
	{
		gap = gap / 2;         // O(log2N)
		//gap = gap / 3 + 1;   // O(log3N)

		//对多组间隔为gap的数据同时排序
		for (int i = 0; i < sz - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];

			while (end >= 0)
			{
				if (tmp > arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
	
}

gap的取值有两种形式,首先它与数组元素个数挂钩,让gap = sz

  1. gap = gap / 2 ;当满足gap > 1时,任何数除2最后结果都是1,对应了gap = 1时就是直接插入排序。
  2. gap = gap / 3 + 1;当满足gap > 1时,为了使最后 gap= 1,所以要+1。

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

3.3 时间复杂度分析:
希尔排序的时间复杂度与数组元素的个数和和gap的取值有关。假设元素个数为N个。
当gap很大时,下面两层循环预排序接近O(N)
当gap很小时,数组已经很接近有序了,差不多也是O(N)

gap = gap / 2时,第一个循环大致执行log2N次(以2为底N的对数)
gap = gap / 3 + 1时,第一个循环大致执行log3N次(以3为底N的对数)

所以希尔排序的时间复杂度是O(N * log2N)或是O(N * log3N)。

3.4 稳定性分析:

不稳定,考虑序列(2,2,1),排序后序列为(1,2,2),我们发现2的相对位置发生了变化(粗体2与非粗体2),所以是不稳定的排序算法。

4. 两种排序的性能对比

clock() 函数是 <time.h> 头文件中的一个函数,用来返回程序启动到函数调用时之间的CPU时钟周期数。这个值通常用来帮助衡量程序或程序的某个部分的性能

我们可以用这个函数进一步对比两种排序占用的CPU时间

代码实现为:

void TestOP()
{
	    srand(time(0));
		const int N = 100000;
		int* a1 = (int*)malloc(sizeof(int) * N);
		int* a2 = (int*)malloc(sizeof(int) * N);
		
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	
	free(a1);
	free(a2);
}

这里让随机生成十万个随机数,分别用希尔排序和直接插入排序来进行排序,测试两种算法的执行时间:
在这里插入图片描述

通过上面的执行时间的对比,可以发现希尔排序的效率远远快于插入排序。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520411.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

08 Python进阶:XML 解析

什么是 XML&#xff1f; XML&#xff08;可扩展标记语言&#xff0c;Extensible Markup Language&#xff09;是一种用于表示和传输数据的标记语言。它被设计用来以一种结构化的形式描述文档的内容&#xff0c;并且具有良好的跨平台和跨语言的特性。XML使用标签来定义数据的结构…

关于 elf loader 的编写

可以使用如下命令观看 elf 文件的信息 readelf -a build/ramdisk.img | vim -在编写 elf loader 的时候&#xff0c;实际上只有下图这一部分 “Program Headers” 是有用的 凡是类型为 “LOAD” 的就是需要加载进内存的部分 所以&#xff0c;只要把这些部分加载进内存里&…

晶核2024搬砖职业推荐!

在晶核手游的广袤世界中&#xff0c;选择一位适合自己的搬砖角色是每位玩家都必须认真考虑的事情。不同的职业拥有独特的技能和特点&#xff0c;能够在搬砖过程中发挥不同的优势。下面&#xff0c;我们将深入探讨晶核搬砖的四大利器&#xff0c;让你对每个角色有更深入的了解&a…

Mac苹果电脑air/pro包含m1~m3打开app显示弹框“xxx”已损坏,无法打开。您应该将它移到废纸篓

应该是保姆级教程了&#xff1a; Mac苹果电脑air/pro包含m1~m3打开app显示弹框“xxx”已损坏&#xff0c;无法打开。您应该将它移到废纸篓。 我下载的是 Sublime Text 3 for Mac中文直装版&#xff0c;https://www.32r.com/soft/38404.html 安装后打开就gg了&#xff1a; 表现…

计算机中数的表示

0. 简介 介绍计算机中数的表示方法&#xff0c;主要内容来自 c s a p p csapp csapp。 1. 整数的表示 包括有符号整数与无符号整数的表示。 假设 w → [ w n − 1 w n − 2 . . . w 0 ] \overrightarrow w[w_{n-1}w_{n-2}...w_0] w [wn−1​wn−2​...w0​] 为一种整数。…

Allavsoft for Mac v3.27.0.8852注册激活版 优秀的视频下载工具

Allavsoft for Mac是一款功能强大的多媒体下载和转换工具&#xff0c;支持从各种在线视频网站和流媒体服务下载视频、音频和图片。它具备批量下载和转换功能&#xff0c;可将文件转换为多种格式&#xff0c;以适应不同设备的播放需求。此外&#xff0c;Allavsoft还提供视频编辑…

windows下部署mongoDB

目录 1. 下载zip安装包并解压&#xff1a;Download MongoDB Community Server | MongoDB 2. 在解压后的文件夹中新建文件夹data及下级文件夹db和log 3. 新建一个mongod.cfg文件&#xff0c;并配置以下内容 4. 在cmd中启动mongodb&#xff0c;并进行验证 5. 部署到本地服务器…

亚信安慧AntDB:打造智慧生态的数据心脏

AntDB的“融合实时”的特性&#xff0c;不仅使得数据库具备了更强大的适应性&#xff0c;更让企业在不同业务场景下能够更好地实现业务目标&#xff0c;释放出更大的商业价值。融合实时的特性让AntDB具有了高度灵活性和实时性&#xff0c;使其能够满足企业在不同业务需求下的快…

2024 批量下载公众号文章内容/阅读数/在看数/点赞数/留言数/粉丝数导出pdf文章备份(带留言):公众号混知近2000篇历史文章在线查看,找文章方便了

关于公众号文章批量下载&#xff0c;我之前写过很多文章&#xff1a; 视频更新版&#xff1a;批量下载公众号文章内容/话题/图片/封面/音频/视频&#xff0c;导出html&#xff0c;pdf&#xff0c;excel包含阅读数/点赞数/留言数 2021陶博士2006/caoz的梦呓/刘备我祖/六神读金…

uni-app如何实现高性能

这篇文章主要讲解uni-app如何实现高性能的问题&#xff1f; 什么是uni-app&#xff1f; 简单说一下什么是uni-app&#xff0c;uni-app是继承自vue.js&#xff0c;对vue做了轻度定制&#xff0c;并且实现了完整的组件化开发&#xff0c;并且支持多端发布的一种架构&#xff0c…

【Java EE】初识Spring Web MVC

文章目录 &#x1f334;什么是Spring Web MVC&#xff1f;&#x1f338;什么是Servlet呢? &#x1f332;MVC 定义&#x1f338;再理解Spring MVC &#x1f333;如何学习Spring MVC呢&#xff1f;⭕总结 &#x1f334;什么是Spring Web MVC&#xff1f; Spring Web MVC 是基于…

【Linux】使用cloudreve搭建个人网盘并传输文件

Cloudreve 是一个开源的个人网盘系统&#xff0c;能够帮助用户搭建属于自己的私有云存储服务。它支持多种存储后端&#xff0c;包括本地存储、远程FTP/SFTP存储、以及云存储服务如阿里云OSS、腾讯云COS和Amazon S3等。Cloudreve具有友好的用户界面和丰富的功能&#xff0c;比如…

揭秘rmallox病毒:防范、清除、恢复一步到位!

引言&#xff1a; 随着信息技术的快速发展&#xff0c;计算机病毒已成为网络安全领域的一大难题。其中&#xff0c;rmallox病毒是近年来备受关注的一种恶意软件。本文将深入探讨rmallox病毒的特性、传播途径、防范措施、清除方法以及数据恢复技巧&#xff0c;帮助读者全面了解这…

创新指南|涵盖创新管理的一系列终极指南

毫无疑问&#xff0c;创新是过去几十年来最热门的流行语和最具争议的话题之一&#xff0c;尽管很多人已经厌倦了到处听到它&#xff0c;但这个术语和概念它的后面就留在这里。由于这已被证明是无休止的争论来源&#xff0c;因此我们决定创建一系列涵盖创新管理的博客文章&#…

Ideal的使用技巧

一、springcloud项目如何将多个服务放到services中一起启动 1、打开ideal&#xff0c;再view -> Tool Windows -> services 2、在services界面 找到 run configuration type -> springboot即可 二、配置临时的启动参数 1、在edit configurations中 2、选择相应的服务…

红黑树平衡艺术:最大化与最小化红色结点比值的策略与实现

红黑树平衡艺术&#xff1a;最大化与最小化红色结点比值的策略与实现 一、 最大比值的红黑树构造1.1 伪代码示例&#xff1a;1.2 C代码示例&#xff1a; 三、最小比值的红黑树构造3.1 伪代码示例&#xff1a;3.2 C代码示例&#xff1a; 四、结论 红黑树是一种自平衡的二叉搜索树…

动态多目标优化:动态约束多目标优化测试集DCP1-DCP9的TruePF(提供MATLAB代码)

一、进化动态约束多目标优化测试集DCP1-DCP9 参考文献&#xff1a; [1]G. Chen, Y. Guo, Y. Wang, J. Liang, D. Gong and S. Yang, “Evolutionary Dynamic Constrained Multiobjective Optimization: Test Suite and Algorithm,” in IEEE Transactions on Evolutionary Com…

从零开始搭建后端信息管理系统(新手小白比如)

如果你是新手小白&#xff0c;首先我们要进行一些准备工作&#xff0c;安装一些基础软件&#xff0c; 备注一下&#xff1a;这里安装的vue环境的后台管理系统&#xff0c;不同的后台管理系统&#xff0c;需要安装不同的插件 准备工作&#xff1a; 安装 Visual Studio Code …

【Linux】UDP编程{诸多编程接口/三版本服务器/编程常见问题}

文章目录 0.预备知识0.1套接字0.2TCP/UDP0.3大小端问题 1.socket 常见API1.1socket1.2各个接口1.3int bind();1.3网络头文件四件套1.4bzero1.5recvfrom1.6sendto() 2.UDP编程2.1服务器编程2.2客户端编程2.3运行测试2.3.1本机通信2.3.2popen2.3.3strcasestr2.3.4回顾C11智能指针…

Ubuntu20.04配置Kinect 2.0驱动安装和ROS环境下配置以及录制bag包和制作ORB-SLAM数据集

1. 安装libfreenect2 1.1 下载官方文件 git clone https://github.com/OpenKinect/libfreenect2.git cd libfreenect21.2 安装build工具 sudo apt-get install build-essential cmake pkg-config1.3 安装libusb sudo apt-get install libusb-1.0-0-dev1.4 安装urboJPEG su…