首页 > 其他分享 >插入排序详细解读

插入排序详细解读

时间:2024-08-21 22:15:00浏览次数:12  
标签:arr 元素 key int 插入排序 位置 解读 索引 详细

插入排序详细解读

图解

第一轮:从第二位置的 6 开始比较,比前面 7 小,交换位置。

img

第二轮:第三位置的 9 比前一位置的 7 大,无需交换位置。

img

第三轮:第四位置的 3 比前一位置的 9 小交换位置,依次往前比较。

img

第四轮:第五位置的 1 比前一位置的 9 小,交换位置,再依次往前比较。

img

......

就这样依次比较到最后一个元素。

步骤解读:

STEP 1:【模拟后面待排序元素】

我们需要有一个外层循环,来不断的将后面新的待排元素进行变换,会不断的取第二个,取第三个.......;(待排元素可以从索引1开始,因为索引1左侧就一个数据,是索引0是有顺序的)

#include<iostream>
using namespace std;
int main() {
	int arr[100] = {7, 6, 9, 3, 1, 5, 2, 4};
	for (int i = 1; i <= 7; i++) {
		
	}
}

STEP 2:【用j变量来记录排好序列部分的最后一个位置】

接下来我们需要定义一个变量j来记录我们的合适位置,(这个j变量会拥有一个特点,什么特点呢?i刚刚已经写了是索引1,j的话就是索引0开始,所以一开始就是i-1),待排序的元素就是已经吸收了arr[i]变量key

#include<iostream>
using namespace std;
int main() {
	int arr[100] = {7, 3, 5, 5, 6, 0, 8};
	for (int i = 1; i <= 6; i++) {
		int key = arr[i];
		int j = i-1;
	}
}

STEP 3:【启动条件&启动后模拟值的交换过程】

书写我们的启动条件,如果当前这个元素前一个元素小,呢就往前放;写成代码就是if(arr[j] > key)

达成这个条件后我们开始比较操作;

操作的主要内容是:(1.交换元素位置 2.寻找合适位置(变量j的值能体现,因为在不断的变小,往前去找))

#include<iostream>
using namespace std;
int main() {
	int arr[100] = {7, 3, 5, 5, 6, 0, 8};
	for (int i = 1; i <= 6; i++) {
		int key = arr[i];
		int j = i-1;
		while (arr[j] > key) {
			arr[j+1] = arr[j];
			j--;
		}
    }
}

STEP 4:【回首掏,有几个情况需要考虑】

对于第三步,我们反思一下可能会出现几个问题:

  1. 【最后元素缺失】后面的值被前面的值覆盖,刚刚为key的位置元素没了,所以我们需要用arr[j + 1] = key;来给他补上
  2. 【历史最小元素,防止数组越界】加入出现了一个,“历史最小元素”,你要排到索引0这个位置,你不可能排到-1嘛,否则将会出现数组的索引错误。我们需要在判断条件上加上j >= 0
  3. 这个时候我再来解释一下key为什么会被用到,因为第一条问题【最后元素缺失】
#include<iostream>
using namespace std;
int main() {
	int arr[100] = {7, 3, 5, 5, 6, 0, 8};
	for (int i = 1; i <= 6; i++) {
		int key = arr[i];
		int j = i-1;
		while (j >= 0 && arr[j] > key) {
			arr[j+1] = arr[j];
			j--;
		}
		//while 结束之后key的位置就找到了
		arr[j + 1] = key;
		//但是此时,j+1会被覆盖
	}
}

至此排序完成,自己输出就好了!

标签:arr,元素,key,int,插入排序,位置,解读,索引,详细
From: https://www.cnblogs.com/bianchengxue/p/18372687

