Python算法——插入排序
插入排序(Insertion Sort)是一种简单但有效的排序算法,它的基本思想是将数组分成已排序和未排序两部分,然后逐一将未排序部分的元素插入到已排序部分的正确位置。插入排序通常比冒泡排序和选择排序更高效,特别适用于对部分有序的数组进行排序。本文将详细介绍插入排序的工作原理和Python实现。
插入排序的工作原理
插入排序的基本思想是将数组分成两部分:已排序部分和未排序部分。在开始时,已排序部分只包含数组的第一个元素,而未排序部分包含剩余的元素。算法的工作过程如下:
- 从未排序部分选择一个元素,将其插入到已排序部分的正确位置。
- 重复上述步骤,直到未排序部分为空。
插入排序的核心思想是每一步将一个元素插入到已排序部分,并确保已排序部分仍然保持有序。这一过程逐渐扩大已排序部分,缩小未排序部分,直到整个数组有序。
下面是一个示例,演示插入排序的过程。我们以升序排序为例:
原始数组:[12, 11, 13, 5, 6]
- 第一步:已排序部分 [12],未排序部分 [11, 13, 5, 6],将 11 插入已排序部分。
- 第二步:已排序部分 [11, 12],未排序部分 [13, 5, 6],将 13 插入已排序部分。
- 第三步:已排序部分 [11, 12, 13],未排序部分 [5, 6],将 5 插入已排序部分。
- c第四步:已排序部分 [5, 11, 12, 13],未排序部分 [6],将 6 插入已排序部分。
Python实现插入排序
下面是Python中的插入排序实现:
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = key
- arr 是待排序的数组。
- 外层循环 for i in range(1, len(arr)) 用于遍历未排序部分的元素。
- 内层循环 while j >= 0 and key < arr[j] 用于找到元素的正确位置。
- key 是当前待插入的元素,将它插入到已排序部分的正确位置。
示例代码
下面是一个使用Python进行插入排序的示例代码:
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = key# 测试排序
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("排序后的数组:", arr)
时间复杂度
插入排序的时间复杂度为 O(n^2),其中 n 是数组的长度。尽管插入排序不如高级排序算法(如快速排序和归并排序)高效,但它在小型数据集上表现良好,尤其在数组部分有序的情况下。
总之,插入排序是一种简单但有效的排序算法,通过将元素逐一插入到已排序部分,实现了排序数组的目标。了解插入排序有助于理解排序算法的基本原理,并为选择适当的排序算法提供了基础。
相关文章:
Python算法——插入排序
插入排序(Insertion Sort)是一种简单但有效的排序算法,它的基本思想是将数组分成已排序和未排序两部分,然后逐一将未排序部分的元素插入到已排序部分的正确位置。插入排序通常比冒泡排序和选择排序更高效,特别适用于对…...
Java21新特性
目录 一、Java21新特性 1、字符串模版 2、scoped values 3、record pattern 4、switch格式匹配 5、可以在switch中使用when 6、Unnamed Classes and Instance Main Methods 7、Structured Concurrency 一、Java21新特性 1、字符串模版 字符串模版可以让开发者更简洁的…...
4 Tensorflow图像识别模型——数据预处理
上一篇:3 tensorflow构建模型详解-CSDN博客 本篇开始介绍识别猫狗图片的模型,内容较多,会分为多个章节介绍。模型构建还是和之前一样的流程: 数据集准备数据预处理创建模型设置损失函数和优化器训练模型 本篇先介绍数据集准备&am…...
SpringBoot整合RabbitMQ学习笔记
SpringBoot整合RabbitMQ学习笔记 以下三种类型的消息,生产者和消费者需各自启动一个服务,模拟生产者服务发送消息,消费者服务监听消息,分布式开发。 一 Fanout类型信息 . RabbitMQ创建交换机和队列 在RabbitMQ控制台,新…...
在校园跑腿系统小程序中,如何设计高效的实时通知与消息推送系统?
1. 选择合适的消息推送服务 在校园跑腿系统小程序中,选择一个适合的消息推送服务。例如,使用WebSocket技术、Firebase Cloud Messaging (FCM)、或第三方推送服务如Pusher或OneSignal等。注册并获取相关的API密钥或访问令牌。 2. 集成服务到小程序后端…...
求极限Lim x->0 (x-sinx)*e-²x / (1-x)⅓
题目如下: 解题思路: 这题运用了无穷小替换、洛必达法则、求导法则 具体解题思路如下: 1、首先带入x趋近于0,可以得到(0*1)/0,所以可以把e的-x的平方沈略掉 然后根据无穷小替换,利用t趋近于0时…...
JavaScript数据类型详细解析与代码实例
JavaScript是一种弱类型动态语言,数据类型分为原始类型和对象类型。 原始类型 原始类型包括:数字、字符串、布尔值和undefined、null。 数字 JavaScript中的数字类型包括整数和浮点数,可以进行基本的数学运算。 var num1 10; // 整数 v…...
.NET Framework中自带的泛型委托Func
Func<>是.NET Framework中自带的泛型委托,可以接收一个或多个输入参数,并且有返回值,和Action类似,.NET基类库也提供了多达16个输入参数的Func委托,输出参数只有1个。 1、Func泛型委托 .NET Framework为我们提…...
深入理解JVM虚拟机第十七篇:虚拟机栈中栈帧的内部结构
大神链接:作者有幸结识技术大神孙哥为好友,获益匪浅。现在把孙哥视频分享给大家。 孙哥链接:孙哥个人主页 作者简介:一个颜值99分,只比孙哥差一点的程序员 本专栏简介:话不多说,让我们一起干翻JavaScript 本文章简介:话不多说,让我们讲清楚虚拟机栈存储结构和运行原理…...
uniapp中地图定位功能实现的几种方案
1.uniapp自带uni.getLocation uni.getLocation(options) getlocation | uni-app官网 实现思路:uni.getLocation获取经纬度后调用接口获取城市名 优点:方便快捷,直接调用 缺点:关闭定位后延时很久,无法控制定位延迟…...
JS功能实现
目录 轮播图移动端轮播图按下回车发表评论tab栏切换全选按钮 轮播图 <style>* {box-sizing: border-box;}.slider {width: 560px;height: 400px;overflow: hidden;}.slider-wrapper {width: 100%;height: 320px;}.slider-wrapper img {width: 100%;height: 100%;display:…...
connect-history-api-fallback原理
connect-history-api-fallback是一个用于处理前端路由的中间件,它的原理是在服务器接收到请求时,检查请求的路径是否匹配到静态文件(如HTML、CSS、JS等),如果不匹配,则将请求重定向到前端的入口文件&#x…...
Android ConstraintLayout分组堆叠圆角ShapeableImageView
Android ConstraintLayout分组堆叠圆角ShapeableImageView <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"…...
Docker Stack部署应用详解+Tomcat项目部署详细实战
Docker Stack 部署应用 概述 单机模式下,可以使用 Docker Compose 来编排多个服务。Docker Swarm 只能实现对单个服务的简单部署。而Docker Stack 只需对已有的 docker-compose.yml 配置文件稍加改造就可以完成 Docker 集群环境下的多服务编排。 stack是一组共享…...
Compose-Multiplatform在Android和iOS上的实践
本文字数:4680字 预计阅读时间:30分钟 01 简介 之前我们探讨过KMM,即Kotlin Multiplatform Mobile,是Kotlin发布的移动端跨平台框架。当时的结论是KMM提倡将共有的逻辑部分抽出,由KMM封装成Android(Kotlin/JVM)的aar和…...
XXL-JOB 默认 accessToken 身份绕过导致 RCE
文章目录 0x01 漏洞介绍0x02 影响版本0x03 环境搭建0x04 漏洞复现第一步 访问页面返回报错信息第二步 执行POC,进行反弹shell第三步 获取shell0x05 修复建议摘抄免责声明0x01 漏洞介绍 XXL-JOB 是一款开源的分布式任务调度平台,用于实现大规模任务的调度和执行。 XXL-JOB 默…...
7 库函数之复位和时钟设置(RCC)所有函数的介绍及使用
7 库函数之复位和时钟设置(RCC)所有函数的介绍及使用的介绍及使用 1. 图片有格式二、RCC库函数固件库函数预览2.1 函数RCC_DeInit2.2 函数RCC_HSEConfig2.3 函数RCC_WaitForHSEStartUp2.4 函数RCC_AdjustHSICalibrationValue2.5 函数RCC_HSICmd2.6 函数RCC_PLLConfig2.7 函数…...
第十七节——指令
一、概念 在Vue.js中,指令(Directives)是一种特殊的语法,用于为HTML元素添加特定的行为和功能。指令以v-作为前缀,通过在HTML标签中使用这些指令来操作DOM,修改元素的属性、样式或行为。 Vue.js提供了一组…...
优雅的 Dockerfile 是怎样炼成的?
Docker 简介 目前,Docker 主要有两个形态:Docker Desktop 和 Docker Engine。 Docker Desktop 是专门针对个人使用而设计的,支持 Mac(已支持arm架构的M系芯片) 和 Windows 快速安装,具有直观的图形界面&a…...
2023-2024 中国科学引文数据库来源期刊列表(CSCD)
文章目录 CSCD来源期刊遴选报告2023-2024 中国科学引文数据库来源期刊列表(CSCD) CSCD来源期刊遴选报告 2023-2024 中国科学引文数据库来源期刊列表(CSCD)...
MiniCPM-V-2_6AR应用赋能:手机摄像头取景框实时图文叠加说明
MiniCPM-V-2_6AR应用赋能:手机摄像头取景框实时图文叠加说明 1. 引言:当手机摄像头"学会思考" 想象一下这样的场景:你正在旅游景点,打开手机摄像头对准一座古建筑,屏幕上不仅显示实时画面,还自…...
[c++] STL概括
STL 是 C 标准库的核心,包含容器、迭代器、算法、函数对象四大组件。对于 OI 竞赛,熟练掌握 STL 可以大幅减少代码量、降低调试难度,是提升代码效率和准确率的关键。  一、常用容器(Container) 1. 序列容器…...
免费AI创作+零跳转!影刀6.0在百家号当前页全自动发文
免费AI创作零跳转!影刀6.0在百家号当前页全自动发文百家号创作者的福音来啦🥳人已经坐在百家号创作页面里了不用自己费脑想标题、写正文,影刀RPA直接调用免费AI大模型,一键搞定爆款创作不用切页、不用手动输入,AI自动贴…...
黑客马拉松利器:OpenClaw+SecGPT-14B快速构建安全PoC
黑客马拉松利器:OpenClawSecGPT-14B快速构建安全PoC 1. 缘起:当安全专家遇上自动化助手 去年参加某次网络安全竞赛时,我遇到了一个典型痛点:在48小时的黑客马拉松中,团队需要快速验证多个漏洞猜想,但手动…...
5步搞定Live Avatar数字人模型:阿里开源项目快速体验指南
5步搞定Live Avatar数字人模型:阿里开源项目快速体验指南 1. 数字人技术新体验 想象一下,你只需要一张照片和一段语音,就能让照片里的人"活"过来,对着镜头自然地说话、微笑、做表情。这不是科幻电影里的场景ÿ…...
自我即自感:一种极简存在论(四篇)
第一篇:自我即自感:一种极简存在论我们早已知道我们总是知道“我是我”。这不是谁告诉我们的,也不是推理出来的。从最原初的体验开始,我们就已经知道:正在感受的这个,就是我。这个“知道”不是反思。你不必…...
CAT使用教程
CAT(Cisco Auditing Tool)是一款专门用于审计Cisco网络设备安全性的工具,主要功能是对Cisco路由器、交换机等设备进行弱口令检测和漏洞扫描。其核心作用是帮助网络安全人员识别Cisco设备中存在的安全隐患,如默认或弱社区字符串&am…...
TurboDiffusion保姆级教程:基于Wan2.1/Wan2.2的AI视频生成快速上手
TurboDiffusion保姆级教程:基于Wan2.1/Wan2.2的AI视频生成快速上手 1. 引言 1.1 为什么选择TurboDiffusion 想象一下,你只需要输入一段文字描述,就能在几秒钟内生成一段高质量的视频。这不是科幻电影里的场景,而是TurboDiffusi…...
CC324条提示词意外泄露——第31条让我出了一身冷汗
324条提示词意外泄露——第31条让我出了一身冷汗 原创 硅谷Alan Walker 硅谷Alan Walker 嘉妍Kea 2026年4月2日 02:47 美国 22人 在小说阅读器中沉浸阅读 当 AI 可以代替你发 Slack、fork 自己,人与 AI 的边界在哪里? src/constants/prompts.ts 57…...
音乐格式自由革命:NCMDump终极指南让你轻松解锁网易云加密音乐
音乐格式自由革命:NCMDump终极指南让你轻松解锁网易云加密音乐 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 还在为网易云音乐下载的歌曲只能在特定客户端播放而烦恼吗?你是否曾经因为NCM格式的限制而无法在…...
