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

python插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常使用in-place排序(即只需用到O(1)的额外空间的排序),因为在排序的过程中,会将元素一边移动,一边向前寻找插入位置。
下面是插入排序的详细描述:
1. **初始化**:将数组视作有序,从第一个元素开始,该元素可以认为已经被排序。
2. **比较与移动**:取出下一个元素,在已经排序的元素序列中从后向前扫描。
3. **插入**:如果该元素(已排序)大于新元素,将该元素移到下一位置,继续比较,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置后。
4. **重复**:重复步骤2和3,直到所有元素都被排序。
5. **结束**:当最后一个元素被插入到序列中时,整个排序过程结束。
插入排序的效率依赖于已经排序的元素的数量。如果数组已经是基本有序的,插入排序将非常高效。在最坏的情况下,即数组完全逆序,每个新元素都需要与已排序的元素依次比较并插入到最前面,此时插入排序的时间复杂度为O(n^2),其中n是数组的长度。
插入排序的优点是实现简单,对于小规模数据排序是有效的,特别是当输入数组基本有序时。但它的缺点是移动元素的次数较多,对于大规模数据排序效率较低。在实际应用中,它通常用作较小数据集的排序算法,或者作为其他排序算法(如快速排序)的辅助排序算法。

```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] = keyreturn arr# 测试
arr = [5, 2, 8, 3, 9, 1]
sorted_arr = insertion_sort(arr)
print(sorted_arr)
```

相关文章:

python插入排序

插入排序&#xff08;Insertion Sort&#xff09;是一种简单直观的排序算法。它的工作原理是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫描&#xff0c;找到相应位置并插入。插入排序在实现上&#xff0c;通常使用in-place排序&#xff0…...

怎么将营业执照图片转为excel表格?(批量合并识别技巧)

一、为何要将营业执照转为excel表格&#xff1f; 1、方便管理&#xff1a;将营业执照转为excel格式&#xff0c;可以方便地进行管理和整理&#xff0c;快速查找需要的信息。 2、数据处理&#xff1a;Excel可以提供丰富的计算和数据分析功能&#xff0c;转化为excel后方便数据…...

关于java数组Arrays类

关于java数组Arrays类 前面的文章中&#xff0c;我们了解了数组创建方法等&#xff0c;我们本篇文章来了解一下数组的方法类Arrays&#xff0c;有了这个类&#xff0c;我们在日常写代码的时候就不不用自己去手动创建方法了&#x1f600;。 Arrays类 数组的工具类java.util.A…...

LeetCode-58/709

1.最后一个单词的长度&#xff08;58&#xff09; 题目描述&#xff1a; 给你一个字符串 s&#xff0c;由若干单词组成&#xff0c;单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。 思路&…...

linux 流量监控

linux 流量监控 Linux 网络流量监控利器 iftop命令详解及实战 https://blog.csdn.net/qq_50247813/article/details/134164093 iftop命令详解 https://www.cnblogs.com/gaoyuechen/p/17300017.html 1 ubuntu如何查看流量监控 Ubuntu是一种非常流行的Linux发行版&#xff0c…...

AUTOSAR从入门到精通-漫谈autosar软件架构(八)

目录 前言 原理 AUTOSAR的方法论 AUTOSAR架构的优点 AUTOSAR 软件架构 1.应用层...

C#设计模式之单例模式

介绍 单例模式&#xff08;Singleton&#xff09;保证一个类仅有一个实例&#xff0c;并提供一个访问它的全局访问点。 单例模式的结构图如下所示&#xff1a; 使用单例模式的原因 对一些类来说&#xff0c;只有一个实例是很重要的。如何才能保证一个类只有一个实例并且这个…...

【源码预备】Calcite基础知识与概念:关系代数概念、查询优化、sql关键字执行顺序以及calcite基础概念

文章目录 一. 关系代数的基本知识二. 查询优化三. SQL语句的解析顺序1. FROM2. WHERE3. GROUP BY4. HAVING5. SELECT 四. Apache Calcite中的基本概念1. Adapter2. Calcite中的关系表达式2.1. 关系表达式例子2.2. 源码底层结构 3. Calcite的优化规则4. Calcite的Trait--算子物理…...

【Java 设计模式】23 种设计模式

文章目录 设计模式是什么计算机行业里的设计模式创建型模式&#xff08;共 5 种&#xff09;结构型模式&#xff08;共 7 种&#xff09;行为型模式&#xff08;共 11 种&#xff09; 总结 设计模式是什么 “每一个模式描述了一个在我们周围不断重复发生的问题&#xff0c;以及…...

