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

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

MySQL 8.0 事务全面讲解

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

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...

SpringCloud优势

目录 完善的微服务支持 高可用性和容错性 灵活的配置管理 强大的服务网关 分布式追踪能力 丰富的社区生态 易于与其他技术栈集成 完善的微服务支持 Spring Cloud 提供了一整套工具和组件来支持微服务架构的开发,包括服务注册与发现、负载均衡、断路器、配置管理等功能…...

Python爬虫(四):PyQuery 框架

PyQuery 框架详解与对比 BeautifulSoup 第一部分&#xff1a;PyQuery 框架介绍 1. PyQuery 是什么&#xff1f; PyQuery 是一个 Python 的 HTML/XML 解析库&#xff0c;它采用了 jQuery 的语法风格&#xff0c;让开发者能够用类似前端 jQuery 的方式处理文档解析。它的核心特…...

OpenHarmony标准系统-HDF框架之I2C驱动开发

文章目录 引言I2C基础知识概念和特性协议&#xff0c;四种信号组合 I2C调试手段硬件软件 HDF框架下的I2C设备驱动案例描述驱动Dispatch驱动读写 总结 引言 I2C基础知识 概念和特性 集成电路总线&#xff0c;由串网12C(1C、12C、Inter-Integrated Circuit BUS)行数据线SDA和串…...