插入排序之C++实现
描述
插入排序是一种简单直观的排序算法。它的基本思想是将一个待排序的数据序列分为已排序和未排序两部分,每次从未排序序列中取出一个元素,然后将它插入到已排序序列的适当位置,直到所有元素都插入完毕,即完成排序。
实现思路
- 从第一个元素开始,将其视为已排序序列。
 - 取出未排序序列的第一个元素,并将它与已排序序列的元素逐个比较。
 - 如果找到一个已排序序列的元素大于待插入元素,将该元素后移一位。
 - 重复步骤3,直到找到一个已排序序列的元素小于或等于待插入元素。
 - 将待插入元素插入到这个位置。
 - 重复步骤2-5,直到未排序序列中的所有元素都被插入到已排序序列中。
 
图解

代码
#include <iostream>
#include <vector>using namespace std;void insertionSort(vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}int main() {vector<int> arr = {9, 5, 7, 1, 3};insertionSort(arr);cout << "插入排序 :" << endl;for (int num : arr) {cout << num << " ";}cout << endl;return 0;
}
 
输出结果:
 
时间复杂度
根据循环次数,插入排序的平均时间复杂度为O(n2),最好情况下为O(n),最坏情况下为O(n2)。
空间复杂度
插入排序的空间复杂度为O(1)。
技巧
- 在内层循环中,可以通过将待插入元素与已排序序列的最后一个元素进行比较,而不是逐个比较已排序序列的元素,以提高效率。
 - 可以使用二分查找来在已排序序列中找到待插入元素的插入位置,以进一步提高效率。
 
