《插入排序》与《选择排序》

目录

前言：

排序的概念：

插入排序：

1.直接插入排序：

2.希尔排序( 缩小增量排序 )：

选择排序：

1.直接选择排序:

2.快速排序：

hore思想：

挖坑法：

双指针法：

总结：

前言：

目前我们进入到了初阶数据结构的尾声，本章将讲解《直接插入排序》《希尔排序》《选择排序》《快速排序》

排序的概念：

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

以下是我们这两章需要学习的排序

插入排序：

1.直接插入排序：

直接插入排序是一种简单的插入排序法，

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

 代码分析：

当插入第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;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

 直接插入排序的特性总结：
        1. 元素集合越接近有序，直接插入排序算法的时间效率越高
        2. 时间复杂度：O(N^2)
        3. 空间复杂度：O(1)，它是一种稳定的排序算法
        4. 稳定性：稳定

2.希尔排序( 缩小增量排序 )：

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

void ShellSort(int* a, int n)
{
	int gap = n;
	//gap > 1的时候是预排序，目的让他接近有序
	//gap == 1的时候是直接插入排序，目的让他有序
	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 (tmp < a[end])
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}
	}
}

 

 

 

希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定

4. 稳定性：不稳定

 《数据结构(C语言版)》--- 严蔚敏 

 《数据结构-用面相对象方法与C++描述》--- 殷人昆

选择排序：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

1.直接选择排序:

1、在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
2、若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3、在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	
	while (begin < end)
	{
		int max = begin;
		int min = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] > a[max])
			{
				max = i;
			}

			if (a[i] < a[min])
			{
				min = i;
			}
		}

		swap(&a[min], &a[begin]);
		if (begin == max)
		{
			max = min;
		}
		swap(&a[max], &a[end]);
		begin++;
		end--;
	}
}

 简单来说就是找到最小的和第一个数据的换，找到最大的和最后一个换

但是要注意的是，存在一种情况：
就是begin的位置和max重叠，即第一个位置就是最大的数字

 

 

2.快速排序：

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
 

hore思想：

//hore思想
int PartSort1(int* a, int begin, int end)
{
	swap(&a[midi], &a[begin]);
	int left = begin;
	int right = end;
	int keyi = begin;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		swap(&a[left], &a[right]);
	}

	swap(&a[left], &a[keyi]);
	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	//hore思想
	int keyi = PartSort1(a, begin, end);

	//分区间[begin,keyi - 1] keyi [keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

我们将介绍三种快速排序的方式，第一种就是最传统的hore思想，其主要的思想和原理是：
“左边找大，右边找小”

如图我们将要对上面的数组进行排序，通过图画则可以完美阐释思路

 

 

 

 

 

以上就是对于总体的排序，而快速排序与二叉树相似，在我们完成总体的排序——“比关键字大的放左边，比关键字大的放右边” 之后，又需要对每一个“分支”再进行一次快速排序，所以我们在这里使用递归算法效率会好些。

 

与二叉树十分相似

 我们可以将区间分为：

[begin,keyi - 1]               keyi                    [keyi + 1, end]

那么hore思想在这就是利用了这个区间，不仅仅是hore，剩下的两种算法也是利用这几个区间。

挖坑法：

int PartSort2(int* a, int begin, int end)
{
	int key = a[begin];
	int hole = begin;
	
	while (begin < end)
	{
		//右边找小
		while (begin < end && a[end] > key)
		{
			--end;
		}
		a[hole] = a[end];
		hole = end;

		//左边找大
		while (begin < end && a[begin] < key)
		{
			++begin;
		}
		a[hole] = a[begin];
		hole = begin;
	}

	a[hole] = key;
	return hole;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	
	//挖坑法	
	//int keyi = PartSort2(a, begin, end);

	//分区间[begin,keyi - 1] keyi [keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

所谓的挖坑法，就是先让right找比关键字小的值，然后将找预先设置好的坑“填满”，再在end的位置“挖坑”。

之后再让left找比关键字大的值，然后将坑“填满”，再在begin的位置“挖坑”。

 

 最后再返回hole所指向的位置剩下的就是上述所讲的递归算法。

双指针法：

int PartSort3(int* a, int begin, int end)
{
	int keyi = begin;
	int prev = begin;
	int cur = prev + 1;

	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			swap(&a[prev], &a[cur]);
		}

		++cur;
	}
	swap(&a[prev], &a[begin]);
	keyi = prev;
	return keyi;
}


void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	//前后指针法
	//int keyi = PartSort3(a, begin, end);

	//分区间[begin,keyi - 1] keyi [keyi + 1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

三指针法的思路就是利用cur指针去找比关键字keyi小的值，再让prev++，之后对a[prev]与a[cur]进行交换，如果prev == cur，则无需多此一举的进行交换。

当cur不再小于等于end的时候，那么这个时候prev也肯定指向的是全数组最小的值，那么将a[prev]与a[begin]进行交换，就能将最小的值放置到最左边。

