【C语言/数据结构】排序(选择排序,推排序,冒泡排序)

 🌈个人主页:秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥 系列专栏:《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

9efbcbc3d25747719da38c01b3fa9b4f.gif​​​​

目录

选择排序

选择排序

​编辑 

 代码呈现

堆排序

代码呈现

交换排序

冒泡排序


前言

    💬 hello! 各位铁子们大家好哇。

             今日更新了选择,堆,冒泡排序的内容
    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

 

选择排序

选择排序

过程图如下: 

 代码呈现

//时间复杂度:O(N^2)
//最好情况下:O(N^2)
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		//当max在begin的位置时
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

分析:开始时,begin指向首元素,end是末尾元素下标。这里的选择排序与上图过程略有差异,这里的选择排序每次选出最大和最小值,分别与头和尾交换。然后begin++和end--来缩小选择的范围。需注意,在同时选最大和最小时,要判断max是否在begin的位置上,如果是,就要把maxi改为mini的值。

堆排序

代码呈现

void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		//假设左孩子小,如果假设错了,就更新一下
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//升序
void HeapSort(int* a, int n)
{
	//建大堆
	//O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

堆排序在前面的文章中已经讲解,这里不再介绍。

交换排序

冒泡排序

//时间复杂度:O(N^2)
//最好情况:O(N);
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = true;
			}
		}
		if (exchange == false)
			break;
	}
}

 分析:这里简单说下时间复杂度最好情况:O(N)。在第一次外层for循环时,如果内层循环结束后,exchange的值还是false,就说明已经是排序好了的,就可以break掉循环,这时就遍历了一次,时间复杂度就是O(N)。

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

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

相关文章

【开源】基于JAVA语言的学生综合素质评价系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 学生功能2.2 教师功能2.3 教务处功能 三、系统展示四、核心代码4.1 查询我的学科竞赛4.2 保存单个问卷4.3 根据类型查询学生问卷4.4 填写语数外评价4.5 填写品德自评问卷分 五、免责说明 一、摘要 1.1 项目介绍 基于J…

美睫师睫毛嫁接零基础学习,日式美睫与开花嫁接实战教学

一、教程描述 大家都说女人的钱好挣&#xff0c;这是因为每个女人在每年&#xff0c;都要花很多钱来打扮自己。本套教程是关于日式美睫和开花嫁接的&#xff0c;从零基础学习到店铺经营都有涉及&#xff0c;就做美睫和睫毛嫁接这两项业务&#xff0c;月收入万元以上应该问题不…

ubuntu 22.04 安装mysql-8.0.34

ubuntu 22.04 安装mysql-8.0.34 1、基础安装配置 更新软件包&#xff1a; sudo apt update查看可用软件包&#xff1a; sudo apt search mysql-server安装最新版本&#xff1a; sudo apt install -y mysql-server或者&#xff0c;安装指定版本&#xff1a; sudo apt inst…

202|读书笔记《金融的本质:伯南克四讲美联储》

今天跟朋友聊天&#x1f4ac;&#xff0c;说已经没人看书了&#x1f4d6; 我想&#xff0c; 还是会有人读书的吧。 ​ 一、美联储的起源和使命 1. 第一讲&#xff1a;美国南北战争结束后的40年间&#xff0c;美国经历了6次大的银行体系恐慌&#xff0c;促使其于1913年成立美联储…

第八篇【传奇开心果系列】beeware的toga开发移动应用示例:实现消消乐安卓手机小游戏

传奇开心果博文系列 系列博文目录beeware的toga开发移动应用示例系列博文目录一、项目目标二、安装依赖三、初步实现四、扩展思路五、实现游戏逻辑示例代码六、实现界面设计示例代码七、实现增加关卡和难度示例代码八、实现存档和排行榜示例代码九、实现添加特殊方块和道具示例…

C语言第十一弹---函数(下)

​ ✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 函数 1、嵌套调用和链式访问 1.1、嵌套调用 1.2、链式访问 2、函数的声明和定义 2.1、单个文件 2.2、多个文件 2.3、static 和 extern 2.3.1、static…

第六课:Prompt

文章目录 第六课&#xff1a;Prompt1、学习总结&#xff1a;Prompt介绍预训练和微调模型回顾挑战 Pre-train, Prompt, PredictPrompting是什么?prompting流程prompt设计 课程ppt及代码地址 2、学习心得&#xff1a;3、经验分享&#xff1a;4、课程反馈&#xff1a;5、使用Mind…

08. BI - 万字长文,银行如何做贷款违约的预测,特征处理及学习

本文为 「茶桁的 AI 秘籍 - BI 篇 第 08 篇」 文章目录 课程回顾案例分析案例实战 Hi&#xff0c; 你好。我是茶桁。 课程回顾 上节课&#xff0c;咱们讲了一个股票的指标&#xff1a;MACD。在趋势行情里面它应该还是有效的指标。它比较忌讳动荡行情&#xff0c;比如说它一会上…

