数据结构入门——排序(代码实现)(下)

int GetMidi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	// left mid right
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])  // mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right]) // mid是最小
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
  1. 三数取中

  2. int GetMidi(int* a, int left, int right):这是一个名为GetMidi的函数,接受一个整型数组指针a,左边界索引left和右边界索引right作为参数。

  3. int mid = (left + right) / 2;:计算左右边界索引的中间索引mid,用于表示三个元素中间位置的索引。

  4. if (a[left] < a[mid]):如果左边界元素小于中间元素。

    a. if (a[mid] < a[right]):且中间元素小于右边界元素,则中间元素为中间值,返回中间索引mid

    b. else if (a[left] > a[right]):否则,如果左边界元素大于右边界元素,说明中间元素为最大值,返回左边界索引left

    c. else:否则,右边界元素为最大值,返回右边界索引right

  5. else:如果左边界元素大于中间元素。

    a. if (a[mid] > a[right]):且中间元素大于右边界元素,则中间元素为中间值,返回中间索引mid

    b. else if (a[left] < a[right]):否则,如果左边界元素小于右边界元素,说明中间元素为最小值,返回左边界索引left

    c. else:否则,右边界元素为最小值,返回右边界索引right

// Hoare
int PartSort1(int* a, int left, int right)
{
	//int midi = GetMidi(a, left, right);
	//Swap(&a[left], &a[midi]);

	int keyi = left;
	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[keyi], &a[left]);
	return left;
};
  1. 快速排序(一)

  2. int PartSort1(int* a, int left, int right):这是一个名为PartSort1的函数,用于对数组进行划分操作,接受一个整型数组指针a,左边界索引left和右边界索引right作为参数。

  3. int keyi = left;:初始化关键元素索引keyi为左边界索引left,作为划分的基准元素索引。

  4. while (left < right):进入一个while循环,循环条件是左边界索引小于右边界索引,表示还有未比较的元素。

  5. while (left < right && a[right] >= a[keyi]):从右边开始找到第一个小于基准元素的元素位置。

  6. while (left < right && a[left] <= a[keyi]):从左边开始找到第一个大于基准元素的元素位置。

  7. Swap(&a[left], &a[right]);:交换左右两侧找到的不符合条件的元素,使得左侧元素小于基准元素,右侧元素大于基准元素。

  8. 继续循环,直到左右指针相遇。

  9. Swap(&a[keyi], &a[left]);:交换基准元素和左指针所指的元素,将基准元素放置到正确的位置。

  10. return left;:返回基准元素的最终位置,用于后续递归调用。

int PartSort2(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	// 保存key值以后,左边形成第一个坑
	int hole = left;

	while (left < right)
	{
		// 右边先走,找小,填到左边的坑,右边形成新的坑位
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;

		// 左边再走,找大,填到右边的坑,左边形成新的坑位
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;
	return hole;
}
  1. 快速排序(二)

  2. int PartSort2(int* a, int left, int right):这是一个名为PartSort2的函数,用于对数组进行划分操作,接受一个整型数组指针a,左边界索引left和右边界索引right作为参数。

  3. int midi = GetMidi(a, left, right);:调用GetMidi函数找到左、中、右三个元素中的中间值索引midi,并将中间值元素与左边界元素交换位置。

  4. int key = a[left];:将左边界元素作为基准值key

  5. int hole = left;:初始化一个坑位hole,用于保存基准值的位置。

  6. while (left < right):进入一个while循环,循环条件是左边界索引小于右边界索引,表示还有未比较的元素。

  7. while (left < right && a[right] >= key):从右边开始找到第一个小于基准值的元素位置。

    a. a[hole] = a[right];:将找到的小于基准值的元素填充到左边的坑位,并更新坑位hole为右边界索引right

  8. while (left < right && a[left] <= key):从左边开始找到第一个大于基准值的元素位置。

    a. a[hole] = a[left];:将找到的大于基准值的元素填充到右边的坑位,并更新坑位hole为左边界索引left

  9. 继续循环,直到左右指针相遇。

  10. a[hole] = key;:将基准值填充到最后的坑位,完成一次划分操作。

  11. return hole;:返回基准值的最终位置,用于后续递归调用。

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}
  1. 快速排序(三)

  2. int PartSort3(int* a, int left, int right):这是一个名为PartSort3的函数,用于对数组进行划分操作,接受一个整型数组指针a,左边界索引left和右边界索引right作为参数。

  3. int midi = GetMidi(a, left, right);:调用GetMidi函数找到左、中、右三个元素中的中间值索引midi,并将中间值元素与左边界元素交换位置。

  4. int prev = left;:初始化prev为左边界索引left,用于记录小于基准值的元素的位置。

  5. int cur = prev + 1;:初始化curprev的下一个位置,用于遍历数组。

  6. int keyi = left;:初始化keyi为左边界索引left,作为划分的基准元素索引。

  7. while (cur <= right):进入一个while循环,循环条件是当前位置小于等于右边界索引,表示还有未比较的元素。

  8. if (a[cur] < a[keyi] && ++prev != cur):如果当前元素小于基准值且prev不等于cur,则交换prevcur位置的元素,将小于基准值的元素放到prev的下一个位置。

  9. ++cur;:移动cur指针到下一个位置。

  10. 继续循环直到遍历完整个数组。

  11. Swap(&a[prev], &a[keyi]);:将基准值放置到prev位置,完成一次划分操作。

  12. return prev;:返回基准值的最终位置,用于后续递归调用。

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

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

