排序小白必读:掌握插入排序的基本原理
一、插入排序是什么?
它是一种简单直观的排序算法。类似于整理扑克牌,想象你手上有一堆未排序的牌,你将它们逐个插入已排序的牌堆中的正确位置。拿起一张牌,与已排序的牌进行比较,将它插入到合适的位置。重复这个过程,直到所有牌都插入到正确的位置。这样,你逐步将牌从小到大有序排列起来。插入排序适用于小规模数据或部分有序的情况。
二、原理
算法步骤:
- 从第一个元素开始,认为该元素已经是一个有序序列。
- 取出下一个元素,在已排序的序列中从后向前遍历。
- 如果已排序的元素大于新元素,将已排序元素向右移动一个位置,直到找到小于或等于新元素的位置。
- 将新元素插入到找到的位置。
- 重复步骤2-4,直到所有元素都被插入到正确的位置。
下面是一个示例,说明了插入排序如何对数组 [7, 2, 4, 1, 5] 进行排序:
初始序列: [7, 2, 4, 1, 5]
- 第一轮迭代:已排序序列为 [7],将下一个元素 2 插入到正确的位置,得到 [2, 7, 4, 1, 5]。
- 第二轮迭代:已排序序列为 [2, 7],将下一个元素 4 插入到正确的位置,得到 [2, 4, 7, 1, 5]。
- 第三轮迭代:已排序序列为 [2, 4, 7],将下一个元素 1 插入到正确的位置,得到 [1, 2, 4, 7, 5]。
- 第四轮迭代:已排序序列为 [1, 2, 4, 7],将下一个元素 5 插入到正确的位置,得到 [1, 2, 4, 5, 7]。
最终排序结果为 [1, 2, 4, 5, 7]。
时间复杂度:
插入排序的平均时间复杂度为 O(n^2),其中 n 是要排序的元素个数。最好情况下,如果输入序列已经有序,时间复杂度可以达到 O(n)。但是,最坏情况下,如果输入序列是逆序的,时间复杂度将达到 O(n^2)。插入排序对于小规模的数据集或基本有序的数据集是一种简单且高效的排序算法。
空间复杂度:
插入排序的空间复杂度为 O(1),它在原地进行排序,只需要少量的额外空间用于存储临时变量。
三、生活中的应用
- 整理书架:当你整理书架上的图书时,你可能希望按照作者的姓氏或书名的字母顺序对它们进行排序。你可以将每本新书插入到已经按顺序排列的书堆中的正确位置,从而完成整理工作。
- 安排日程:当你有很多待办事项或约会时,你可以使用插入排序的思想来安排它们的顺序。你可以根据优先级或时间的顺序,逐个将待办事项插入到已经安排好的日程中的正确位置。
- 积木排序:有一堆不同大小的积木,你想要将它们按照从小到大的顺序排列。你先拿起一块放在最前面,再拿起第二块,并跟第一块做比较,如果比第一块小,那就放左边,如果比第一块放右边,你再拿起第三块积木,重复前面的过程,根据比较大小的方式,将其放在合适的位置,以此类推,就可以将一堆积木从小到达进行排序。
用一句话总结插入排序
插入排序是一种通过逐个比较和插入元素的方法,将数据按照一定顺序逐步排列的排序算法。
四、考考你
- 你正在整理一堆杂乱的照片,希望按照拍摄日期将它们有序地放入相册中,你会如何运用插入排序的思想?
- 假设你有一箱各式各样的食材,你想要按照保质期的先后顺序进行整理,你会如何使用插入排序的思想将它们有序地放置?
- 你正在准备一个晚会的座位安排,来宾们的姓名按照字母顺序已经排好,现在有一个新的来宾需要加入,请问你将如何使用插入排序的思想来安排他的座位?
- 你正在整理书籍,希望按照作者的姓氏将它们放入书架上的正确位置,你会如何应用插入排序的思想?
- 假设你有一堆不同尺寸的衣服需要整理,你打算使用插入排序的思想将它们按照尺寸从小到大排列,该如何操作?
你在生活中有什么地方用到插入排序吗?欢迎你把你的故事分享出来。
相关文章:
排序小白必读:掌握插入排序的基本原理
一、插入排序是什么? 它是一种简单直观的排序算法。类似于整理扑克牌,想象你手上有一堆未排序的牌,你将它们逐个插入已排序的牌堆中的正确位置。拿起一张牌,与已排序的牌进行比较,将它插入到合适的位置。重复这个过程…...
html常见兼容性问题
1. png24位的图片在iE6浏览器上出现背景 解决方案:做成PNG8,也可以引用一段脚本处理. 2. 浏览器默认的margin和padding不同 解决方案:加一个全局的 *{margin:0;padding:0;} 来统一。 3. IE6双边距bug:在IE6下,如果对…...
Docker实战:docker compose 搭建Redis
1、配置文件准备 redis 配置文件:https://pan.baidu.com/s/1YreI9_1BMh8XRyyV9BH08g2、创建目录并赋权 mkdir -p /home/docker/redis/data /home/redis/logs /home/redis/conf chmod -R 777 /home/docker/redis/data* chmod -R 777 /home/docker/redis/logs*3、re…...

