【数据结构】排序算法(二):交换排序——从冒泡到快排的分治进化
目录一、冒泡排序1.1 算法思想1.2 代码实现1.3 运行推演1.4 复杂度分析二、快速排序2.1 算法思想2.2 代码实现2.3 运行推演2.4 复杂度分析前言 交换排序的本质是通过“比较相邻元素、逆序则交换”逐步消除逆序对。冒泡排序作为最朴素的交换排序以稳定的相邻交换保证稳定性快速排序则凭借分治策略与高效的划分操作成为实际应用中最快的通用排序算法。本文将从冒泡排序的迭代优化讲起直至快速排序的递归分治与复杂度陷阱结合代码与状态日志逐帧剖析。一、冒泡排序1.1 算法思想冒泡排序重复地遍历待排序序列每次比较相邻的两个元素如果它们的顺序错误前大于后就交换。每一趟遍历完成后当前未排序部分中的最大元素会像气泡一样“浮”到末尾。经过n-1趟遍历后整个序列有序。1.2 代码实现voidBubbleSort(DataType a[],intn){inti,j;for(i0;in-1;i){intflag0;// 优化标志位记录本趟是否发生过交换for(j0;jn-1-i;j){if(a[j]a[j1]){DataType tempa[j];a[j]a[j1];a[j1]temp;flag1;}}if(flag0){break;// 整趟无交换已经有序}}}代码解析外层循环i控制趟数每完成一趟末尾就多一个排好序的元素因此内层循环的终点为n - 1 - i。flag标志位是冒泡排序的重要优化如果某一趟完整遍历后没有发生任何交换说明数组已经完全有序可以直接结束排序。这将最好情况的时间复杂度从O ( n 2 ) O(n^2)O(n2)降至O ( n ) O(n)O(n)。1.3 运行推演初始数据4 6 3 2 8 0 1 10 5 4状态日志每一趟结束后的数组4 3 2 6 0 1 8 5 4 10 3 2 4 0 1 6 5 4 8 10 2 3 0 1 4 5 4 6 8 10 2 0 1 3 4 4 5 6 8 10 0 1 2 3 4 4 5 6 8 10步骤解析 第一趟排序中从索引0开始逐对比较。46?不交换63?交换得4,3,6,...62?交换……最大值 10 逐渐被推至末端。每趟过后数组尾部的有序序列逐步加长。到第五趟时发现未发生任何交换算法提前终止。可以看到冒泡排序的“有序尾部”是从后向前逐渐构建的。1.4 复杂度分析时间复杂度最好情况序列已有序且启用flag优化一趟扫描即可退出O ( n ) O(n)O(n)。最坏情况完全逆序需n − 1 n-1n−1趟完整遍历O ( n 2 ) O(n^2)O(n2)。平均O ( n 2 ) O(n^2)O(n2)。空间复杂度O ( 1 ) O(1)O(1)。稳定性 稳定。相邻元素若相等不发生交换相对顺序不变。二、快速排序2.1 算法思想快速排序采用分治策略从序列中选取一个元素作为“基准”pivot通过一趟划分Partition将序列分成左右两部分使得左边所有元素不大于基准右边所有元素不小于基准此时基准就落在了它的最终正确位置上。然后递归地对左右两部分进行同样的操作直到每个子区间只剩一个元素或为空。2.2 代码实现intPartition(DataType a[],intlow,inthigh){DataType pivota[low];//将第一个元素作为基准while(lowhigh){while(lowhigha[high]pivot)--high;a[low]a[high];while(lowhigha[low]pivot)low;a[high]a[low];}a[low]pivot;returnlow;}voidQuickSort(DataType a[],intlow,inthigh){if(lowhigh){intpivotposPartition(a,low,high);QuickSort(a,low,pivotpos-1);QuickSort(a,pivotpos1,high);}}///////// 调用 ///////////QuickSort(a,0,n-1);////////////////////////代码解析Partition函数采用经典的“左右指针填坑法”。选取a[low]作为基准并保存low位置即成为一个“坑”。右指针high向左移动找到第一个小于 pivot 的元素填入左坑此时high位置变成新坑左指针low向右移动找到第一个大于 pivot 的元素填入右坑。如此交替直至low high将 pivot 填入最后的坑位返回划分点。递归主函数QuickSort接收low和high若区间长度大于 1 则划分并递归处理左右子区间。注意while循环中的和保证了相等的元素不会陷入无限交换但也因此可能使相等元素分布不均不过这并不影响正确性。2.3 运行推演初始数据4 6 3 2 8 0 1 10 5 4状态日志每次划分后的数组状态以 4 为基准划分后: 1 0 3 2 4 8 6 10 5 4 以 1 为基准划分后: 0 1 3 2 4 8 6 10 5 4 以 3 为基准划分后: 0 1 2 3 4 8 6 10 5 4 以 8 为基准划分后: 0 1 2 3 4 4 6 5 8 10 以 4 为基准划分后: 0 1 2 3 4 4 6 5 8 10 以 6 为基准划分后: 0 1 2 3 4 4 5 6 8 10 0 1 2 3 4 4 5 6 8 10步骤解析 第一轮以首个元素4为基准。右指针从尾端向左找到4索引9处4停止但继续向左找到1不大于4将1填到左坑索引0左指针向右找到64填入右坑……最后基准4归位到索引4左侧全部 4右侧全部 4。后面递归直至全数组有序。日志清晰展现了分治的过程和基准逐步归位的工作方式。2.4 复杂度分析时间复杂度最好/平均每次划分将序列均分递归深度为log ⁡ n \log nlogn每层操作总和O ( n ) O(n)O(n)总时间O ( n log ⁡ n ) O(n \log n)O(nlogn)。最坏每次划分极不平衡如原序列已有序且始终取首元素为基准递归深度退化为n nn复杂度O ( n 2 ) O(n^2)O(n2)。空间复杂度 主要由递归调用栈深度决定。最好/平均O ( log ⁡ n ) O(\log n)O(logn)最坏O ( n ) O(n)O(n)。稳定性 不稳定。划分过程中的远距离填坑交换会改变相同元素的相对顺序。下一篇我们将进入选择排序的世界剖析简单选择排序与堆排序敬请期待。

相关新闻

1分钟解决iPhone USB网络共享驱动问题:Windows用户的终极指南

1分钟解决iPhone USB网络共享驱动问题:Windows用户的终极指南

1分钟解决iPhone USB网络共享驱动问题:Windows用户的终极指南 【免费下载链接】Apple-Mobile-Drivers-Installer Powershell script to easily install Apple USB and Mobile Device Ethernet (USB Tethering) drivers on Windows! 项目地址: https://gitcode.com…

2026/6/29 21:17:19阅读更多 →
【VLM】Seed2.1模型

【VLM】Seed2.1模型

note 面向视觉理解场景,Seed2.1 Pro 在 CharXiv-RQ、MeasureBench 等多个基准上取得最高分,体现出模型在复杂文档理解、图表读取、数值识别和视觉细节判断上的进一步提升。这类能力可以帮助模型在处理 PDF、报告、图表和多页材料时减少误读,…

2026/6/29 21:17:19阅读更多 →
3个高效技巧:如何彻底解决ComfyUI ControlNet Aux插件的安装难题?

3个高效技巧:如何彻底解决ComfyUI ControlNet Aux插件的安装难题?

3个高效技巧:如何彻底解决ComfyUI ControlNet Aux插件的安装难题? 【免费下载链接】comfyui_controlnet_aux ComfyUIs ControlNet Auxiliary Preprocessors 项目地址: https://gitcode.com/gh_mirrors/co/comfyui_controlnet_aux 对于AI绘画创作者…

2026/6/29 21:17:19阅读更多 →
item0(1):接地

item0(1):接地

Q:其实一直有个问题想问,那些芯片或者电阻的gnd还需要单独引一根线出来,再接到背面gnd网络吗?板子正面不是本来就要铺铜嘛?A:你的直觉完全正确!绝大多数情况下,不需要专门给每个芯片…

2026/6/29 22:22:43阅读更多 →
GM-Alt₂富勒烯室温超导体系学术评价

GM-Alt₂富勒烯室温超导体系学术评价

GM-Alt₂富勒烯室温超导体系学术评价 GM-Alt₂富勒烯室温超导体发明作者:乖乖数学 版本1:英文论文摘要(arXiv/PRB标准格式) Abstract A room-temperature superconducting GM-Alt₂ fullerene composite thin film supported o…

2026/6/29 22:22:43阅读更多 →
ChatGPT Plus值不值得续费:基于37项功能对比、127小时实测数据与API调用成本精算

ChatGPT Plus值不值得续费:基于37项功能对比、127小时实测数据与API调用成本精算

更多请点击: https://codechina.net 第一章:ChatGPT Plus与免费版的核心定位差异 ChatGPT Plus 与免费版并非简单的“功能增减”关系,而是基于不同用户场景与服务承诺所构建的差异化产品形态。免费版面向广泛公众提供基础对话能力&#xff0…

2026/6/29 22:22:43阅读更多 →
JiYuTrainer:极域电子教室破解工具,让学习回归自由

JiYuTrainer:极域电子教室破解工具,让学习回归自由

JiYuTrainer:极域电子教室破解工具,让学习回归自由 【免费下载链接】JiYuTrainer 极域电子教室防控制软件, StudenMain.exe 破解 项目地址: https://gitcode.com/gh_mirrors/ji/JiYuTrainer 你是否曾在学校机房上课时,被极域电子教室的…

2026/6/29 22:22:43阅读更多 →
3D Web 服务器环境搭建

3D Web 服务器环境搭建

一、Ubuntu安装nodejs# 导入源 curl -fsSL https://deb.nodesource.com/setup_lts.x | sudo -E bash - # 安装 sudo apt install nodejs -y //安装包管理器(1)curl -fsSL https://deb.nodesource.com/setup_lts.x | sudo -E bash - 导入源的作用&…

2026/6/29 22:22:43阅读更多 →
彩虹云商城二开美化源码 新增大量功能 云商城Plus版

彩虹云商城二开美化源码 新增大量功能 云商城Plus版

彩虹云商城二开美化源码 新增大量功能 云商城Plus版 彩虹云商城Plus版【开山祖师】 1:可视化面板 2:客服系统 3:异次元模板 4:分站长后台可在线交流 5:修复一键对接等等 内含完整搭建教程 下载链接:https://ww…

2026/6/29 22:17:41阅读更多 →
AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

6个月前的2025年12月,Boris Cherny 公开宣布自己卸载了 IDE。一时间,Vibe Coding 成了全行业最热的话题。6个月后,当我们回过头来拉一份真实账本,发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…

2026/6/29 3:27:55阅读更多 →
审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

引言:审计结束三个月了,审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间,内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中,审计…

2026/6/29 2:19:08阅读更多 →
如何在3秒内从普通图片生成专业级法线贴图:DeepBump的终极指南

如何在3秒内从普通图片生成专业级法线贴图:DeepBump的终极指南

如何在3秒内从普通图片生成专业级法线贴图:DeepBump的终极指南 【免费下载链接】DeepBump Normal & height maps generation from single pictures 项目地址: https://gitcode.com/gh_mirrors/de/DeepBump 还在为3D建模中的纹理制作而烦恼吗?…

2026/6/29 0:01:47阅读更多 →
OCAuxiliaryTools:终极OpenCore配置工具,让黑苹果安装从未如此简单!

OCAuxiliaryTools:终极OpenCore配置工具,让黑苹果安装从未如此简单!

OCAuxiliaryTools:终极OpenCore配置工具,让黑苹果安装从未如此简单! 【免费下载链接】OCAuxiliaryTools Cross-platform GUI management tools for OpenCore(OCAT) 项目地址: https://gitcode.com/gh_mirrors/oc/OCA…

2026/6/29 0:01:47阅读更多 →
终极Windows 11精简指南:使用tiny11builder快速创建纯净系统镜像

终极Windows 11精简指南:使用tiny11builder快速创建纯净系统镜像

终极Windows 11精简指南:使用tiny11builder快速创建纯净系统镜像 【免费下载链接】tiny11builder Scripts to build a trimmed-down Windows 11 image. 项目地址: https://gitcode.com/GitHub_Trending/ti/tiny11builder 你是否厌倦了Windows 11系统自带的20…

2026/6/29 0:01:47阅读更多 →