相关文章

c++二叉树的进阶--二叉搜索树

1. 二叉搜索树的概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值 若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根节点的值 它的左…

R-Tree与其他空间索引结构的对比

文章目录 R-Tree vs Quadtree/OctreeR-Tree vs kd-TreeR-Tree vs BSP TreeR-Tree vs Hilbert R-Tree总结Python: 使用rtree库实现R-TreeJavaScript: 使用rbush库实现kd-Tree R-Tree是一种广泛使用的空间索引结构&#xff0c;尤其适用于处理多维空间数据。然而&#xff0c;还有其…

电脑上怎么调照片尺寸?怎么压缩图片为144×144

在一些社交媒体平台通常要求用户上传头像&#xff0c;并对其进行裁剪和调整大小&#xff0c;144x144像素是常见的头像尺寸之一&#xff0c;适合在社交媒体上展示个人头像或者小图标&#xff0c;为了可以保证图片的画质&#xff0c;我们尽量会选择专业的图片处理工具来完成操作。…

OpenAI推出强化企业级安全与成本管理新功能

欢迎大家在 GitHub 上 Star 我们&#xff1a; 分布式全链路因果学习系统 OpenASCE: https://github.com/Open-All-Scale-Causal-Engine/OpenASCE 大模型驱动的知识图谱 OpenSPG: https://github.com/OpenSPG/openspg 大规模图学习系统 OpenAGL: https://github.com/TuGraph-…

探索在Apache SeaTunnel上使用Hudi连接器,高效管理大数据的技术

Apache Hudi是一个数据湖处理框架&#xff0c;通过提供简单的方式来进行数据的插入、更新和删除操作&#xff0c;Hudi能够帮助数据工程师和科学家更高效地处理大数据&#xff0c;并支持实时查询。 支持的处理引擎 Spark Flink SeaTunnel Zeta 主要特性 批处理 流处理 精确一次性…

Linux——(grep指令及zip/tar压缩指令)

1.grep指令 语法&#xff1a; grep【选项】查找字符串 文件 功能&#xff1a; 在文件中搜索字符串&#xff0c;将找到的行打印出来 常用选项&#xff1a; -i &#xff1a;忽略大小写&#xff0c;所以大小写视为相同 -n &#xff1a; 顺便输出行号 -v &#xff1a;反向选择&…

DDD领域驱动设计总结和C#代码示例

DDD&#xff08;领域驱动设计&#xff09;是一种软件设计方法&#xff0c;它强调以业务领域为核心来驱动软件的设计和开发。 DDD 的设计初衷是为了解决复杂业务领域的设计和开发问题&#xff0c;它提供了一套丰富的概念和模式&#xff0c;帮助开发者更好地理解和建模业务领域&…

【管理咨询宝藏88】556页!公司经营分析内部培训

本报告首发于公号“管理咨询宝藏”&#xff0c;如需阅读完整版报告内容&#xff0c;请查阅公号“管理咨询宝藏”。 【管理咨询宝藏88】556页&#xff01;公司经营分析内部培训 【格式】PDF版本 【关键词】经营分析、内部培训、多业务分析 【核心观点】 - 非常全面和详细的公…

Composer初次接触

php一直都是简单处理一下单片机的后台服务&#xff0c;没什么深入研究 今天安装一个 php composer.phar require qiniu/php-sdkComposer完全不懂&#xff0c;照着一试&#xff0c;就报错了 - topthink/think-installer v1.0.12 requires composer-plugin-api ^1.0 -> found…

