当前位置: 首页 > news >正文

排序小白必读:掌握插入排序的基本原理

一、插入排序是什么?

它是一种简单直观的排序算法。类似于整理扑克牌,想象你手上有一堆未排序的牌,你将它们逐个插入已排序的牌堆中的正确位置。拿起一张牌,与已排序的牌进行比较,将它插入到合适的位置。重复这个过程,直到所有牌都插入到正确的位置。这样,你逐步将牌从小到大有序排列起来。插入排序适用于小规模数据或部分有序的情况。

二、原理

算法步骤:

  1. 从第一个元素开始,认为该元素已经是一个有序序列。
  2. 取出下一个元素,在已排序的序列中从后向前遍历。
  3. 如果已排序的元素大于新元素,将已排序元素向右移动一个位置,直到找到小于或等于新元素的位置。
  4. 将新元素插入到找到的位置。
  5. 重复步骤2-4,直到所有元素都被插入到正确的位置。
    下面是一个示例,说明了插入排序如何对数组 [7, 2, 4, 1, 5] 进行排序:

初始序列: [7, 2, 4, 1, 5]

  1. 第一轮迭代:已排序序列为 [7],将下一个元素 2 插入到正确的位置,得到 [2, 7, 4, 1, 5]。
  2. 第二轮迭代:已排序序列为 [2, 7],将下一个元素 4 插入到正确的位置,得到 [2, 4, 7, 1, 5]。
  3. 第三轮迭代:已排序序列为 [2, 4, 7],将下一个元素 1 插入到正确的位置,得到 [1, 2, 4, 7, 5]。
  4. 第四轮迭代:已排序序列为 [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),它在原地进行排序,只需要少量的额外空间用于存储临时变量。

三、生活中的应用

  1. 整理书架:当你整理书架上的图书时,你可能希望按照作者的姓氏或书名的字母顺序对它们进行排序。你可以将每本新书插入到已经按顺序排列的书堆中的正确位置,从而完成整理工作。
  2. 安排日程:当你有很多待办事项或约会时,你可以使用插入排序的思想来安排它们的顺序。你可以根据优先级或时间的顺序,逐个将待办事项插入到已经安排好的日程中的正确位置。
  3. 积木排序:有一堆不同大小的积木,你想要将它们按照从小到大的顺序排列。你先拿起一块放在最前面,再拿起第二块,并跟第一块做比较,如果比第一块小,那就放左边,如果比第一块放右边,你再拿起第三块积木,重复前面的过程,根据比较大小的方式,将其放在合适的位置,以此类推,就可以将一堆积木从小到达进行排序。

用一句话总结插入排序
插入排序是一种通过逐个比较和插入元素的方法,将数据按照一定顺序逐步排列的排序算法。

四、考考你

  1. 你正在整理一堆杂乱的照片,希望按照拍摄日期将它们有序地放入相册中,你会如何运用插入排序的思想?
  2. 假设你有一箱各式各样的食材,你想要按照保质期的先后顺序进行整理,你会如何使用插入排序的思想将它们有序地放置?
  3. 你正在准备一个晚会的座位安排,来宾们的姓名按照字母顺序已经排好,现在有一个新的来宾需要加入,请问你将如何使用插入排序的思想来安排他的座位?
  4. 你正在整理书籍,希望按照作者的姓氏将它们放入书架上的正确位置,你会如何应用插入排序的思想?
  5. 假设你有一堆不同尺寸的衣服需要整理,你打算使用插入排序的思想将它们按照尺寸从小到大排列,该如何操作?

你在生活中有什么地方用到插入排序吗?欢迎你把你的故事分享出来。

相关文章:

排序小白必读:掌握插入排序的基本原理

一、插入排序是什么? 它是一种简单直观的排序算法。类似于整理扑克牌,想象你手上有一堆未排序的牌,你将它们逐个插入已排序的牌堆中的正确位置。拿起一张牌,与已排序的牌进行比较,将它插入到合适的位置。重复这个过程…...

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&#xff…...

学单片机有什么用?

单片机简而言之就是一个小计算机系统,它已经应用到了我们生活中的方方面面。单片机比专用处理器适合应用于嵌入式系统,因此它得到了多的应用,事实上单片机是世界上数量多的计算机。 现代人类生活中所用的几乎每件电子和机械产品中都会集成有单…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...