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

从零开始!DeepSeek-R1-Distill-Qwen-1.5B完整部署流程详解

从零开始&#xff01;DeepSeek-R1-Distill-Qwen-1.5B完整部署流程详解 1. 模型简介与核心优势 1.1 什么是DeepSeek-R1-Distill-Qwen-1.5B&#xff1f; DeepSeek-R1-Distill-Qwen-1.5B是一款经过知识蒸馏优化的轻量级语言模型&#xff0c;由DeepSeek团队基于Qwen-1.5B架构开发…...

从MATLAB验证到FPGA上板:双频信号叠加的完整开发闭环实战

从MATLAB验证到FPGA上板&#xff1a;双频信号叠加的完整开发闭环实战 在数字信号处理领域&#xff0c;实现双频信号的精确叠加是一个常见但极具挑战性的任务。无论是通信系统中的载波调制&#xff0c;还是音频处理中的音效合成&#xff0c;都需要工程师能够准确地在硬件层面实现…...

从拒稿到录用:我的TOMM投稿实战复盘与经验分享

1. 从TMM拒稿到TOMM录用的心路历程 第一次收到TMM的拒稿邮件时&#xff0c;我正在实验室熬夜改代码。邮件弹出来的那一刻&#xff0c;整个人就像被泼了一盆冷水。那篇论文已经经历了三轮大修&#xff0c;每次都是几十条审稿意见&#xff0c;我们团队前前后后修改了上百个细节。…...

热键冲突解决:从检测到修复的完整指南

热键冲突解决&#xff1a;从检测到修复的完整指南 【免费下载链接】hotkey-detective A small program for investigating stolen hotkeys under Windows 8 项目地址: https://gitcode.com/gh_mirrors/ho/hotkey-detective 在日常电脑使用中&#xff0c;我们经常会遇到这…...

避坑指南:QT5的QListView复选框居中/对齐问题解决方案(含TableView对比)

QT5复选框对齐终极指南&#xff1a;从QListView到TableView的完美排版方案 在QT5界面开发中&#xff0c;复选框控件的视觉对齐问题堪称"程序员强迫症终结者"——明明功能已经实现&#xff0c;却总在UI细节上栽跟头。本文将带您深入解决QListView和TableView中复选框居…...

usearch的内存泄漏自动化测试:在CI中集成泄漏检测

usearch的内存泄漏自动化测试&#xff1a;在CI中集成泄漏检测 【免费下载链接】usearch Fastest Open-Source Search & Clustering engine for Vectors & &#x1f51c; Strings in C, C, Python, JavaScript, Rust, Java, Objective-C, Swift, C#, GoLang, and Wolf…...

终极Chromium性能优化方案:Thorium浏览器让你的上网体验快如闪电

终极Chromium性能优化方案&#xff1a;Thorium浏览器让你的上网体验快如闪电 【免费下载链接】thorium Chromium fork named after radioactive element No. 90. Windows and MacOS/Raspi/Android/Special builds are in different repositories, links are towards the top of…...

文墨共鸣惊艳效果:古风UI下实时语义相似度计算与墨韵动画演示

文墨共鸣惊艳效果&#xff1a;古风UI下实时语义相似度计算与墨韵动画演示 1. 项目概览 文墨共鸣是一个将深度学习技术与传统水墨美学完美结合的系统。它基于先进的StructBERT模型&#xff0c;能够智能分析两段文字之间的语义相似度&#xff0c;并通过优雅的古风界面直观展示结…...

GLM-OCR赋能微信小程序:开发随身扫描与文档管理工具

GLM-OCR赋能微信小程序&#xff1a;开发随身扫描与文档管理工具 1. 引言 你有没有遇到过这样的场景&#xff1f;开会时看到白板上写满了重要信息&#xff0c;想快速记录下来&#xff0c;却只能对着手机一张张拍照&#xff0c;事后还得手动整理&#xff1b;或者收到一份纸质合…...

从手机端到边缘设备:聊聊轻量化模型设计中FLOPs、MACs和Params的权衡艺术

从手机端到边缘设备&#xff1a;轻量化模型设计中FLOPs、MACs和Params的权衡艺术 当我们在智能手机上使用人脸解锁功能&#xff0c;或是通过智能音箱与AI助手对话时&#xff0c;背后运行的往往是经过精心设计的轻量化神经网络模型。这些模型需要在有限的算力和内存资源下&#…...