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

Python算法——插入排序

插入排序(Insertion Sort)是一种简单但有效的排序算法,它的基本思想是将数组分成已排序和未排序两部分,然后逐一将未排序部分的元素插入到已排序部分的正确位置。插入排序通常比冒泡排序和选择排序更高效,特别适用于对部分有序的数组进行排序。本文将详细介绍插入排序的工作原理和Python实现。

插入排序的工作原理

插入排序的基本思想是将数组分成两部分:已排序部分和未排序部分。在开始时,已排序部分只包含数组的第一个元素,而未排序部分包含剩余的元素。算法的工作过程如下:

  1. 从未排序部分选择一个元素,将其插入到已排序部分的正确位置。
  2. 重复上述步骤,直到未排序部分为空。
    插入排序的核心思想是每一步将一个元素插入到已排序部分,并确保已排序部分仍然保持有序。这一过程逐渐扩大已排序部分,缩小未排序部分,直到整个数组有序。

下面是一个示例,演示插入排序的过程。我们以升序排序为例:

原始数组:[12, 11, 13, 5, 6]

  1. 第一步:已排序部分 [12],未排序部分 [11, 13, 5, 6],将 11 插入已排序部分。
  2. 第二步:已排序部分 [11, 12],未排序部分 [13, 5, 6],将 13 插入已排序部分。
  3. 第三步:已排序部分 [11, 12, 13],未排序部分 [5, 6],将 5 插入已排序部分。
  4. 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算法——插入排序

插入排序&#xff08;Insertion Sort&#xff09;是一种简单但有效的排序算法&#xff0c;它的基本思想是将数组分成已排序和未排序两部分&#xff0c;然后逐一将未排序部分的元素插入到已排序部分的正确位置。插入排序通常比冒泡排序和选择排序更高效&#xff0c;特别适用于对…...

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图像识别模型——数据预处理

上一篇&#xff1a;3 tensorflow构建模型详解-CSDN博客 本篇开始介绍识别猫狗图片的模型&#xff0c;内容较多&#xff0c;会分为多个章节介绍。模型构建还是和之前一样的流程&#xff1a; 数据集准备数据预处理创建模型设置损失函数和优化器训练模型 本篇先介绍数据集准备&am…...

SpringBoot整合RabbitMQ学习笔记

SpringBoot整合RabbitMQ学习笔记 以下三种类型的消息&#xff0c;生产者和消费者需各自启动一个服务&#xff0c;模拟生产者服务发送消息&#xff0c;消费者服务监听消息&#xff0c;分布式开发。 一 Fanout类型信息 . RabbitMQ创建交换机和队列 在RabbitMQ控制台&#xff0c;新…...

在校园跑腿系统小程序中,如何设计高效的实时通知与消息推送系统?

1. 选择合适的消息推送服务 在校园跑腿系统小程序中&#xff0c;选择一个适合的消息推送服务。例如&#xff0c;使用WebSocket技术、Firebase Cloud Messaging (FCM)、或第三方推送服务如Pusher或OneSignal等。注册并获取相关的API密钥或访问令牌。 2. 集成服务到小程序后端…...

求极限Lim x->0 (x-sinx)*e-²x / (1-x)⅓

题目如下&#xff1a; 解题思路: 这题运用了无穷小替换、洛必达法则、求导法则 具体解题思路如下: 1、首先带入x趋近于0&#xff0c;可以得到&#xff08;0*1&#xff09;/0&#xff0c;所以可以把e的-x的平方沈略掉 然后根据无穷小替换&#xff0c;利用t趋近于0时&#xf…...

JavaScript数据类型详细解析与代码实例

JavaScript是一种弱类型动态语言&#xff0c;数据类型分为原始类型和对象类型。 原始类型 原始类型包括&#xff1a;数字、字符串、布尔值和undefined、null。 数字 JavaScript中的数字类型包括整数和浮点数&#xff0c;可以进行基本的数学运算。 var num1 10; // 整数 v…...

.NET Framework中自带的泛型委托Func

Func<>是.NET Framework中自带的泛型委托&#xff0c;可以接收一个或多个输入参数&#xff0c;并且有返回值&#xff0c;和Action类似&#xff0c;.NET基类库也提供了多达16个输入参数的Func委托&#xff0c;输出参数只有1个。 1、Func泛型委托 .NET Framework为我们提…...

深入理解JVM虚拟机第十七篇:虚拟机栈中栈帧的内部结构