结论
坚持自己的梦想,即使没有翅膀也能飞翔。
相关文章:
插入排序之C++实现
描述 插入排序是一种简单直观的排序算法。它的基本思想是将一个待排序的数据序列分为已排序和未排序两部分,每次从未排序序列中取出一个元素,然后将它插入到已排序序列的适当位置,直到所有元素都插入完毕,即完成排序。 实现思路…...
Tomcat日志乱码了怎么处理?
【前言】 tomacat日志有三个地方,分别是Output(控制台)、Tomcat Localhost Log(tomcat本地日志)、Tomcat Catalina Log。 启动日志和大部分报错日志、普通日志都在output打印;有些错误日志,在Tomcat Localhost Log。 三个日志显示区,都可能…...
[node] Node.js的路由
[node] Node.js的路由 路由 & 路由解析路由信息的整合URL信息路由处理逻辑路由逻辑与URL信息的整合路由的使用 路由 & 路由解析 路由需要提供请求的 URL 和其他需要的 GET/POST 参数,随后路由需要根据这些数据来执行相应的代码。 因此,根据 HT…...
网络编程第三天作业
...
AIGC:大语言模型LLM的幻觉问题
引言 在使用ChatGPT或者其他大模型时,我们经常会遇到模型答非所问、知识错误、甚至自相矛盾的问题。 虽然大语言模型(LLMs)在各种下游任务中展示出了卓越的能力,在多个领域有广泛应用,但存在着幻觉的问题:…...
【C语言刷题每日一题#牛客网BC68】——X形图案
问题描述 思路分析 首先根据输入的描述,多组输入需要将scanf放在循环中来实现 #include<stdio.h> int main() {int a 0;while (scanf("%d", &a) ! EOF){} } 完成了输入之后,再来分析输出——输出的是一个由“*”组成的对称的X形…...
阻断血缘关系以及checkpoint文件清理
spark-sql读写同一张表,报错Cannot overwrite a path that is also being read from 1. 增加checkpoint,设置检查点阻断血缘关系 sparkSession.sparkContext.setCheckpointDir("/tmp/spark/job/OrderOnlineSparkJob")val oldOneIdTagSql s&…...
PHP代码审计之反序列化攻击链CVE-2019-6340漏洞研究
关键词 php 反序列化 cms Drupal CVE-2019-6340 DrupalKernel 前言 简简单单介绍下php的反序列化漏洞 php反序列化漏洞简单示例 来看一段简单的php反序列化示例 <?phpclass pingTest {public $ipAddress "127.0.0.1";public $isValid False;public $output…...
PyTorch之线性回归
1.定义: 回归分析是确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。线性回归是利用称为线性回归方程的最小二乘函数,对一个或多个自变量和因变量之间关系,进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参…...
SSTI模板注入基础(Flask+Jinja2)
文章目录 一、前置知识1.1 模板引擎1.2 渲染 二、SSTI模板注入2.1 原理2.2 沙箱逃逸沙箱逃逸payload讲解其他重要payload 2.3 过滤绕过点.被过滤下划线_被过滤单双引号 "被过滤中括号[]被过滤关键字被过滤 三、PasecaCTF-2019-Web-Flask SSTI参考文献 一、前置知识 1.1 模…...
React网页转换为pdf并下载|使用jspdf html2canvas
checkout 分支后突然报错,提示: Cant resolve jspdf in ... Cant resolve html2canvas in ... 解决方法很简单,重新 yarn install 就好了,至于为什么,我暂时也不知道,总之解决了。 思路来源: 先…...
EASYEXCEL导出表格(有标题、单元格合并)
EASYEXCEL导出表格(有标题、单元格合并) xlsx格式报表的导出,导出的数据存在父子关系,即相当于树形数据,有单元格合并和标题形式的要求,查阅了一些资料,总算是弄出来了,这里另写一个…...
pytest 断言异常
一、前置说明 在 pytest 中,断言异常是通过 pytest 内置的 pytest.raises 上下文管理器来实现的。通过使用 pytest.raises,可以捕获并断言代码中引发的异常。 二、操作步骤 1. 编写测试代码 atme/demos/demo_pytest_tutorials/test_pytest_raises.py import pytest# 示例…...
听GPT 讲Rust源代码--src/tools(22)
File: rust/src/tools/tidy/src/lib.rs rust/src/tools/tidy/src/lib.rs是Rust编译器源代码中tidy工具的实现文件之一。tidy工具是Rust项目中的一项静态检查工具,用于确保代码质量和一致性。 tidy工具主要有以下几个作用: 格式化代码:tidy工具…...
OD Linux发行版本
题目描述: Linux操作系统有多个发行版,distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联,例如Ubuntu基于Debian开发,而Mint又基于Ubuntu开发,那么我们认为Mint同Debian也存在关联。 发行版集是一个或多…...
华为端口隔离简单使用方法同vlan下控制个别电脑不给互通
必须得用access接口,hybrid口不行 dhcp enable interface Vlanif1 ip address 192.168.1.1 255.255.255.0 dhcp select interface interface MEth0/0/1 interface GigabitEthernet0/0/1 port link-type access port-isolate enable group 1 interface GigabitEther…...
DaVinci各版本安装指南
链接: https://pan.baidu.com/s/1g1kaXZxcw-etsJENiW2IUQ?pwd0531  #2024版 1.鼠标右击【DaVinci_Resolve_Studio_18.5(64bit)】压缩包(win11及以上系统需先点击“显示更多选项”)【解压到 DaVinci_Resolve_Studio_18.5(64bit)】。 2.打开解压后的文…...
【黑马甄选离线数仓day10_会员主题域开发_DWS和ADS层】
day10_会员主题域开发 会员主题_DWS和ADS层 DWS层开发 门店会员分类天表: 维度指标: 指标:新增注册会员数、累计注册会员数、新增消费会员数、累计消费会员数、新增复购会员数、累计复购会员数、活跃会员数、沉睡会员数、会员消费金额 维度: 时间维度(…...
OD 完美走位
题目描述: 在第一人称射击游戏中,玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动,从而完成走位。假设玩家每按动一次键盘,游戏人物会向某个方向移动一步,如果玩家在操作一定次数的键…...
SpringSecurity6 | 失败后的跳转
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏: MySQL学习 🥭本文内容: SpringSecurity6 | 失败后的跳转 📚个人知识库: Leo知识库,欢迎大家访问 学习…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