###C语言程序设计-----C语言学习(5)#

前言&#xff1a;感谢您的关注哦&#xff0c;我会持续更新编程相关知识&#xff0c;愿您在这里有所收获。如果有任何问题&#xff0c;欢迎沟通交流&#xff01;期待与您在学习编程的道路上共同进步&#xff01; 一. 主干知识的学习 1.switch语句 switch语句可以处理多分支选…

ubuntu 22 安装 node,npm,vue

1:安装 nodejs sudo apt update curl -fsSL https://deb.nodesource.com/setup_20.x | sudo -E bash - sudo apt update && sudo apt install -y nodejs node -v 2:安装npm sudo npm install n -g npm -v 3:安装vite npm install vite -g 4:运行vue 把项目拷贝到…

公考之判断推理(一、图形推理)

一、前言 判断推理这一题型主要具体分为四种题型&#xff1a; 1.图形推理 2.类比推理 3.定义判断 4.逻辑判断每种题型做题方法又不一样。 才本文采用总分的形式结构。 每一小标题的下面紧接着就是总结。二、图形推理常见的命题形式 图形推理常见的命题形式&#xff1a; 1.…

鸿蒙ArkUI 宫格+列表+HttpAPI实现

鸿蒙ArkUI学习实现一个轮播图、一个九宫格、一个图文列表。然后请求第三方HTTPAPI加载数据&#xff0c;使用了axios鸿蒙扩展库来实现第三方API数据加载并动态显示数据。 import {navigateTo } from ../common/Pageimport axios, {AxiosResponse } from ohos/axiosinterface IDa…

ASP.NET Core基础之用扩展方法封装服务配置

阅读本文你的收获 了解C#中的扩展方法机制学会在ASP.NET Core 中&#xff0c;用扩展方法封装服务配置&#xff0c;使得代码更加简洁 一、什么是扩展方法 扩展方法使能够向现有类型添加方法&#xff0c;而无需创建新的派生类型、重新编译或以其他方式修改原始类型。 扩展方法…

从 React 到 Qwik:开启高效前端开发的新篇章

1. Qwik Qwik 是一个为构建高性能的 Web 应用程序而设计的前端 JavaScript 框架,它专注于提供即时启动性能,即使是在移动设备上。Qwik 的关键特性是它采用了称为“恢复性”的技术,该技术消除了传统前端框架中常见的 hydration 过程。 恢复性是一种序列化和恢复应用程序状态…

HbuilderX报错“Error: Fail to open IDE“,以及运行之后没有打开微信开发者,或者运行没有反应的解决办法

开始 问题:HbuilderX启动时,打开微信开发者工具报错"Error: Fail to open IDE",以及运行之后没有打开微信开发者,或者运行没有反应的解决办法! 解决办法: 按照步骤一步一步完成分析,除非代码报错,否则都是可以启动的 第一步:检查HbuildX是否登录账号 第二步:检查微信…

背后的魔术师----jsp

作为一名对技术充满热情的学习者&#xff0c;我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代&#xff0c;我远非专家&#xff0c;而是一位不断追求进步的旅行者。通过这篇博客&#xff0c;我想分享我在某个领域的学习经验&#xff0c;与大家共同探讨、共…

嵌入式软件工程师面试题——2025校招社招通用(C/C++)(四十四)

说明&#xff1a; 面试群&#xff0c;群号&#xff1a; 228447240面试题来源于网络书籍&#xff0c;公司题目以及博主原创或修改&#xff08;题目大部分来源于各种公司&#xff09;&#xff1b;文中很多题目&#xff0c;或许大家直接编译器写完&#xff0c;1分钟就出结果了。但…

Linux编译实时内核和打补丁

目录 1.Linux内核2.实时内核3.编译实时内核3.1 准备3.2 获取内核源码3.3 编译3.4 设置GRUB确保启动到实时内核 4.给内核打补丁5.安装新的内核 1.Linux内核 https://github.com/torvalds/linux Linux内核是Linux操作系统的核心部分&#xff0c;它是操作系统的基本组成部分&…

研发日记,Matlab/Simulink避坑指南(七)——数据溢出钳位Bug

文章目录 前言 背景介绍 问题描述 分析排查 解决方案 总结归纳 前言 见《研发日记&#xff0c;Matlab/Simulink避坑指南(二)——非对称数据溢出Bug》 见《研发日记&#xff0c;Matlab/Simulink避坑指南(三)——向上取整Bug》 见《研发日记&#xff0c;Matlab/Simulink避坑…

棋盘(来源:第十四届蓝桥杯省赛JavaA/C/研究生组 , 第十四届蓝桥杯省赛PythonC组)

小蓝拥有 nn大小的棋盘&#xff0c;一开始棋盘上全都是白子。 小蓝进行了 m 次操作&#xff0c;每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色&#xff0c;黑色棋子变为白色)。 请输出所有操作做完后棋盘上每个棋子的颜色。 输入格式 输入的第…
最新文章