C++数据结构X篇_21_插入排序(稳定的排序)

文章目录

  • 1. 插入排序原理
  • 2. 算法图解
  • 3. 核心代码:
  • 4. 插入排序整体代码实现

1. 插入排序原理

插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

  1. 原理是将无序序列插入到有序序列中
  2. 直接插入排序的两种性质:
  • 当待排序的原序列中大多数元素都已有序的情况下,此时进行的元素比较和移动的次数较少;

  • 当原序列的长度很小时,即便它的所有元素都是无序的,此时进行的元素比较和移动的次数还是很少。

后篇介绍的希尔排序就是基于上面2个性质的改进

2. 算法图解

将待排序的集合看做两部分,已排序的区间(0…i) ; 待排序的区间[i…n);每次选择无序区间的第一个元素插入到有序区间的合适位置,直到整个数组有序。

因为不知道数组中得前几个元素是已经有序的,所以直接从第二个元素开始执行插入排序,将每个元素都进行一次插入排序。

算法图解如下:
在这里插入图片描述

3. 核心代码:

void insert_sort(int arr[], int length)  //升序
{int j;//第一个元素当做有序的,第二个看做无序,从第二个插入第一个元素并进行比较for (int i = 1; i < length; i++){if (arr[i] < arr[i - 1])  //比升序序列最大值要小,进入插入排序{int temp = arr[i];//从右向左for (j = i - 1; j >= 0; j--){if (temp < arr[j]) //升序序列中元素大于arr[i]{arr[j + 1] = arr[j]; //向前移动一位}else{break;}}arr[j + 1] = temp;}}
}

4. 插入排序整体代码实现

