【数据结构】排序——插入排序,选择排序
前言
本篇博客我们正式开启数据结构中的排序,说到排序,我们能联想到我之前在C语言博客中的冒泡排序,它是排序中的一种,但实现效率太慢,这篇博客我们介绍两种新排序,并好好深入理解排序
💓 个人主页:小张同学zkf
⏩ 文章专栏:数据结构
若有问题 评论区见📝
🎉欢迎大家点赞👍收藏⭐文章
目录
1.排序
1.1排序的概念
1.2排序的常见算法
2.插入排序
3.选择排序
1.排序
1.1排序的概念
1.2排序的常见算法

2.插入排序
即冒泡排序外,我们来认识一下一个新的排序
我们来看一下动图
如何用代码实现出来这个插入排序那
我们观察动图其实可以看到假如一趟0~end数是有序的,那么end+1的数得挨个与0~end数比较,比较若比end+1的数大,向右移一位,继续与下一位比较,若比end+1的数小,就插在这个数的前面,进行下一趟重复此过程
代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void charupaixu(int* a, int x)
{for (int i = 0; i < x - 1; i++){int end =i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end+1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}
int main()
{int arr[] = { 2,4,89,23,987,123,5678,13,76,67,6666};charupaixu(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){printf("%d ", arr[i]);}return 0;
}
这个排序的时间复杂度O(N)为N^2,但相比冒泡效率还是快的
3.选择排序
选择排序其实思路特别简单,通过最前面与最后面的指针进行遍历找到最大的与最小的,将最小的与开头的数交换,最大的与最后面的数交换,再两边指针减减,重复此过程
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void swap(int* as, int* aq)
{int tmp = *as;*as = *aq;*aq = tmp;
}
void xuanzepaixu(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[min] > a[i]){min = i;}if (a[max] < a[i]){max = i;}}swap(&a[min], &a[begin]);if (begin == max){max = min;}swap(&a[max], &a[end]);begin++;end--;}
}
int main()
{int arr[] = { 34,56,56,87,7644,79,382,4657,272687,246581,6341,346345,5,267,7,22,2724,57 };xuanzepaixu(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(0); i++){printf("%d ", arr[i]);}return 0;
}
但要注意,将最小数与开头数交换,此刻有可能最大数就是开头数,如果是这种情况,我们要刷新一遍最大值,然后再将最大值与结尾互换。
选择排序的时间复杂度也是O(N^2)但是比效率比冒泡还要低,综上三个排序,插入排序目前最优
结束语
这篇博客先介绍三个排序,与之前的冒泡排序已经有四个,但这些还都是太慢,其中之一的插入排序一定要好好掌握,下片博客的希尔排序要用到插入排序的思维
OK,本篇博客结束!!!
相关文章:
【数据结构】排序——插入排序,选择排序
前言 本篇博客我们正式开启数据结构中的排序,说到排序,我们能联想到我之前在C语言博客中的冒泡排序,它是排序中的一种,但实现效率太慢,这篇博客我们介绍两种新排序,并好好深入理解排序 💓 个人主…...
2024.6.9刷题记录
目录 一、1103. 分糖果 II 1.模拟 2.数学 二、312. 戳气球 1.递归-记忆化搜索 2.区间dp 三、2. 两数相加 1.迭代 2.递归-新建节点 3.递归-原节点 四、4. 寻找两个正序数组的中位数 1.堆 2.双指针二分 五、5. 最长回文子串 1.动态规划 2.中心扩展算法 六、6. Z…...
Matlab|遗传粒子群-混沌粒子群-基本粒子群
目录 1 主要内容 2 部分代码 3 效果图 4 下载链接 1 主要内容 很多同学在发文章时候最犯愁的就是创新点创新点创新点(重要的事情说三遍),对于采用智能算法的模型,可以采用算法改进的方式来达到提高整个文章创新水平的目的&…...
31|HTTP3:甩掉TCP、TLS 的包袱,构建高效网络
前面两篇文章我们分析了HTTP/1和HTTP/2,在HTTP/2出现之前,开发者需要采取很多变通的方式来解决HTTP/1所存在的问题,不过HTTP/2在2018年就开始得到了大规模的应用,HTTP/1中存在的一大堆缺陷都得到了解决。 HTTP/2的一个核心特性是…...
2 程序的灵魂—算法-2.2 简单算法举例-【例 2.3】
【例 2.3】判定 2000 — 2500 年中的每一年是否闰年,将结果输出。 润年的条件: 1. 能被 4 整除,但不能被 100 整除的年份; 2. 能被 100 整除,又能被 400 整除的年份; 设 y 为被检测的年份,则算法可表示如下…...
Python中的上下文管理器(contextlib)模块
Python中的contextlib模块提供了一些用于创建和管理上下文管理器(context managers)的工具。上下文管理器是实现了__enter__()和__exit__()方法的对象,它们通常用于确保在代码块执行前后执行某些操作,比如资源获取与释放、设置和重…...
C语言:定义和使用结构体变量
定义和使用结构体变量 介绍基础用法1.定义结构体2. 声明结构体变量3. 初始化和访问结构体成员4. 使用指针访问结构体成员5. 使用结构体数组 高级用法6. 嵌套结构体7. 匿名结构体8. 结构体和动态内存分配9. 结构体作为函数参数按值传递按引用传递 介绍 在C语言中,结…...
Vue3学习第二天记录
Vue3学习第二天记录 背景说明截图记录一个简单的JS文件Vue3的watch()函数Vue3的toRef()/toRefs()函数前端数据类型的分类前端写一个对外暴露的函数前端的...语法Vue3中watch()函数的总结Vue3中watchEffect()函数Vue3中watch()函数的坑Vue3中computed()函数 背景 最近在学习尚硅…...
C语言:双链表
一、什么是双链表? 双链表,顾名思义,是一种每个节点都包含两个链接的链表:一个指向下一个节点,另一个指向前一个节点。这种结构使得双链表在遍历、插入和删除操作上都表现出色。与单链表相比,双链表不仅可以…...
Java物业管理系统+数据库应用程序开发[JavaSE+JDBC+idea控制台+MySQL]
背景: 使用JavaSEJDBCMySQL技术实现一个物业管理系统,具体要求如下 物业管理系统需求: 需求分析 1.1用户需求分析 在进入系统之前,要进行身份确认,只有用户名和用户密码都相符的用户方可进入本系统,为…...
未在本地计算机上注册“Microsoft.ACE.OLEDB.12.0”提供程序。.net 读取excel的时候报错(实测有效)
1. 下载AccessDatabaseEngine.exe 下载链接 添加链接描述 2. office excel是64为的需要安装【AccessDatabaseEngine.exe】、32位的【AccessDatabaseEngine_X64.exe】 3. 我的是64为,跳过32位安装检测 1. 找到下载的安装包 2.输入安装包文件全称并在后面加上/pas…...
JVM垃圾收集器和性能调优
目标: 1.JVM垃圾收集器有哪几种? 2.CMS垃圾收集器回收步骤。 一、JVM常见的垃圾回收器 为什么垃圾回收的时候需要STW? 标记垃圾的时候,如果不STW,可能用户线程就会不停的产生垃圾。 1.1 单线程收集 Serial和SerialOld使用单…...
汽车EDI——Volvo EDI 项目案例
项目背景 作为Volvo的长期合作伙伴,C公司收到Volvo的EDI对接邀请,需要实现EDI对接。C公司将会面临哪些挑战?又应该相应地选择何种EDI解决方案呢? 汽车行业强调供需双方的高效协同(比如研发设计、生产计划、物流信息等…...
Qt应用程序发布
一、静态编译发布 1.0:以Release模式构建工程 1.1:查看当前构建生成路径,并将所生成的.exe单独拷贝出来 1.2:将可执行文件*.exe拷贝至任一目标文件夹:D:\Temporary\QQIF 2:查看安装Qt时发布工具windeployqt.exe所在的目录 windeployqt.exe在Qt开发套件的bin目录下。Qt的每…...
Python 机器学习 基础 之 【常用机器学习库】 NumPy 数值计算库
Python 机器学习 基础 之 【常用机器学习库】 NumPy 数值计算库 目录 Python 机器学习 基础 之 【常用机器学习库】 NumPy 数值计算库...
Linux Kernel nf_tables 本地权限提升漏洞(CVE-2024-1086)
文章目录 前言声明一、netfilter介绍二、漏洞成因三、漏洞危害四、影响范围五、漏洞复现六、修复方案临时解决方案升级修复方案 前言 2024年1月,各Linux发行版官方发布漏洞公告,修复了一个 netfilter:nf_tables 模块中的释放后重用漏洞(CVE-…...
[word] word如何清除超链接 #媒体#笔记#知识分享
word如何清除超链接 办公中,少不了使用word,这个是大家必备的软件,今天给大家分享下word如何清除超链接的操作办法,一起来学习下吧! 1、清除所有超链接 按下组合键CtrlshiftF9,就可以将网上复制带有超链…...
【Linux】进程(9):进程控制1
大家好,我是苏貝,本篇博客带大家了解Linux进程(9)进程控制1,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 目录 1 fork函数2 进程终止(A)终止是…...
华为RH2288H V3服务器iBMC的SSL证书续期
本文对华为RH2288H V3服务器iBMC的SSL证书续期,以避名登录告警提示及主机状态异常。 一、检查现网服务器iBMC的SSL证书到期时间 登录iBMC,点击配置--SSL证书,如下: 可以看到本服务器SSL证书将于今年7月22日到期。 二、联系厂家…...
ubuntu开机黑屏
BusyBox v1.30.1 (Ubuntu 1:1.30.1-4ubuntu6.1) built-in shell (ash) Enter help for a list of built-in commands. 解决: help 看看哪个盘出问题了 fsck -y /dev/sda1 (出问题的磁盘/分区) reboot 就可以进入系统了 fsck命令…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...