大神链接:作者有幸结识技术大神孙哥为好友,获益匪浅。现在把孙哥视频分享给大家。 孙哥链接:孙哥个人主页 作者简介:一个颜值99分,只比孙哥差一点的程序员 本专栏简介:话不多说,让我们一起干翻JavaScript 本文章简介:话不多说,让我们讲清楚虚拟机栈存储结构和运行原理…...

uniapp中地图定位功能实现的几种方案

1.uniapp自带uni.getLocation uni.getLocation(options) getlocation | uni-app官网 实现思路&#xff1a;uni.getLocation获取经纬度后调用接口获取城市名 优点&#xff1a;方便快捷&#xff0c;直接调用 缺点&#xff1a;关闭定位后延时很久&#xff0c;无法控制定位延迟…...

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是一个用于处理前端路由的中间件&#xff0c;它的原理是在服务器接收到请求时&#xff0c;检查请求的路径是否匹配到静态文件&#xff08;如HTML、CSS、JS等&#xff09;&#xff0c;如果不匹配&#xff0c;则将请求重定向到前端的入口文件&#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 部署应用 概述 单机模式下&#xff0c;可以使用 Docker Compose 来编排多个服务。Docker Swarm 只能实现对单个服务的简单部署。而Docker Stack 只需对已有的 docker-compose.yml 配置文件稍加改造就可以完成 Docker 集群环境下的多服务编排。 stack是一组共享…...

Compose-Multiplatform在Android和iOS上的实践

本文字数&#xff1a;4680字 预计阅读时间&#xff1a;30分钟 01 简介 之前我们探讨过KMM&#xff0c;即Kotlin Multiplatform Mobile&#xff0c;是Kotlin发布的移动端跨平台框架。当时的结论是KMM提倡将共有的逻辑部分抽出&#xff0c;由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中&#xff0c;指令&#xff08;Directives&#xff09;是一种特殊的语法&#xff0c;用于为HTML元素添加特定的行为和功能。指令以v-作为前缀&#xff0c;通过在HTML标签中使用这些指令来操作DOM&#xff0c;修改元素的属性、样式或行为。 Vue.js提供了一组…...

优雅的 Dockerfile 是怎样炼成的?

Docker 简介 目前&#xff0c;Docker 主要有两个形态&#xff1a;Docker Desktop 和 Docker Engine。 Docker Desktop 是专门针对个人使用而设计的&#xff0c;支持 Mac&#xff08;已支持arm架构的M系芯片&#xff09; 和 Windows 快速安装&#xff0c;具有直观的图形界面&a…...

2023-2024 中国科学引文数据库来源期刊列表(CSCD)

文章目录 CSCD来源期刊遴选报告2023-2024 中国科学引文数据库来源期刊列表&#xff08;CSCD&#xff09; CSCD来源期刊遴选报告 2023-2024 中国科学引文数据库来源期刊列表&#xff08;CSCD&#xff09;...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

电脑桌面太单调,用Python写一个桌面小宠物应用。

下面是一个使用Python创建的简单桌面小宠物应用。这个小宠物会在桌面上游荡&#xff0c;可以响应鼠标点击&#xff0c;并且有简单的动画效果。 import tkinter as tk import random import time from PIL import Image, ImageTk import os import sysclass DesktopPet:def __i…...

MyBatis-Plus 常用条件构造方法

1.常用条件方法 方法 说明eq等于 ne不等于 <>gt大于 >ge大于等于 >lt小于 <le小于等于 <betweenBETWEEN 值1 AND 值2notBetweenNOT BETWEEN 值1 AND 值2likeLIKE %值%notLikeNOT LIKE %值%likeLeftLIKE %值likeRightLIKE 值%isNull字段 IS NULLisNotNull字段…...

解决MybatisPlus使用Druid1.2.11连接池查询PG数据库报Merge sql error的一种办法

目录 前言 一、问题重现 1、环境说明 2、重现步骤 3、错误信息 二、关于LATERAL 1、Lateral作用场景 2、在四至场景中使用 三、问题解决之道 1、源码追踪 2、关闭sql合并 3、改写处理SQL 四、总结 前言 在博客&#xff1a;【写在创作纪念日】基于SpringBoot和PostG…...

LeetCode - 148. 排序链表

目录 题目 思路 基本情况检查 复杂度分析 执行示例 读者可能出的错误 正确的写法 题目 148. 排序链表 - 力扣&#xff08;LeetCode&#xff09; 思路 链表归并排序采用"分治"的策略&#xff0c;主要分为三个步骤&#xff1a; 分割&#xff1a;将链表从中间…...