#include <iostream>
using namespace std;void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//打印数组
void printArr(int arr[])
{for (int i = 0; i < 10; i++){cout << arr[i] << endl;}
}//插入排序
void insert_sort(int arr[], int length)  //升序
{int j;for (int i = 1; i < length; i++){if (arr[i] < arr[i - 1])  //比升序序列最大值要小{int temp = arr[i];for (j = i - 1; j >= 0; j--){if (temp < arr[j]) //升序序列中元素大于arr[i]{arr[j + 1] = arr[j]; //向前移动一位}else{break;}}arr[j + 1] = temp;}}printArr(arr);
}int main()
{int arr[] = { 8,2,3,9,6,4,7,1,5,10 };insert_sort(arr, 10);system("pause");return 0;
}

运行结果:
在这里插入图片描述

  1. 插入排序,插入排序代码实现,插入排序代码思路梳理
  2. 优秀博文:十大经典排序算法-插入排序算法详解,常见的几种排序(C++)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

toluaframework中C#怎么调用Lua的方法以及无GC方法

toluaframework中C#怎么调用Lua的方法 问题Util.CallMethodLuaManager.CallFunctionLuaFunction.LazyCall 解决方案LuaFunction脚本无GC消耗的调用 用法总结 问题 用过luaframework框架的人应该都知道框架提供了Util的工具类&#xff0c;工具类提供了一个方法就是Util.CallMet…

可自由搭建的能源管理平台,轻松实现高效节能

随着科技的不断发展&#xff0c;能源问题越来越重要。为了提高能源的利用效率&#xff0c;减少能源浪费&#xff0c;能源用能企业纷纷开始注重能源管理工作&#xff0c;并想要一款可以进行高效管理的工具。智慧能源管理平台&#xff0c;是一款可自由搭建的能源管理平台&#xf…

零基础Linux_23(多线程)线程安全+线程互斥(加锁)+死锁

目录 1. 线程安全 1.1 线程不安全前期 1.2 线程不安全原因 2. 线程互斥 2.1 加锁保护&#xff08;代码&#xff09; 2.2 锁的本质 3. 可重入对比线程安全 4. 死锁 4.1 死锁的必要条件 4.2 避免死锁 5. 笔试面试题 答案及解析 本篇完。 1. 线程安全 基于上一篇线程…

改善游戏体验:数据分析与可视化的威力

当今&#xff0c;电子游戏已经超越了娱乐&#xff0c;成为一种文化现象&#xff0c;汇聚了全球数十亿的玩家。游戏制作公司正采用越来越复杂的技术来提高游戏质量&#xff0c;同时游戏数据分析和可视化工具变得不可或缺。 数据的力量&#xff1a;解析游戏体验 游戏制作涉及到大…

C51--单片机中断

51单片机是单线程模式&#xff0c;需要用到硬件中断。 一、中断系统 中断系统是为使CPU具有对外界紧急事件的实时处理能力而设置的。 当中央处理器CPU正在处理某件事的时候&#xff0c;外界发生了紧急事件请求&#xff0c;要求CPU暂停当前工作&#xff0c;转而去处理这个紧急…

软考高项-计算题(3)

题10 问题一 EV50*0.525 问题二 EACBAC/CPI CPIEV/AC25/28 EAC50*28/2556 问题三 因为CPI<1&#xff0c;所以项目实际费用超支 题11 PV2000500010000750006500020000177000 AC2100450012000860006000015000179600 EV200050001000075000*0.965000*0.720000*0.351370…

CANOE 仿真+测试

仿真测试 CANoe的自动化测试系统简介Canoe TFS常用函数测试判别函数测试架构函数测试报告函数检测函数 创建自动化测试工程其他常用函数 CANoe的自动化测试系统简介 基于CANoe的自动化测试系统架构&#xff0c;根据ECU的测试环境和测试规范&#xff0c;搭建基于CANoe的测试系统…

【置顶帖】关于博主/关于博客/博客大事记

关于博主 ● 信息安全从业者 ● 注册信息安全认证专家资质 ● CSDN认证业界专家、安全博客专家 、全栈安全领域优质创作者 ● 中国信通院【2021-GOLF IT新治理领导力论坛】演讲嘉宾 ● 安世加【2021-EISS企业信息安全峰会-上海】演讲嘉宾 ● CSDN【2022-隐私计算论坛】演讲嘉宾…

uni-app打包apk实现自动更新

一、直接复制粘贴就可用(豪横) app.vue文件里写 //app.vue里写 <script>export default {onShow: function() {console.log(App Show)},onHide: function() {console.log(App Hide)},onLaunch: function() {let appVersion uni.getSystemInfo({success: function(e) {ap…

springboot在线招聘系统

springboot在线招聘管理系统&#xff0c;java在线招聘管理系统&#xff0c;在线招聘管理系统 运行环境&#xff1a; JAVA版本&#xff1a;JDK1.8 IDE类型&#xff1a;IDEA、Eclipse都可运行 数据库类型&#xff1a;MySql&#xff08;8.x版本都可&#xff09; 硬件环境&#xf…

手机桌面待办事项APP推荐

每天&#xff0c;我们每个人都面临着繁琐的事务和任务&#xff0c;而手机成了我们日常生活中不可或缺的伙伴。手机上的待办事项工具像一个可靠的助手&#xff0c;可以帮助我们更好地记录、管理和完成任务。在手机桌面上使用的待办事项APP推荐用哪一个呢&#xff1f; 手机是我们…

MTK AEE_EXP调试方法及user版本打开方案

一、AEE介绍 AEE (Android Exception Engine)是安卓的一个异常捕获和调试信息生成机制。 手机发生错误(异常重启/卡死)时生成db文件(一种被加密过的二进制文件)用来保存和记录异常发生时候的全部内存信息,经过调试和仿真这些信息,能够追踪到异常的缘由。 二、调试方法…

OS的Alarm定时器调度机制

调度表触发的任务在编译时就被静态定义&#xff0c;任务的触发时间和执行顺序是固定的。这种方式适用于已知的、固定的任务触发模式&#xff0c;例如周期性任务或事件驱动任务。而使用 Alarm 机制触发的任务具有更大的灵活性。Alarm 允许在运行时动态地设置和修改任务的触发时间…

人工智能轨道交通行业周刊-第64期(2023.10.16-10.29)

本期关键词&#xff1a;北斗应用、供电智能运维、5G-R、铁路职称、星火大模型 1 整理涉及公众号名单 1.1 行业类 RT轨道交通人民铁道世界轨道交通资讯网铁路信号技术交流北京铁路轨道交通网上榜铁路视点ITS World轨道交通联盟VSTR铁路与城市轨道交通RailMetro轨道世界铁路那…

数据可视化报表分享:区域管理驾驶舱

在零售数据分析中&#xff0c;区域管理驾驶舱报表是用来分析企业运营数据&#xff0c;以制定销售策略和提高利润。因此这张报表需要整合大量数据&#xff0c;数据整合、分析、指标计算的工作量极大&#xff0c;在讲究高效率、高度及时性的大数据时代&#xff0c;BI数据可视化分…

QT图形视图框架绘制曲线图和Smith图

QT图形视图框架绘制曲线图和Smith图 QGraphicsView是Qt框架中的一个图形视图部件&#xff0c;用于显示和处理2D图形元素。它提供了强大的工具来创建交互式和自定义的图形应用程序。在绘制折线图和Smith图时&#xff0c;使用QGraphicsView有以下一些优点&#xff1a; 交互性&am…

iOS开发-CoreNFC实现NFC标签Tag读取功能

iOS开发-CoreNFC实现NFC标签Tag读取功能 一、NFC近场通信 近场通信&#xff08;NFC&#xff09;是一种无线通信技术&#xff0c;它使设备能够在不使用互联网的情况下相互通信。它首先识别附近配备NFC的设备。NFC常用于智能手机和平板电脑。 二、实现NFC标签Tag读取功能 在…

vue实现多时间文字条件查询

// 搜索功能 // 获取搜索框内容 const dateOneref() const dateTworef() // 重新创建数组 const itemList ref([]); const query()>{console.log(formattedDateTime.value);console.log(list.value);itemList.value list.value.filter(item > {//获取数据框的内容是否与…

server2012 通过防火墙开启局域网内限定IP进行远程桌面连接

我这里需要被远程桌面的电脑系统版本为windows server2012 1、打开允许远程连接设置 2、开启防火墙 3、设置允许“远程桌面应用”通过防火墙 勾选”远程桌面“ 3、入站规则设置 高级设置→入站规则→远程桌面-用户模式(TCP-In) 进入远程桌面属性的作用域——>远程IP地址—…

FL Studio21最新中文版DAW数字音频工作站

大概从去年开始&#xff0c;“电子音乐制作技术”成为越来越常见的说法。一开始我们觉得这种说法太过于笼统&#xff0c;因为电子音乐制作的技术早已不限于用在电子音乐&#xff0c;它更像是现代音乐制作技术。毕竟现代化的90%的音乐都是这么做出来的。 对&#xff0c;我们说的…