相关文章

  • 数据结构day03(栈 Stack 顺序栈、链式栈 )内含具体详细代码实现
    目录【1】栈 Stack1》栈的定义 2》顺序栈 2》链式栈 4》顺序栈的链式栈的区别【1】栈 Stack1》栈的定义栈:是只允许在一端进行插入或删除的线性表,首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。栈顶:线性表允许进行插入删除的一端......
  • 大模型是什么?(超详细)大模型教程入门到精通
    大模型的定义大模型是指具有数千万甚至数亿参数的深度学习模型。近年来,随着计算机技术和大数据的快速发展,深度学习在各个领域取得了显著的成果,如自然语言处理,图片生成,工业数字化等。为了提高模型的性能,研究者们不断尝试增加模型的参数数量,从而诞生了大模型这一概念。大模......
  • 基于SpringBoot+Vue+uniapp的钢材销售管理系统的详细设计和实现(源码+lw+部署文档+讲
    文章目录前言详细视频演示具体实现截图技术栈后端框架SpringBoot前端框架Vue持久层框架MyBaitsPlus系统测试系统测试目的系统功能测试系统测试结论为什么选择我代码参考数据库参考源码获取前言......
  • 基于SpringBoot+Vue+uniapp的大学生二手闲置物品置换交易管理系统的详细设计和实现(源
    文章目录前言详细视频演示具体实现截图技术栈后端框架SpringBoot前端框架Vue持久层框架MyBaitsPlus系统测试系统测试目的系统功能测试系统测试结论为什么选择我代码参考数据库参考源码获取前言......
  • 【RTT-Studio】详细使用教程十三:UART的DMA 接收及轮询发送
    文章目录一、简介二、RTT配置三、使用信号量接收四、使用消息队列接收五、测试验证一、简介  串口是指数据一位一位地顺序传送,其特点是通讯线路简单,只要一对传输线就可以实现双向通信(可以直接利用电话线作为传输线),从而大大降低了成本,特别适用于远距离通信,但传送速......
  • Office 2010 详细安装教程
    Office2010引入了新的文件格式,改善了用户界面,并提供了64位版本,以提高性能和支持更大的数据集。此外,Office2010还包括了在线协作功能,允许用户从不同地点和设备上共同工作,以及新的SmartArt图形和背景移除工具等功能,以提高办公效率和文档的专业外观。 安装包:百度网盘请输入......
  • 目标追踪 ByteTrack 算法详细流程分析
    原理介绍ByteTrack是字节跳动与2021年10月份公开的一个全新的多目标跟踪算法,原论文是《ByteTrack:Multi-ObjectTrackingbyAssociatingEveryDetectionBox》。ByteTrak的MOTA和FPS等指标上都实现了较好的性能,要优于现有的大多数MOT(多目标追踪)算法。github地址:https://git......
  • 机器学习线性回归算法——原理+python详细代码解析(sklearn)
    线性回归算法作为经典的机器学习算法之一,拥有极为广泛的应用范围,深受业界人士的青睐。该算法主要用于研究分析响应变量如何受到特征变量的线性影响。其通过构建回归方程,借助各特征变量对响应变量进行拟合,并且能够利用回归方程进行预测。鉴于线性回归算法较为基础、简单,所以比较......
  • AVL树、2-3-4树、红黑树节点增加删除原理(详细说明)
    AVL树与红黑树引入:BST(二叉查找树)在插入的时候会导致倾斜,不同的插入顺序会导致树的高度不一样,树的高度直接影响到树的查找效率,最坏的情况就是所有节点就在一条斜线上,导致树的高度为N。平衡二叉树(BalancedBST)在插入和删除的时候,会通过旋转将高度保持在Logn。删除节点:   ......
  • C语言编译预处理详细易懂版
    C语言允许在源程序中包含编译预处理命令,他们以"#"开头,包括宏定义、文件包含和条件编译。本博客主要详细介绍宏定义、文件包含和条件编译。一、宏定义1、无参数的宏定义是指用一个指定的标识符来代表一个字符串,一般格式如下:#define 宏名 字符串说明:①#表示预处理命......