最后更新关键字，关键字此时则为a[prev]，并且继续分区间进行排序。

 

 

 

 剩下的就是和上述两种方法一致的步骤，分区间进行排序。

总结：

通过本章我们学习了很多排序，其中对于快速排序还需要我们进行较为深的理解，而希尔排序的时间复杂度的算法目前我们难以理解透彻。下面我们将对《归并排序》和《非递归的快速排序和归并排序》和《计数排序》进行讲解。

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

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

相关文章

责任链模式与spring容器的搭配应用

责任链模式与spring容器的搭配应用

背景 有个需求&#xff0c;原先只涉及到一种A情况设备的筛选&#xff0c;每次筛选会经过多个流程&#xff0c;比如先a功能&#xff0c;a功能通过再筛选b功能&#xff0c;然后再筛选c功能&#xff0c;以此类推。现在新增了另外一种B情况的筛选&#xff0c;B情况同样需要A情况的筛…
阅读更多...
软件设计师软考题目解析02 --每日五题

软件设计师软考题目解析02 --每日五题

想说的话&#xff1a;要准备软考了。0.0&#xff0c;其实我是不想考的&#xff0c;但是吧&#xff0c;由于本人已经学完所有知识了&#xff0c;只是被学校的课程给锁在那里了&#xff0c;不然早找工作去了。寻思着反正也无聊&#xff0c;就考个证玩玩。 本人github地址&#xf…
阅读更多...
网络中的进程监控

网络中的进程监控

每个企业都有一些流程和程序来实现他们的业务目标&#xff0c;这同样适用于网络&#xff0c;网络中的进程监控是分析、处理和管理网络内发生的各种活动以提高网络性能和能力的做法。 网络中需要监控的基本进程 监视系统资源&#xff08;CPU 利用率、内存利用率、CPU 温度等&a…
阅读更多...
ChatGPT在数据分析学习阶段的应用

ChatGPT在数据分析学习阶段的应用

ChatGPT在数据分析学习阶段的应用 ​ 这个阶段&#xff0c;核心是三件事&#xff1a;制定学习计划、确定学习资料以及学习策略。我们可以自己完成这几件事&#xff0c;当然也可以借助ChatGPT来高效地达到目的。 1.1 制定学习计划 ​ 学习阶段的第一件事是制定学习计划&#…
阅读更多...
红队评估四靶场

红队评估四靶场

文章目录 环境搭建1.设置所需网卡2.更改win7设置3.DC设置4.web设置开启docker服务5.kali网段`渗透启动`1.确认对方靶机的IP地址2.端口探测3.web探测`2001端口``2002端口`Tomcat/8.5.19漏洞复现`2003端口`4.docker逃逸5.ssh密钥爆破`域渗透启动`1.提权2.隧道搭建各项配置文件内容…
阅读更多...
自助点餐系统微信小程序，支持外卖、到店等

自助点餐系统微信小程序，支持外卖、到店等

总体介绍 系统总共分为三个端&#xff1a;后端&#xff0c;后台管理系统、微信小程序。 基于当前流行技术组合的前后端分离商城系统&#xff1a; SpringBoot2MybatisPlusSpringSecurityjwtredisVue的前后端分离的商城系统&#xff0c; 包含分类、sku、积分、多门店等 预览图…
阅读更多...
JavaSE-04笔记【面向对象01】

JavaSE-04笔记【面向对象01】

文章目录 1. final 关键字1.1 采用final修饰的类不能被继承1.2 采用 final 修饰的方法不能被覆盖1.3 采用 final 修饰的变量(基本类型)不能被修改1.4 采用final 修饰的变量必须显示初始化1.5 如果修饰的引用&#xff0c;那么这个引用只能指向一个对象&#xff0c;也就是说这个引…
阅读更多...
OpenBMC的c++代码中的变量初始化问题（二）

OpenBMC的c++代码中的变量初始化问题（二）

1 开发平台 Win11、VS2022、Fedora39。 2 作业目的 通过VS2022跨平台Linux构建openbmc/intel-ipmi-oem的x64可执行模块。 3 问题描述 该模块启动后&#xff0c;出现以下异常&#xff1a; 上图中的调用堆栈消息是&#xff1a; std::__uniq_ptr_impl<sd_bus, sdbusplus::…
阅读更多...
Windows下VTK 源码编译（For Qt PCL）

Windows下VTK 源码编译（For Qt PCL）

虽然我们在windows下安装PCL的时候就已经安装了VTK&#xff0c;由于跟着PCL安装的VTK是没有和QT联合编译的&#xff0c;所以在使用PCL和QT做点云可视化界面的时候是无法使用QT的插件QVTKWidget。 VTK 源码下载 Tags VTK / VTK GitLab 我这里的环境是Win10 Visual Studio&…
阅读更多...
Android 相机启动流程笔记

Android 相机启动流程笔记

