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

python实现插入排序、快速排序

python实现插入排序、快速排序

        • 算法步骤:
      • Python实现插入排序
      • 快速排序
        • 算法步骤:
      • Python实现快速排序
      • 算法时间复杂度

插入排序是一种简单直观的排序算法。它的基本思想是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法步骤:
  1. 从第一个元素开始,认为它已经被排序。
  2. 取出下一个元素,在已排序的元素序列中从后向前扫描。
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置。
  4. 重复步骤3,直到找到已排序的元素小于或等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2-5,直到所有元素均排序。

Python实现插入排序

def insertion_sort(lst):for i in range(1, len(lst)):key = lst[i]j = i - 1while j >= 0 and key < lst[j]:lst[j + 1] = lst[j]j -= 1lst[j + 1] = keyreturn lst# 示例
lst = [12, 11, 13, 5, 6]
sorted_lst = insertion_sort(lst)
print("排序后的列表:", sorted_lst)

快速排序

快速排序是一种分治算法,通常被认为是目前最快的排序算法之一。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个过程可以递归进行,以达到整个数据变成有序序列。

算法步骤:
  1. 从数列中挑出一个元素,称为“基准”(pivot)。
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

Python实现快速排序

def quick_sort(lst):if len(lst) <= 1:return lstelse:pivot = lst[len(lst) // 2]left = [x for x in lst if x < pivot]middle = [x for x in lst if x == pivot]right = [x for x in lst if x > pivot]return quick_sort(left) + middle + quick_sort(right)# 示例
lst = [3, 6, 8, 10, 1, 2, 1]
sorted_lst = quick_sort(lst)
print("排序后的列表:", sorted_lst)

算法时间复杂度

  • 插入排序的时间复杂度为O(n^2),适用于小规模数据或基本有序的数据。
  • 快速排序的平均时间复杂度为O(n log n),最差时间复杂度为O(n^2),但由于其常数因子较小,且具有较好的性能,因此在实际应用中广泛使用。

通过以上实现,可以看到这两种排序算法在不同场景下的适用性。插入排序算法简单直观,适用于小规模数据;快速排序则效率高,适用于大规模数据。

相关文章:

python实现插入排序、快速排序

python实现插入排序、快速排序 算法步骤&#xff1a; Python实现插入排序快速排序算法步骤&#xff1a; Python实现快速排序算法时间复杂度 插入排序是一种简单直观的排序算法。它的基本思想是通过构建有序序列&#xff0c;对于未排序数据&#xff0c;在已排序序列中从后向前扫…...

Spring Boot集成kudu快速入门Demo

1.什么是kudu 在Kudu出现前&#xff0c;由于传统存储系统的局限性&#xff0c;对于数据的快速输入和分析还没有一个完美的解决方案&#xff0c;要么以缓慢的数据输入为代价实现快速分析&#xff0c;要么以缓慢的分析为代价实现数据快速输入。随着快速输入和分析场景越来越多&a…...

html超文本传输协议

在今天的Web开发学习中&#xff0c;我掌握了一些HTML和CSS的基础知识&#xff0c;下面我将分享我的学习笔记&#xff0c;帮助大家快速构建一个简单的Web界面。 一、HTML基础标签 1. 网站头 使用<title>标签定义网页的标题。 html <title>我的第一个网页</t…...

利用AI辅助制作ppt封面

如何利用AI辅助制作一个炫酷的PPT封面 标题使用镂空字背景替换为动态视频 标题使用镂空字 1.首先&#xff0c;新建一个空白的ppt页面&#xff0c;插入一张你认为符合主题的图片&#xff0c;占满整个可视页面。 2.其次&#xff0c;插入一个矩形&#xff0c;右键选择设置形状格式…...

【spring boot】初学者项目快速练手

一小时带你从0到1实现一个SpringBoot项目开发_哔哩哔哩_bilibili 一、简介 二、项目结构 三、代码结构 1.生成框架 Spring Initializr 快速生成一个初始的项目代码&#xff0c;会生成一个demo文件 打开intellj idea&#xff0c;导入demo文件 2.目录结构 源码都放在src-ma…...

Laravel+swoole 实现websocket长链接

需要使用 swoole 扩展 我使用的是 swoole 5.x start 方法启动服务 和 定时器 调整 listenQueue 定时器可以降低消息通讯延迟 定时器会自动推送队列里面的消息 testMessage 方法测试给指定用户推送消息 使用 laravel console 启动 <?phpnamespace App\Console\Comman…...

【C#】Array和List

C#中的List<T>和数组&#xff08;T[]&#xff09;在某些方面是相似的&#xff0c;因为它们都是用来存储一系列元素的集合。然而&#xff0c;它们在功能和使用上有一些重要的区别&#xff1a; 数组&#xff08;Array&#xff09; 固定大小&#xff1a;数组的大小在声明时…...

SpringCloud网关的实现原理与使用指南

Spring Cloud网关是一个基于Spring Cloud的微服务网关&#xff0c;它是一个独立的项目&#xff0c;可以对外提供API接口服务&#xff0c;负责请求的转发和路由。本文将介绍Spring Cloud网关的实现原理和使用指南。 一、Spring Cloud网关的实现原理 Spring Cloud网关基于Spring…...

LabVIEW 与 PLC 通讯方式

在工业自动化中&#xff0c;LabVIEW 与 PLC&#xff08;可编程逻辑控制器&#xff09;的通信至关重要&#xff0c;常见的通信方式包括 OPC、Modbus、EtherNet/IP、Profibus/Profinet 和 Serial&#xff08;RS232/RS485&#xff09;。这些通信协议各有特点和应用场景&#xff0c…...

数据结构初阶·排序算法(内排序)

目录 前言&#xff1a; 1 冒泡排序 2 选择排序 3 插入排序 4 希尔排序 5 快速排序 5.1 Hoare版本 5.2 挖坑法 5.3 前后指针法 5.4 非递归快排 6 归并排序 6.1递归版本归并 6.2 非递归版本归并 7 计数排序 8 排序总结 前言&#xff1a; 目前常见的排序算法有9种…...

PL/SQL oracle上多表关联的一些记录

1.记录自己在PL/SQL上写的几张表的关联条件没有跑出来的一些优化 1. join后面跟上筛选条件 left join on t1.id t2.id and --- 带上分区字段&#xff0c;如 t1.month 202405, 操作跑不出来的一些问题&#xff0c;可能是数据量过大&#xff0c;未做分区过滤 2. 创建…...

Java.Net.UnknownHostException:揭开网络迷雾,解锁异常处理秘籍

在Java编程的浩瀚宇宙中&#xff0c;java.net.UnknownHostException犹如一朵不时飘过的乌云&#xff0c;让开发者在追求网络畅通无阻的道路上遭遇小挫。但别担心&#xff0c;今天我们就来一场说走就走的探险&#xff0c;揭秘这个异常的真面目&#xff0c;并手把手教你几招应对之…...

第十课:telnet(远程登入)

如何远程管理网络设备&#xff1f; 只要保证PC和路由器的ip是互通的&#xff0c;那么PC就可以远程管理路由器&#xff08;用telnet技术管理&#xff09;。 我们搭建一个下面这样的简单的拓扑图进行介绍 首先我们点击云&#xff0c;把云打开&#xff0c;点击增加 我们绑定vmn…...

【概率论三】参数估计:点估计(矩估计、极大似然法)、区间估计

文章目录 一. 点估计1. 矩估计法2. 极大似然法2.1. 似然函数2.2. 极大似然估计法 3. 评价估计量的标准3.1. 无偏性3.2. 有效性3.3. 一致性 二. 区间估计1. 区间估计的概念2. 正态总体参数的区间估计 参数估计讲什么 由样本来确定未知参数参数估计分为点估计与区间估计 一. 点估…...

自动化产线 搭配数据采集监控平台 创新与突破

自动化产线在现在的各行各业中应用广泛&#xff0c;已经是现在的生产趋势&#xff0c;不同的自动化生产设备充斥在各行各业中&#xff0c;自动化的设备会产生很多的数据&#xff0c;这些数据如何更科学化的管理&#xff0c;更优质的利用&#xff0c;就需要数据采集监控平台来完…...

【Karapathy大神build-nanogpt】Take Away Notes

B站翻译LINK Personal Note Andrej rebuild gpt2 in pytorch. Take Away Points Before entereing serious training, he use Shakespear’s work as a small debugging datset to see if a model can overfit. Overfitging is a should thing.If we use TF32 or BF32, (by…...

MySQL学习记录 —— 이십이 MySQL服务器日志

文章目录 1、日志介绍2、一般、慢查询日志1、一般查询日志2、慢查询日志FILE格式TABLE格式 3、错误日志4、二进制日志5、日志维护 1、日志介绍 中继服务器的数据来源于集群中的主服务。每次做一些操作时&#xff0c;把操作保存到重做日志&#xff0c;这样崩溃时就可以从重做日志…...

HTTPS请求头缺少HttpOnly和Secure属性解决方案

问题描述&#xff1a; 建立Filter拦截器类 package com.ruoyi.framework.security.filter;import com.ruoyi.common.core.domain.model.LoginUser; import com.ruoyi.common.utils.SecurityUtils; import com.ruoyi.common.utils.StringUtils; import com.ruoyi.framework.…...

react基础样式控制

行内样式 <div style{{width:500px, height:300px,background:#ccc,margin:200px auto}}>文本</div> class类名 注意&#xff1a;在react中使用class类名必须使用className 在外部src下新建index.css文件写入你的样式 .fontcolor{color:red } 在用到的页面引入…...

【区块链 + 智慧政务】涉税行政事业性收费“e 链通”项目 | FISCO BCOS应用案例

国内很多城市目前划转至税务部门征收的非税收入项目已达 17 项&#xff0c;其征管方式为行政主管部门核定后交由税务 部门征收。涉税行政事业性收费受限于传统的管理模式&#xff0c;缴费人、业务主管部门、税务部门、财政部门四方处于 相对孤立的状态&#xff0c;信息的传递靠…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...