当前位置: 首页 > 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…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...

Python的__call__ 方法

在 Python 中&#xff0c;__call__ 是一个特殊的魔术方法&#xff08;magic method&#xff09;&#xff0c;它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时&#xff08;例如 obj()&#xff09;&#xff0c;Python 会自动调用该对象的 __call__ 方法…...