和你一起终身学习&#xff0c;这里是程序员Android 经典好文推荐&#xff0c;通过阅读本文&#xff0c;您将收获以下知识点: 一、Camera 框架介绍&#xff1a; Camera的框架分为Kernel部分和hal部分&#xff0c;其中kernel部分主要有两块&#xff1a; image sensor driver&…
阅读更多...
【计算机学院寒假社会实践】——卫生服务无限情，社区居民乐融融

【计算机学院寒假社会实践】——卫生服务无限情，社区居民乐融融

为了加强社区基层党组织建设和改进社区工作&#xff0c;推动社区更好繁荣发展&#xff0c;曲阜师范大学计算机学院“青年扎根基层&#xff0c;服务走进社区”实践队员周兴睿在2024年2月14日来到了山东省滨州市陈集社区&#xff0c;对社区卫生进行清洁工作。 这一年&#xff0c;…
阅读更多...
[剪藏] - “闷声赚票房”的雷佳音，“窝囊废赛道”的成功学代表？

[剪藏] - “闷声赚票房”的雷佳音，“窝囊废赛道”的成功学代表？

作者| 糖炒山楂 编辑| Mia 猫眼专业版上&#xff0c;雷佳音主演电影票房达到了147亿&#xff0c;排在影人榜第12名。按照平台对《热辣滚烫》和《第二十条》最终票房的预测&#xff0c;他的个人票房还有10亿左右的上升空间。 相比贾玲、赵丽颖等女性扛起了春节档的焦点话题&a…
阅读更多...
微服务Day6

微服务Day6

文章目录 DSL查询文档RestClient查询文档快速入门 旅游案例 DSL查询文档 RestClient查询文档 快速入门 Testvoid testMatchAll() throws IOException {//1.准备RequestSearchRequest request new SearchRequest("hotel");//2.准备DSLrequest.source().query(QueryB…
阅读更多...
计算机网络实验四VLAN与三层交换机

计算机网络实验四VLAN与三层交换机

一、实验目的和要求 1&#xff09;掌握VLAN的基本配置方法&#xff0c;理解VLAN的功能和作用&#xff1b; 2&#xff09;掌握三层交换机的基本配置方法。 二、实验环境 1&#xff09;运行Windows 2008 Server/XP/7操作系统的PC一台。 2&#xff09;PacketTracer。 实验内…
阅读更多...
H12-821_29

H12-821_29

29.四台路由器运行IS-S且已经建立邻接关系,区域号和路由器的等级如图中标记,下列说法中正确的有? A.R2和R3都会产生ATT置位的Level-1的LSP B.R1没有R4产生的LSP,因此R1只能通过缺省路由和R4通信 C.R2和R3都会产生ATT置位的Leve1-2的LSP D.R2和R3互相学习缺省路由,该网络出现路…
阅读更多...
Github 2024-02-23 开源项目日报 Top10

Github 2024-02-23 开源项目日报 Top10

根据Github Trendings的统计&#xff0c;今日(2024-02-23统计)共有10个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量非开发语言项目4Python项目3TypeScript项目1HTML项目1Dart项目1Rust项目1 从零开始构建你喜爱的技术 创建周…
阅读更多...
CVE-2023-44313 Apache ServiceComb Service-Center SSRF 漏洞研究

CVE-2023-44313 Apache ServiceComb Service-Center SSRF 漏洞研究

本次项目基于go语言&#xff08;本人不精通&#xff09;&#xff0c;虽不是java web框架了 &#xff0c;但搭建web服务的框架一些思想理念却是通用的&#xff0c;我们由此可以得到一些蛛丝马迹....... 目录 漏洞简介 漏洞分析 漏洞复现 漏洞简介 Apache ServiceComb Servi…
阅读更多...
PCIe和SATA接口统计

PCIe和SATA接口统计

一、PCIe接口 1、Add-in-Card(AIC) AIC是最常见的PCIe接口形态，组装过电脑的同学可能比较清楚，电脑上的主板上都会有下面的几排插槽，这就是典型的PCIe AIC的插槽，比较常见的插槽位宽为x16和x1 插在上面的卡就是PCIe AIC。PCIe AIC常见的有显卡，无线网卡，存储设备等等 A…
阅读更多...
Javaweb之SpringBootWeb案例之AOP案例的详细解析

Javaweb之SpringBootWeb案例之AOP案例的详细解析

4. AOP案例 SpringAOP的相关知识我们就已经全部学习完毕了。最后我们要通过一个案例来对AOP进行一个综合的应用。 4.1 需求 需求&#xff1a;将案例中增、删、改相关接口的操作日志记录到数据库表中 就是当访问部门管理和员工管理当中的增、删、改相关功能接口时&#xff0c…
阅读更多...
Python入门学习——基础语法

Python入门学习——基础语法

一、Python解释器 1. Python解释器的作用是&#xff1a; 将Python代码翻译成计算机认识的O和1并提交计算机执行在解释器环境内可以一行行的执行我们输入的代码也可以使用解释器程序&#xff0c;去执行".py"代码文件 2. Python解释器程序在&#xff1a; <Python…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站