Debian11 Crontab
Crontab用户命令 可执行文件 crontab命令的可执行文件在哪儿? $ which -a crontab /usr/bin/crontab /bin/crontabcrontab命令的可执行文件有2个:/usr/bin/crontab 和 /bin/crontab $ diff /usr/bin/crontab /bin/crontab $diff 发现这两个文件并无区…...

css 文字排版-平铺
序: 1、表格的宽度要有!!!!! 2、容器不能是display:inline 3、扩展---》node全栈框架 代码 text-align-last: justify; width: 70px; display: inline-block; 主要是用于表单左侧文字排序!...

把握潮流:服装定制小程序的发展与趋势
随着互联网的快速发展,小程序成为了人们生活中不可或缺的一部分。尤其在服装行业,定制化已经成为了一种趋势。为了满足消费者个性化的需求,服装定制小程序应运而生。 为了方便开发者的设计和制作,我们可以使用第三方的制作平台来创…...

Go 安装配置
介绍Ubuntu20.04 安装和配置Go 可以参考官网的这个为 Go 开发配置Visual Studio Code - Go on Azure | Microsoft Learn 1.安装Go 去这个地方下载Go https://go.dev/doc/install 如果之前安装过,可以参考这个(没有可以忽略) 下载完成后执…...

镜像底层原理详解和基于Docker file创建镜像
目录 一、镜像底层原理 1.联合文件系统(UnionFS) 2.镜像加载原理 3.为什么Docker里的centos的大小才200M? 二、Dockerfile 1.简介 2.Dockerfile操作常用命令 (1)FORM 镜像 (2)MAINTAINER 维护人信息 (3&…...

k8s扩缩容与滚动更新
使用kubectl run创建应用 kubectl run kubernetes-bootcamp \> --imagedocker.io/jocatalin/kubernetes-bootcamp:v1 \> --port8080 端口暴露出去 kubectl expose pod kubernetes-bootcamp --type"NodePort" --port 8080 使用kubectl create创建应用 kubect…...
4.小程序的运行机制
启动过程 把小程序的代码包下载到本地解析app.json全局配置文件执行app.js小程序入口文件,调用App()创建小程序的实例渲染小程序首页小程序启动完成 页面渲染过程 加载解析页面的.json配置文件加载页面.wxml模板和.scss样式执行页面的.ts文件,调用Pag…...

基于 Vercel TiDB Serverless 的 chatbot
作者: shiyuhang0 原文来源: https://tidb.net/blog/7b5fcdc9 # 前言 TiDB Serverless 去年就有和 Vercel 的集成了,同时还有一个 bookstore template 方便大家体验。但个人感觉 bookstore 不够炫酷,借 2023 TiDB hackthon 的…...

Android 多渠道打包及VasDolly使用
目录 1.添加productFlavors的配置buildConfigFieldmanifestPlaceholdersresValue 2.设置apk文件的名称,便于识别3.添加vasdolly、添加gradle脚本(windows) 作用:一次性可以打多个apk包,名字、包名、logo等可以不相同。…...

LeetCode 42题:接雨水
题目 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,…...
spring boot 提示:程序包不存在,解决方法总结
背景: 之前出现过这样的问题,打包安装父项目就好了,今天改了一下代码,重新编译的时候,又出现了这样的情况,决定深度挖掘一下这里面的问题 spring boot 提示:程序包不存在,解决方法总…...

docker项目实战
1、使用mysql:5.6和 owncloud 镜像,构建一个个人网盘 1)拉取mysql:5.6和owncloud镜像 [rootmaster ~]# docker pull mysql:5.6 5.6: Pulling from library/mysql 35b2232c987e: Pull complete fc55c00e48f2: Pull complete 0030405130e3: Pull compl…...

银行客户关系管理系统springboot财务金融进销存java jsp源代码
本项目为前几天收费帮学妹做的一个项目,Java EE JSP项目,在工作环境中基本使用不到,但是很多学校把这个当作编程入门的项目来做,故分享出本项目供初学者参考。 一、项目描述 银行客户关系管理系统springboot 系统有1权限&#x…...
Maven 插件 maven-antrun-plugin 执行 ant 脚本
Ant 相信大家都不陌生,你可以把它理解为使用 xml 格式描述的一系列命令处理工具。它是一种基于Java的build工具。理论上来说,它有些类似于(Unix)C中的make、有些类似于基于shell命令编写的sh脚本文件。Ant 用 Java 的类来扩展。&a…...

【仿写框架之仿写Tomact】四、封装HttpRequest对象(属性映射http请求报文)、HttpResponse对象(属性映射http响应报文)
文章目录 1、创建HttpRequest对象2、创建HttpResponse对象 1、创建HttpRequest对象 HttpRequest对象中的属性与HTTP协议中的内容对应,用于后序servlet从request中获取请求中的参数。 参照http请求报文: import java.io.BufferedReader; import java…...
LeetCode 41题:缺失的第一个正数
目录 题目 思路 代码 题目 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1: 输入:nums [1,2,0] 输出:3示例 2ÿ…...
学单片机有什么用?
单片机简而言之就是一个小计算机系统,它已经应用到了我们生活中的方方面面。单片机比专用处理器适合应用于嵌入式系统,因此它得到了多的应用,事实上单片机是世界上数量多的计算机。 现代人类生活中所用的几乎每件电子和机械产品中都会集成有单…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...