Python爬虫入门指南--爬虫技术的由来、发展与未来--实战课程大赠送

爬虫&#xff0c;也称为网络爬虫或网络蜘蛛&#xff0c;是一种自动化程序&#xff0c;专门用于遍历互联网并收集数据。这种技术的起源、发展和未来都与互联网紧密相连&#xff0c;并在信息检索、数据挖掘等多个领域发挥着不可或缺的作用。 "免费IP池大放送&#xff01;助…

【汇编语言】流程转移和子程序

【汇编语言】流程转移和子程序 文章目录 【汇编语言】流程转移和子程序前言一、“转移”综述二、操作符offset三、jmp指令jmp指令——无条件转移jmp指令&#xff1a;依据位移进行转移两种段内转移远转移&#xff1a;jmp far ptr 标号转移地址在寄存器中的jmp指令转移地址在内存…

Linux信号(处理)

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 前言&#xff1a; Linux信号(产生)-CSDN博客 Linux信号(保存)-CSDN博客 前面我们解释了信号的产生和保存&#xff0c;接下来我们就要解释信号的处理&#xff0c;关于操作系统在合适的时候对信号进行处理&#xff0c;合适…

C++奇迹之旅:从0开始实现日期时间计算器

文章目录 &#x1f4dd;前言&#x1f320; 头文件Date.h&#x1f309;日期计算函数&#x1f320;前后置&#x1f309;前后置-- &#x1f320;两对象日期相减&#x1f309;自定义流输入和输出 &#x1f309; 代码&#x1f309; 头文件Date.h&#x1f320;Date.cpp&#x1f309; …

(windows ssh) windows开启ssh服务,并通过ssh登录该win主机

☆ 问题描述 想要通过ssh访问win主句 ★ 解决方案 安装ssh服务 打开服务 如果这里开不来就“打开服务”&#xff0c;找到下面两个开启服务 然后可以尝试ssh链接&#xff0c;注意&#xff0c;账号密码&#xff0c;账号是这个&#xff1a; 密码是这个 同理&#xff0c;如果…

matlab新手快速上手5(蚁群算法)

本文根据一个较为简单的蚁群算法框架详细分析蚁群算法的实现过程&#xff0c;对matlab新手友好&#xff0c;源码在文末给出。 蚁群算法简介&#xff1a; 蚁群算法是一种启发式优化算法&#xff0c;灵感来源于观察蚂蚁寻找食物的行为。在这个算法中&#xff0c;解决方案被看作是…

vue3中的ref、isRef、shallowRef、triggerRef和customRef

1.ref 接受一个参数值并返回一个响应式且可改变的 ref 对象。 ref 对象拥有一个指向内部值的单一属性 .value property &#xff0c;指向内部值。 例&#xff1a;此时&#xff0c;页面上的 str1 也跟着变化 <template><div><button click"handleClick&quo…

BUUCTF-MISC-10.LSB1

10.LSB1 题目&#xff1a;lsb隐写&#xff0c;stegsolve可以看到包含了一个PNG图片 使用stegsolve打开这个图片 由PNG文件头可以看出隐写内容为PNG文件&#xff0c;按save Bin键保存为PNG文件。 得到一张二维码图片&#xff0c;使用CQR扫一下

盲返模式:电商领域的新玩法与商业创新

大家好&#xff0c;我是微三云周丽&#xff0c;今天给大家分析当下市场比较火爆的商业模式&#xff01; 小编今天跟大伙们分享什么是什么是盲返模式&#xff1f; 随着互联网的深入发展&#xff0c;电商行业正面临着前所未有的机遇与挑战。在这个竞争激烈的市场环境中&#xff…

GAN 生成对抗神经网络

GAN 文章目录 GANGAN的结构GAN的目标函数GAN的训练GAN的优势和不足优势不足 GAN的结构 GAN的设计灵感来源于博弈论中的零和博弈&#xff08;Zero-sum Game&#xff09;&#xff0c;在零和博弈中&#xff0c;参与双方的收益是完全相反的&#xff0c;一方的收益必然导致另一 方的…

Python400集 视频教程,手把手带你零基础手写神经网络!!

嗨喽&#xff0c;大家好&#xff0c;今天又要给大家整一波福利了&#xff01; 学习编程&#xff0c;最忌讳就是今天一个教程&#xff0c;明天一个教程&#xff0c;频繁更换教程&#xff0c;增加自己的学习成本&#xff0c;对于新手小白会是一件严重打击自信心的事情。所以今天…