ElasticSearch深度分页解决方案

一、前言 ElasticSearch是一个基于Lucene的搜索引擎&#xff0c;它支持复杂的全文搜索和实时数据分析。在实际应用中&#xff0c;我们经常需要对大量数据进行分页查询&#xff0c;但是传统的分页方式在处理大量数据时会遇到性能瓶颈。本文将介绍ElasticSearch分页工作原理、深…...

nginx下upstream模块详解

目录 一&#xff1a;介绍 二&#xff1a;特性介绍 一&#xff1a;介绍 Nginx的upstream模块用于定义后端服务器组&#xff0c;以及与这些服务器进行通信的方式。它是Nginx负载均衡功能的核心部分&#xff0c;允许将请求转发到多个后端服务器&#xff0c;并平衡负载。 在upst…...

基于ssm的双减后初小教育课外学习生活活动平台的设计与实现论文

双减后初小教育课外学习生活活动平台的设计与实现 摘 要 当下&#xff0c;正处于信息化的时代&#xff0c;许多行业顺应时代的变化&#xff0c;结合使用计算机技术向数字化、信息化建设迈进。以前学校对于课外学习活动信息的管理和控制&#xff0c;采用人工登记的方式保存相关…...

wblogic中间件配置数据源

配置数据源 1.服务-数据源-配置-新建 2.单机选一般数据源 3.选择源名称、jndi名称、数据库类型 4.选择驱动 5.下一步 6.输入连接串信息 参考&#xff1a; 格式二&#xff1a;jdbc:oracle:thin:<host>:<port>:<SID> 数据库名称配置的sid 7.测试配置&#xff…...

Java数据结构之装箱拆箱

装箱和拆箱 也叫装包拆包&#xff0c;装包是把那八种基本数据类型转换为它的包装类&#xff0c;拆包则相反 上面这俩种方式都是装包&#xff0c;下面是它的字节码文件 用到了Integer的ValueOf方法&#xff1a; 就是返回了一个Integer类的对象&#xff0c;把它的value属性设置成…...

各版本 操作系统 对 .NET Framework 与 .NET Core 支持

有两种类型的受支持版本&#xff1a;长期支持 (LTS) 版本和标准期限支持 (STS) 版本。 所有版本的质量都是一样的。 唯一的区别是支持的时间长短。 LTS 版本可获得为期三年的免费支持和补丁。 STS 版本可获得 18 个月的免费支持和修补程序。 有关详细信息&#xff0c;请参阅 .N…...

Golang 线程安全与 sync.Map

前言 线程安全通常是指在并发环境下&#xff0c;共享资源的访问被适当地管理&#xff0c;以防止竞争条件&#xff08;race conditions&#xff09;导致的数据不一致 Go语言中的线程安全可以通过多种方式实现 实现方式 互斥锁&#xff08;Mutexes&#xff09; Go的sync包提供…...

1.2 Hadoop概述

小肥柴的Hadoop之旅 1.2 Hadoop概述 目录1.2 Hadoop概述1.2.1 回归问题1.2.2 Google的三篇论文1.2.3 Hadoop的诞生过程1.2.4 Hadoop特点简介 参考文献和资料 ) 目录 1.2 Hadoop概述 1.2.1 回归问题 通过前一篇帖子的介绍&#xff0c;特别是问题思考部分的说明&#xff0c;我…...

Adams许可管理安全控制策略

随着全球信息化的快速发展&#xff0c;信息安全和许可管理问题日益凸显。在这场无形的挑战中&#xff0c;Adams许可管理安全控制策略以其卓越的性能和可靠性&#xff0c;引领着解决这类问题的新潮流。 Adams许可管理安全控制策略是一种全方位、多层次的安全控制方案&#xff0…...

无人地磅系统|内蒙古中兴首创无人地磅和远程高效管理的突破

走进标杆企业&#xff0c;感受名企力量&#xff0c;探寻学习优秀企业领先之道。 本期要跟砼行们推介的标杆企业是内蒙古赤峰市砼行业的龙头企业&#xff1a;赤峰中兴首创混凝土搅拌有限责任公司&#xff08;以下简称为中兴首创&#xff09;。 中兴首创成立于2011年初&#xff…...

【SpringCloud】7、Spring Cloud Gateway限流配置

