第七课:Python基础排序算法与比较排序原理深度解析
比较排序算法是算法领域中的经典内容,其核心思想通过元素间的比较操作确定相对顺序。本文将深入探讨冒泡排序的优化策略、选择排序的变种实现、插入排序的典型应用场景,并通过统计比较次数直观展示算法效率差异。
一、冒泡排序的优化策略
传统冒泡排序存在冗余比较,可通过以下两种方式优化:
1. 提前终止机制
当某次遍历未发生交换时,说明数组已有序,可提前结束排序。
2. 缩减遍历范围
记录每次遍历最后发生交换的位置,后续遍历只需处理该位置之前的元素。
def bubble_sort(arr):n = len(arr)# 遍历数组for i in range(n - 1):# 记录最后交换的位置last_pos = 0# 进行剩余数据遍历for j in range(n - 1 - i):# 比较大小if arr[j] > arr[j + 1]:# 对数据进行位置调换arr[j], arr[j + 1] = arr[j + 1], arr[j]# 更新最后交换位置last_pos = j# 缩减后续遍历范围n = last_pos + 1return arr# 方法测试
print(bubble_sort([5, 3, 8, 4, 2]))
二、选择排序的变种实现
传统选择排序每次遍历仅确定一个元素位置,变种实现可同时确定首尾元素:
双向选择排序
- 每轮遍历同时查找最小值和最大值
- 将最小值交换到前端,最大值交换到后端
- 时间复杂度仍为O(n²),但比较次数减少约50%
def selection_sort(arr):left = 0right = len(arr) - 1# 左右数据比较while left < right:min_idx = leftmax_idx = leftfor i in range(left, right + 1):if arr[i] < arr[min_idx]:min_idx = iif arr[i] > arr[max_idx]:max_idx = i# 交换最小元素到前端arr[left], arr[min_idx] = arr[min_idx], arr[left]# 若最大值已在前端,需重新定位if max_idx == left:max_idx = min_idx# 交换最大元素到后端arr[right], arr[max_idx] = arr[max_idx], arr[right]left += 1right -= 1return arr# 测试
print(selection_sort([9, 5, 7, 2, 8]))
三、插入排序的典型应用场景
插入排序在以下场景表现优异:
1. 小规模数据排序
当数据量较小时(通常n < 100),插入排序的常数因子优势超过O(n²)复杂度劣势。
2. 部分有序数据
对基本有序的数据,插入排序接近O(n)时间复杂度。
3. 在线算法
数据实时到达时,可动态维护已排序序列。
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# 测试接近有序数组
print(insertion_sort([1, 3, 2, 4, 5, 6, 7]))
四、排序算法比较次数统计
通过计数器统计不同算法的比较操作次数,直观比较效率差异:
import randomdef count_comparisons(func, arr):class Counter:count = 0def __lt__(self, other):Counter.count += 1return func(self, other)wrapped_arr = [Counter() if isinstance(x, int) else x for x in arr]func(wrapped_arr)return Counter.count# 测试不同算法
algorithms = {"Bubble Sort": lambda x: optimized_bubble_sort(x.copy()),"Selection Sort": lambda x: bidirectional_selection_sort(x.copy()),"Insertion Sort": lambda x: insertion_sort(x.copy())
}test_cases = {"Random": [random.randint(0, 100) for _ in range(20)],"Sorted": list(range(20)),"Reversed": list(range(20, 0, -1))
}for name, arr in test_cases.items():print(f"\nTest Case: {name} Array")for algo_name, algo_func in algorithms.items():original = arr.copy()count = count_comparisons(algo_func, original)print(f"{algo_name}: {count} comparisons")
典型输出结果:
Test Case: Random Array
Bubble Sort: 172 comparisons
Selection Sort: 190 comparisons
Insertion Sort: 164 comparisonsTest Case: Sorted Array
Bubble Sort: 19 comparisons
Selection Sort: 190 comparisons
Insertion Sort: 19 comparisonsTest Case: Reversed Array
Bubble Sort: 190 comparisons
Selection Sort: 190 comparisons
Insertion Sort: 171 comparisons
五、结论
- 冒泡排序优化后适合处理部分有序数据
- 双向选择排序通过减少比较次数提升效率
- 插入排序在小数据量和实时场景中表现突出
- 比较次数统计显示:
- 最好情况下(已有序),插入排序和冒泡排序优势明显
- 最坏情况下(逆序),所有算法比较次数接近理论最大值
- 随机数据中,插入排序通常表现最佳
理解这些基础排序算法的原理及优化策略,不仅有助于算法面试准备,更能培养对算法效率的直观感知。在实际开发中,应根据数据规模和特性选择合适的排序策略。
关注我!!🫵 持续为你带来Python算法相关内容。
相关文章:
第七课:Python基础排序算法与比较排序原理深度解析
比较排序算法是算法领域中的经典内容,其核心思想通过元素间的比较操作确定相对顺序。本文将深入探讨冒泡排序的优化策略、选择排序的变种实现、插入排序的典型应用场景,并通过统计比较次数直观展示算法效率差异。 一、冒泡排序的优化策略 传统冒泡排序存…...
项目流程中关键节点的测试类型
一、全流程测试框架图 #mermaid-svg-LmUdhLObstSpThwP {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-LmUdhLObstSpThwP .error-icon{fill:#552222;}#mermaid-svg-LmUdhLObstSpThwP .error-text{fill:#552222;strok…...
EasyRTC嵌入式音视频通信SDK:WebRTC技术下的硬件与软件协同演进,开启通信新时代
在当今数字化时代,智能设备的普及和人们对实时通信需求的不断增长,推动了嵌入式音视频通信技术的快速发。EasyRTC嵌入式音视频通信SDK凭借其独特的技术特点和应用优势,在嵌入式设备和多平台实时通信领域脱颖而出。 1、轻量级设计与高性能 Ea…...
机器视觉工程师如何看机器视觉展会,有些机器视觉兄弟参加机器视觉展会,真的是参加了?重在参与?
作为机器视觉工程师,参加机器视觉展会不仅是了解行业前沿技术的窗口,也是拓展专业网络、寻找解决方案的重要机会。以下是结合展会信息和工程师视角的综合建议: 一、聚焦技术趋势与创新应用 参与技术论坛与研讨会 展会同期的技术论坛是获取行业洞见的核心渠道。例如: 上海展…...
重温Ubuntu 24.04 LTS
用户调整 # 创建新用户 sudo adduser newusername # 设置新用户的密码 sudo passwd newusername # 将新用户添加到 sudo 组 sudo usermod -aG sudo newusername # 修改ssh访问权限 sudo nano /etc/ssh/sshd_config # 将新用户加入,此时root将无法访问 AllowUsers n…...
新版 eslintrc 文件弃用 .eslintignore已弃用 替代方案
1.进入eslint.config.mjs文件 2.import { defineConfig, globalIgnores } from "eslint/config"; 引入globalIgnores 3.配置 defineConfig([ ... globalIgnores([ "config/*", ".husky", ".local", "public/*", ".…...
优化 SQL 语句方向和提升性能技巧
优化 SQL 语句是提升 MySQL 性能的关键步骤之一。通过优化 SQL 语句,可以减少查询时间、降低服务器负载、提高系统吞吐量。以下是优化 SQL 语句的方法、策略和技巧: 一、优化 SQL 语句的方法 1. 使用 EXPLAIN 分析查询 作用:查看 SQL 语句的执行计划,了解查询是如何执行的…...
数据可视化革命!「图表狐」五大行业新范式:从科研论文到商业决策的AI进化论
图表狐 - AI图表生成工具,在线数据可视化 一、学术研究:突破传统制图范式 案例1 基因测序热图 用户输入: "绘制差异表达基因热图,行标签为GeneA/B/C,列包含正常组5例、癌症组7例,红色标记上调基因(f…...
Jenkins集成Trivy安全漏洞检查指南
要将Jenkins与Trivy集成以实现制品的安全漏洞检查,可以按照以下步骤操作: 安装Trivy 在Jenkins服务器或构建节点上安装Trivy # 使用包管理器(如Debian/Ubuntu) sudo apt-get install -y wget apt-transport-https gnupg lsb-rel…...
git使用钩子文件出现错误
git的钩子文件出现错误 问题打印:解决办法1.删除本地钩子文件2. 恢复commit-msg钩子3.重新提交工程 问题打印: 无法commit 1 个文件: .git/hooks/commit-msg: 行 1: 未预期的符号 < 附近有语法错误 .git/hooks/commit-msg: 行 1: Your browse does …...
SpringBoot 第二课(Ⅱ)配置嵌入式服务器
目录 一、封装类解读 二、注册Servlet三大组件(Servlet、Filter、Listener) 自定义这三个组件 WebConfig MyFilter MyListener HelloController hello1.html hello2.html 三、使用外置的Servlet容器 1.一定要确保打包方式是war包 2.将…...
Python学习笔记(6)
Python学习笔记(6) 第13节课 函数基础1.函数定义与调用2.函数的返回值3.局部变量与全局变量 第13节课 函数基础 对于任何一个知识点,必须讨论的三个问题: (1)它是啥 (2)为啥有它 …...
HarmonyOS Next应用架构设计与模块化开发详解
引言 在HarmonyOS Next开发中,合理的应用架构设计和模块化开发是构建高效、可维护应用的关键。本文将深入探讨HarmonyOS Next应用的架构设计思路,并通过实际代码示例展示如何实现模块化开发。 应用架构设计 HarmonyOS Next应用通常采用分层架构设计&…...
batman-adv 优化:基于信号强度(RSSI)选择链路
batman-adv 优化:基于信号强度(RSSI)选择链路 1. 背景介绍 batman-adv(Better Approach To Mobile Ad-hoc Networking Advanced) 是一种用于无线 Mesh 网络的路由协议。它主要基于 ETX(Expected Transmis…...
计算机二级:函数基础题
函数基础题 第一题 rinput("请输入半径:") c3.1415926*r*2 print("{:.0f}".format(c))输出: Type Error第二题 a7 b2 print(a%2)输出 1第三题 ab4 def my_ab(ab,xy):abpow(ab,xy)print(ab,end"\n") my_ab(ab,2)prin…...
系统思考与心智模式
“问题不是出在我们做了多少,而是出在我们做了什么。” — 赫尔曼凯恩 “一分耕耘一分收获”,这似乎是我们脑海中根深蒂固的心智模式。今天,我在一家餐厅用餐,店员告诉我,打卡收藏可以获得一份小食。没过多久…...
高考志愿填报管理系统基于Spring Boot SSM
目录 摘要 一、系统需求分析: 1.1用户主体分析 1.2 功能需求分析 1.3、非功能需求分析 二、技术实现: 三、结论: 摘要 该系统主要实现了:学生信息管理、院校信息查询、专业信息展示、志愿填报模拟、智能推荐管…...
[深度学习]图像分类项目-食物分类
图像分类项目-食物分类(监督学习和半监督学习) 文章目录 图像分类项目-食物分类(监督学习和半监督学习)项目介绍数据处理设定随机种子读取文件内容图像增广定义Dataset类 模型定义迁移学习 定义超参Adam和AdamW 训练过程半监督学习定义Dataset类模型定义定义超参训练过程 项目介…...
Qt在ARM中,如何使用drmModeObjectSetProperty 设置 Plane 的 zpos 值
在 Qt 中直接使用 drmModeObjectSetProperty 设置 Plane 的 zpos 值需要结合 Linux DRM/KMS API 和 Qt 的底层窗口系统(如 eglfs 平台插件)。以下是详细步骤和代码示例: 1. 原理说明 DRM/KMS 基础: Plane:负责图层合成…...
springboot milvus search向量相似度查询 踩坑使用经验
1.前提提要:java的pom 版本为:2.4.9 milvus 版本是:2.4.13-hotfix 2.先来工具类方法 /*** 向量搜索* param client* param query* return*/public SearchResp search(NonNull MilvusClientV2 client, NonNull VectorCondition query) {final …...
BFS解决FloodFill算法
1.图像渲染 733. 图像渲染 - 力扣(LeetCode) 1.题目解析 有一幅以 m x n 的二维整数数组表示的图画 image ,其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行…...
计算机组成原理
计算机组成原理是计算机科学与技术领域的一门基础课程,它主要研究计算机硬件系统的结构、设计和工作原理。通过学习计算机组成原理,可以深入理解计算机是如何执行程序的,从最底层的角度了解计算机的工作机制。以下是计算机组成原理的一些核心…...
Spring Boot整合SSE实现消息推送:跨域问题解决与前后端联调实战
摘要 本文记录了一次完整的Spring Boot整合Server-Sent Events(SSE)实现实时消息推送的开发过程,重点分析前后端联调时遇到的跨域问题及解决方案。通过CrossOrigin注解的实际应用案例,帮助开发者快速定位和解决类似问题。 一、项…...
硅基流动:推理加速,告别“服务器繁忙,请稍后再试”
DeepSeek虽然一直热度高涨,但存在一个很直接的问题——“服务器繁忙,请稍后再试”。 一、介绍概况 硅基流动(SiliconFlow)是北京硅基流动科技有限公司推出的AI基础设施(AI Infra)平台,成立于202…...
腾讯云DNS和Lego工具结合使用,可以方便地为你的域名自动申请和续期SSL证书。
腾讯云DNS和Lego工具结合使用,可以方便地为你的域名自动申请和续期SSL证书。以下是具体步骤: 1. 准备工作 腾讯云账号:确保你有一个腾讯云账号,并且已经开通了DNS服务。域名:确保你拥有一个域名,并且已经…...
微服务 - 高级篇
微服务 - 高级篇 一、服务治理(一)服务注册与发现(二)负载均衡(三)服务熔断与降级 二、分布式事务(一)解决方案(二)最终一致性 三、性能优化(一&a…...
【Linux】线程基础
🔥个人主页:Quitecoder 🔥专栏:linux笔记仓 目录 01.背景知识02.线程概念简单使用线程线程调度成本更低 01.背景知识 OS进行内存管理,不是以字节为单位的,而是以内存块为单位的,默认大小为4kb&…...
WHAM 人体3d重建部署笔记 vitpose
目录 视频结果: docker安装说明: conda环境安装说明: 依赖项: 依赖库: 安装 mmpose,mmcv 下载模型权重: 算法原理, demo脚本 报错inference_top_down_pose_model: 测试命令: 视频结果: wham_smpl预测结果 git地址: GitHub - yohanshin/WHAM WHAM: Recons…...
netplan是如何操控systemd-networkd的? 笔记250324
netplan是如何操控systemd-networkd的? netplan通过以下方式操控systemd-networkd: 工作原理:netplan读取位于/etc/netplan/目录下的YAML格式的配置文件,这些配置文件描述了网络接口的配置。netplan会将这些配置文件解析并转换为systemd-ne…...
[学成在线]06-视频分片上传
上传视频 需求分析 教学机构人员进入媒资管理列表查询自己上传的媒资文件。 点击“媒资管理” 进入媒资管理列表页面查询本机构上传的媒资文件。 教育机构用户在"媒资管理"页面中点击 "上传视频" 按钮。 点击“上传视频”打开上传页面 选择要上传的文件…...
机器视觉场景应用中,有没有超景深的工业镜头
在机器视觉领域,确实存在具有超景深特性的工业镜头,这类镜头通过特殊的光学设计或技术手段,能够显著扩大清晰成像的纵向范围,从而满足复杂检测场景中对多平面物体清晰成像的需求。以下是相关技术要点及典型镜头类型: 1. 远心镜头 远心镜头是超景深镜头的典型代表,其特点包…...
初探 Dubbo Rust SDK打造现代微服务的新可能
一、背景故事:为什么要在微服务中用 Rust? 微服务世界曾是 Java 的天下,后来 Go 异军突起,如今,Rust 凭借其“高性能 安全 零成本抽象”的特性,正在逐步走入服务端核心舞台。 问题随之而来:…...
如何理解响应式编程
思考: 分析Netty与Reactor背压协调策略 用户的问题是关于如何在 Netty 和 Project Reactor 联合使用时处理背压问题,特别是当 Reactor 的处理速度跟不上 Netty 的事件产生速度时该怎么办。这是一个技术性很强的问题,涉及到 Netty 的非阻塞特…...
Python网络编程入门
一.Socket 简称套接字,是进程之间通信的一个工具,好比现实生活中的插座,所有的家用电器要想工作都是基于插座进行,进程之间要想进行网络通信需要Socket,Socket好比数据的搬运工~ 2个进程之间通过Socket进行相互通讯&a…...
DeepSeek 助力 Vue3 开发:打造丝滑的表格(Table)之添加导出数据功能示例14,TableView15_14多功能组合的导出表格示例
前言:哈喽,大家好,今天给大家分享一篇文章!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏+关注哦 💕 目录 DeepSeek 助力 Vue3 开发:打造丝滑的表格(Table)之添加导出数据功能示例14,TableView15_14多功…...
鸿蒙特效教程10-卡片展开/收起效果
鸿蒙特效教程10-卡片展开/收起效果 在移动应用开发中,卡片是一种常见且实用的UI元素,能够将信息以紧凑且易于理解的方式呈现给用户。 本教程将详细讲解如何在HarmonyOS中实现卡片的展开/收起效果,通过这个实例,你将掌握ArkUI中状…...
如何创建一个socket服务器?
1. 导入必要的库 首先,需要导入Python的socket库,它提供了创建和管理socket连接的功能。 python import socket 2. 创建服务器端socket 使用socket.socket()函数创建一个服务器端的socket对象,指定协议族(如socket.AF_INET表示…...
react自定义hook
自定义hook: 用来封装复用的逻辑,,自定义hook是以use开头的普通函数,,将组件中可复用的状态逻辑抽取到自定义的hook中,简化组件代码 常见自定义hook例子: 封装一个简单的计数器 import {useS…...
Android Compose 框架的状态与 ViewModel 的协同(collectAsState)深入剖析(二十一)
Android Compose 框架的状态与 ViewModel 的协同(collectAsState)深入剖析 一、引言 在现代 Android 应用开发中,构建响应式和动态的用户界面是至关重要的。Android Compose 作为新一代的声明式 UI 工具包,为开发者提供了一种简…...
系统与网络安全------网络应用基础(1)
资料整理于网络资料、书本资料、AI,仅供个人学习参考。 TCP/IP协议及配置 概述 TCP/IP协议族 计算机之间进行通信时必须共同遵循的一种通信规定 最广泛使用的通信协议的集合 包括大量Internet应用中的标准协议 支持跨网络架构、跨操作系统平台的数据通信 主机…...
linux常用指令(6)
今天我们继续学习一些linux常用指令,丰富我们linux基础知识,那么话不多说,来看. 1.cp指令 功能描述:拷贝文件到指定目录 基本语法:cp [选项] source dest 常用选项:-r:递归复制整个文件夹 拷贝文件: 拷贝文件夹&am…...
EasyUI数据表格中嵌入下拉框
效果 代码 $(function () {// 标记当前正在编辑的行var editorIndex -1;var data [{code: 1,name: 1,price: 1,status: 0},{code: 2,name: 2,price: 2,status: 1}]$(#dg).datagrid({data: data,onDblClickCell:function (index, field, value) {var dg $(this);if(field ! …...
【设计模式】单件模式
七、单件模式 单件(Singleton) 模式也称单例模式/单态模式,是一种创建型模式,用于创建只能产生 一个对象实例 的类。该模式比较特殊,其实现代码中没有用到设计模式中经常提起的抽象概念,而是使用了一种比较特殊的语法结构&#x…...
C++类与对象的第二个简单的实战练习-3.24笔记
哔哩哔哩C面向对象高级语言程序设计教程(118集全) 实战二 Cube.h #pragma once class Cube { private:double length;double width;double height; public:double area(void);double Volume(void);//bool judgement(double L1, double W1, double H1);…...
【视频】m3u8相关操作
1、视频文件转m3u8 1.1 常用命令 1)默认只保留 5 个ts文件 ffmpeg -i input.mp4 -start_number 0 -hls_time 10 -hls_list_size 0 -f hls stream1.m3u82)去掉音频 -an,保留全部ts文件 ffmpeg -i input.mp4 -vf scale=640:480 -an -start_number 0 -hls_time 10 -hls_lis…...
G-Star 校园开发者计划·黑科大|开源第一课之 Git 入门
万事开源先修 Git。Git 是当下主流的分布式版本控制工具,在软件开发、文档管理等方面用处极大。它能自动记录文件改动,简化合并流程,还特别适合多人协作开发。学会 Git,就相当于掌握了一把通往开源世界的钥匙,以后参与…...
前端框架学习路径与注意事项
学习前端框架是一个系统化的过程,需要结合理论、实践和工具链的综合掌握。以下是学习路径的关键方面和注意事项: 一、学习路径的核心方面 1. 基础概念与核心思想 组件化开发:理解组件的作用(复用性、隔离性)、组件通信…...
Apache Hive:基于Hadoop的分布式数据仓库
Apache Hive 是一个基于 Apache Hadoop 构建的开源分布式数据仓库系统,支持使用 SQL 执行 PB 级大规模数据分析与查询。 主要功能 Apache Hive 提供的主要功能如下。 HiveServer2 HiveServer2 服务用于支持接收客户端连接和查询请求。 HiveServer2 支持多客户端…...
langgraph简单Demo3(画一个简单的图)
文章目录 画图简单解析再贴结果图 画图 from langgraph.graph import StateGraph, END from typing import TypedDict# 定义状态结构 # (刚入门可能不理解这是什么,可以理解为一个自定义的变量库,你的所有的入参出参都可以定义在这里) # 如下࿱…...
LCR 187. 破冰游戏(python3解法)
难度:简单 社团共有 num 位成员参与破冰游戏,编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target,从 0 号成员起开始计数,排在第 target 位的成员离开圆桌,且成员离开后从下一个成员开始计数…...