python实现插入排序算法

简介: 插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实...

插入排序,其原理是通过构建一个初始的有序序列,然后从无需序列中抽取元素,插入到有序序列的相对排序位置,就像将一堆编号混乱的书,一本一本的放到书架上,找到上下编号之间的位置插入,最后完成整理。

python实现插入排序并不难,从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置,实现如下:

def insert_sort(items):
    for i in range(1, len(items)):
        # 从第i个元素开始向前比较,如果小于前一个元素,交换位置
        for j in range(i, 0, -1):
            if items[j] < items[j-1]:
                items[j], items[j-1] = items[j-1], items[j]

插入排序的可应用于这样的场景:需要合并两个有序序列,并且合并后的序列依旧有序,此时插入排序可以排上用场。

如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。

最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用

但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

相关文章
|
机器学习/深度学习 人工智能 自然语言处理
图解机器学习 | GBDT模型详解
GBDT是一种迭代的决策树算法,将决策树与集成思想进行了有效的结合。本文讲解GBDT算法的Boosting核心思想、训练过程、优缺点、与随机森林的对比、以及Python代码实现。
10157 2
图解机器学习 | GBDT模型详解
|
28天前
|
弹性计算 安全 数据库
阿里云免费云服务器全解析:学生可用300元券抵扣,个人和企业直接申请免费试用
本文梳理阿里云免费云服务器试用体系,分学生、个人、企业三套入口:学生认证后可领每年 300 元无门槛优惠券,在专属专区抵扣云服务器、数据库、CDN、大模型等产品;个人版与企业版 ECS 免费试用分别提供 300 元、660 元额度;轻量应用服务器提供 2vCPU 4GiB、2vCPU 1GiB 预装镜像试用。但免费资源均有额度、时长、地域、流量、续费与备案限制,试用 ECS 不支持备案,应先认证、验证后转入付费方案。
|
3月前
|
人工智能 JSON 自然语言处理
Vibe Coding实战:从零构建网页3D交互角色
本文详解Vibe Coding(氛围编程)在网页3D开发中的实践:以“2D→3D→网页”标准化流程为核心,结合腾讯混元3D生成高质量可动画模型,再用Three.js嵌入GLB文件实现交互式渲染,并提供完整代码、提示词模板及八大常见坑点解决方案,助力零基础快速落地3D网页应用。
557 0
Vibe Coding实战:从零构建网页3D交互角色
|
4月前
|
数据采集 运维 监控
本地探店达人筛选与合作全流程实操运营指南
本文详解实体门店高效对接本地探店达人的实操方法:破除“唯粉丝论”误区,聚焦内容垂直度、粉丝地域匹配度与真实互动质量三大筛选标准;梳理置换、单篇付费、长期绑定三类合作模式及书面约定要点;提供发布后48小时流量助推、转化复盘与素材二次复用策略,助力门店科学分配资源,提升同城引流与转化效率。(239字)
|
7月前
|
SQL 人工智能 Java
揭秘AI全栈代码生成器的技术内核:从Prompt工程到本地一键部署的架构实战
本文介绍“智码方舟”AI工程化架构:突破“AI写代码”到“可运行系统”的鸿沟。通过多Agent协同、JSON Schema约束生成、DB Schema统一推演、Docker Compose混合部署及云原生调度(阿里云百炼),实现自然语言→完整全栈工程→一键本地启动的闭环,大幅提升AI生成代码的落地效率。
|
10月前
|
弹性计算 ice
阿里云4核8g服务器多少钱一年?1个月和1小时价格,省钱购买方法分享
阿里云4核8G服务器价格因实例类型而异,经济型e实例约159元/月,计算型c9i约371元/月,支持按小时计费及年付优惠,实际购买可享折扣,热门CPU含Intel Xeon、AMD EPYC等。
863 10
|
11月前
|
监控 安全 网络安全
静态IP怎么选购及静态IP的优势
本文介绍静态IP购买与优质网络代理服务的优势,涵盖稳定性、安全性和匿名性。静态IP适合企业及长期连接需求,优质代理服务保障隐私,动态住宅IP灵活多变。通过对比各类IP特点,帮助用户根据实际需求选择最佳网络解决方案,提升上网体验与安全性。(238字)
|
消息中间件 人工智能 数据可视化
文生图架构设计原来如此简单之用户界面架构
节点式界面是文生图工具中一种强大而灵活的设计范式,以 ComfyUI 为代表。这种设计将复杂的图像生成过程分解为可视化的模块化组件,使用户能够精确控制生成流程的每个环节。
870 2
|
10月前
|
监控 数据可视化 安全
研发团队必看的技术债务管理的方法与工具
本文系统阐述技术债务的识别、分类与管理策略,将其分为紧急、重要、一般和整理四类,揭示其复利危害,并提供量化评估、优先级排序、偿还计划及工具支持的完整框架,助力团队从被动应对转向主动治理,将技术债转化为可控的技术投资。
|
网络协议 网络安全
【网络安全】Wireshark过滤数据包&分析TCP三次握手(下)
【网络安全】Wireshark过滤数据包&分析TCP三次握手
826 1