当前位置: 首页 > 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;信息的传递靠…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

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

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

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

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

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...