1、限流介绍 Spring Cloud Gateway 的限流配置主要涉及到令牌桶算法的实现。令牌桶算法可以对某一时间窗口内的请求数进行限制,保持系统的可用性和稳定性,防止因流量暴增而导致的系统运行缓慢或宕机。 在 Spring Cloud Gateway 中,官方提供了 RequestRateLimiterGatewayFi…...

离散数学实战:用Python解决图论问题(附完整代码示例)

离散数学实战&#xff1a;用Python解决图论问题&#xff08;附完整代码示例&#xff09; 当你在社交软件上查看"可能认识的人"推荐&#xff0c;或是用导航软件规划最短路线时&#xff0c;背后都在运行图论算法。作为离散数学中最具工程价值的领域&#xff0c;图论将现…...

8255A工作方式0实战:手把手教你用汇编语言驱动八路抢答器LED与数码管

8255A工作方式0实战&#xff1a;从零构建八路抢答器驱动框架 记得第一次在实验室见到8255A芯片时&#xff0c;那块黑色的DIP封装器件看起来平平无奇&#xff0c;直到它让八颗LED随着我的汇编指令跳起"灯光芭蕾"。本文将带你深入这个经典可编程并行接口芯片的实战应用…...

nlp_structbert_sentence-similarity_chinese-large实战教程:本地知识库向量化检索完整指南

nlp_structbert_sentence-similarity_chinese-large实战教程&#xff1a;本地知识库向量化检索完整指南 你是不是经常遇到这样的问题&#xff1a;面对公司内部堆积如山的文档、产品手册、客服记录&#xff0c;想找某个特定信息时&#xff0c;却像大海捞针一样困难&#xff1f;…...

ViGEmBus虚拟手柄驱动:如何让任何设备变身Xbox 360或PS4控制器

ViGEmBus虚拟手柄驱动&#xff1a;如何让任何设备变身Xbox 360或PS4控制器 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus 在Windows游戏生态中&#xff0c;…...

Windows右键菜单终极管理指南:ContextMenuManager完全掌控你的系统交互体验

Windows右键菜单终极管理指南&#xff1a;ContextMenuManager完全掌控你的系统交互体验 【免费下载链接】ContextMenuManager &#x1f5b1;️ 纯粹的Windows右键菜单管理程序 项目地址: https://gitcode.com/gh_mirrors/co/ContextMenuManager Windows右键菜单管理一直…...

实战必备:快马AI打造ensp实验室级安装方案,保障网络教学顺利进行

作为一名网络工程专业的教师&#xff0c;我深知ensp&#xff08;Enterprise Network Simulation Platform&#xff09;在实验教学中的重要性。但每次新学期开始&#xff0c;最头疼的就是帮学生们搭建实验环境。不同电脑配置、系统版本、驱动兼容性问题&#xff0c;常常让简单的…...

压力型旋流喷嘴内喉部一点横向流体运动

&#xff08;一&#xff09;单图逐段解读图 1&#xff1a;0~0.0045s 全时段曲线&#xff08;含完整瞬态 准稳态&#xff09;分段特征与机理瞬态冲击段&#xff08;0~0.0002s&#xff09;曲线特征&#xff1a;极端剧烈的高频正负震荡&#xff0c;峰值接近 2m/s&#xff0c;是全…...

SEO_全面介绍SEO从入门到精通的关键知识点

<h2>什么是SEO&#xff1f;</h2> <p>SEO&#xff08;Search Engine Optimization&#xff0c;搜索引擎优化&#xff09;是一套通过优化网站内容和结构&#xff0c;以提高其在搜索引擎结果页面&#xff08;SERP&#xff09;中的自然排名的技术和策略。SEO不仅…...

【FastAPI 2.0流式AI响应终极指南】:20年架构师亲授异步SSE/Chunked Transfer实战避坑清单

第一章&#xff1a;FastAPI 2.0流式AI响应面试概览在现代AI应用开发中&#xff0c;面试场景下的实时交互体验正成为关键评估维度。FastAPI 2.0 引入了对原生异步流式响应&#xff08;StreamingResponse&#xff09;的深度优化&#xff0c;支持 Server-Sent Events&#xff08;S…...

Gepetto核心工具详解:函数反编译、变量重命名与代码注释

Gepetto核心工具详解&#xff1a;函数反编译、变量重命名与代码注释 【免费下载链接】Gepetto IDA plugin which queries OpenAIs gpt-3.5-turbo language model to speed up reverse-engineering 项目地址: https://gitcode.com/gh_mirrors/ge/Gepetto Gepetto是一款集…...