1. 为什么要手写这三种排序算法我最近在整理基础算法资料时把冒泡排序、选择排序、插入排序的Python实现重新写了一遍。这三个排序算法几乎是所有编程入门课程的标配也是面试中经常出现的考题。很多人觉得它们简单但真正落实到代码层面能一次写对的人其实不多尤其是插入排序的移位逻辑和冒泡排序的边界条件稍不留神就会出错。这篇内容主要解决三类问题第一帮助你理解这三种排序的核心执行过程不是死背代码而是从运行逻辑上建立直觉第二提供可以直接跑起来的Python源码包含基础版本和优化版本并逐行解释关键代码的设计意图第三分享我在实际编码和教学过程中踩过的坑比如索引越界、空数组处理、稳定性和原地排序问题这些经验在普通教程里不容易看到。适合阅读这篇文章的人包括刚开始学算法的大学生、准备面试的求职者、想把手写排序逻辑梳理清楚的开发者以及想了解Python代码风格细节的爱好者。不管你是哪种角色读完这篇内容都可以直接照着代码敲一遍再对照性能测试数据加深理解。2. 三种排序的核心思路与适用场景2.1 冒泡排序相邻交换与大数上浮冒泡排序的思路非常直观从头开始依次比较相邻的两个元素如果顺序不对就交换。每一轮结束后当前范围内最大的元素就会像气泡一样浮到最右侧就像水里冒泡泡一样最大的气泡先到水面。用生活场景来类比你在食堂排队打饭老师傅让你和旁边同学比身高如果你比旁边矮就和旁边同学换位置从队头走到队尾最高的人自然就到了队伍末尾。下一轮就不用管最后那个人了继续从队头来一轮次高的人站到倒数第二个位置。重复这个动作队伍就从矮到高排列了。这个算法的代码结构是双层循环外层循环控制轮数内层循环执行相邻比较和交换。一个容易忽略的细节是每轮过后比较的区间就可以缩短一位因为末尾的元素已经有序。如果不缩短区间算法依然能正确排序但会多出大量无意义的比较性能损耗在数据量大时相当明显。2.2 选择排序每轮锁定最小值选择排序的思路更简单直接每一轮从待排序区间中找出最小值把这个最小值放到区间的最左端。下一轮从剩余的元素中继续找最小值放到第二位置。重复这个过程直到所有元素有序。和冒泡排序一样它也是双层循环但交换次数显著减少。冒泡排序每轮可能交换很多次而选择排序每轮最多只交换一次。这也是选择排序在某些场景下反而比冒泡快的原因虽然比较次数同样是O(n²)但交换操作的常数因子更小。实际写代码时选择排序最容易出错的地方是找最小值和交换的配合。很多新手会把最小值直接存成值然后忘了记录它的下标。最后交换的时候只能用值去查找位置这样一来如果数组里有重复值交换就会错位。正确做法是用一个变量记录最小值的下标而不是记录值本身。2.3 插入排序扑克牌式的逐步有序插入排序的思路非常符合人类的日常习惯。你想一下自己打扑克牌的时候摸到新牌后怎么整理你会把新牌插入到手里已经有序的牌堆中从右往左找到合适的位置然后把牌插进去。插入排序的代码逻辑就是模拟这个过程。从第二个元素开始把当前元素当作新摸到的牌向左遍历已经有序的部分只要遇到比它大的元素就往后挪一位直到找到合适的位置把当前元素放进去。这里有一个关键认知插入排序在几乎有序的数据上表现极其优秀时间复杂度能退化到O(n)。原因是内层循环一旦发现当前元素比前一个元素大就立即停止不需要完整遍历左侧的有序区间。对于近乎排好的数据这个特性让插入排序成为三种算法中最快的一种甚至在某些场景下可以和快排一战。另外你需要注意这里用的是往后挪而不是相邻交换。交换操作通常需要三次赋值而挪动只需要一次赋值。这个微小的差异在大数组上会被放大很多倍实际运行时间可能差出两到三倍。3. 源码实现与关键细节解析3.1 冒泡排序源码与优化版本先给出基础版本的冒泡排序实现def bubble_sort_basic(arr): n len(arr) for i in range(n - 1): for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] return arr外层循环range(n - 1)控制的是轮数。为什么是n - 1而不是n因为最后一轮只剩一个元素时它自然已经有序不需要再比较。内层循环range(n - 1 - i)里的-i就是前面说的区间缩短每轮冒出一个最大值末尾元素无需再参与比较。再看一个优化版本如果某一轮内层循环完全没有发生交换说明数组已经完全有序可以直接跳出。def bubble_sort_optimized(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break return arr这个优化在实际测试中非常有效。如果你对一个已经排好序的数组执行冒泡排序优化版本只需要跑一轮就能判断出有序并提前退出时间复杂度从O(n²)直接降到了O(n)。这个提前退出标志位的思路在很多其他算法里也可以复用比如判断一个数组是否完全有序时它同样能派上用场。3.2 选择排序源码与易错点选择排序的参考实现如下def selection_sort(arr): n len(arr) for i in range(n - 1): min_index i for j in range(i 1, n): if arr[j] arr[min_index]: min_index j if min_index ! i: arr[i], arr[min_index] arr[min_index], arr[i] return arr核心在于min_index这个变量。每一轮先将min_index初始化为当前轮次的起始位置i然后从i 1到末尾逐个比较每当发现更小的元素就更新min_index。内层循环结束后min_index就是最小元素所在的位置。如果min_index等于i说明当前位置已经是最小值无需交换。这个代码里最常见的错误是把min_index写成min_val然后在交换时使用arr.index(min_val)去查找下标。这个做法有两个问题首先是性能问题arr.index()本身就是一次O(n)的线性查找会额外增加时间开销其次是正确性问题当数组中有重复值时index()返回的是第一次出现的下标如果它已经排到了正确位置交换就会打乱原本的次序。选择排序是你学习的第一个不稳定排序算法。举个例子数组[5, 3, 5, 2]第一轮找出最小值2把它和第一个5交换原本两个5的相对顺序就被破坏了。这在只排序数字时无所谓但如果排序的是对象稳定性就可能变成硬性需求。3.3 插入排序源码与移位逻辑插入排序有两种常见写法先看使用while循环的版本def insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arrkey变量保存的是当前要插入的元素。while j 0 and arr[j] key是整个排序算法的灵魂它从右往左扫描有序区只要发现前一个元素比key大就把那个元素往后挪动一个位置。当循环结束时j指向的是第一个不大于key的元素位置因此key要放在j 1的位置。这里特别强调一点while j 0这个条件不能写成while arr[j] key因为当j变为-1时越界访问会直接报错。Python 的列表索引从 0 开始访问arr[-1]不会报错但指向的是列表的最后一个元素这个隐藏陷阱会导致逻辑错误非常难排查。另一个使用for循环的实现方式def insertion_sort_for(arr): n len(arr) for i in range(1, n): key arr[i] for j in range(i - 1, -1, -1): if arr[j] key: arr[j 1] arr[j] else: break else: j -1 arr[j 1] key return arr这段代码的for...else结构有点特殊。else分支只有在循环正常结束、没有遇到break时才会执行代表key比有序区所有元素都小此时j变成了-1。arr[j 1]就是arr[0]key会被放在数组头部。这个写法更能体现 Python 的for...else特性但对初学者不太友好我建议首先掌握while版本它的控制流更直观不容易出错。不过在循环结束后j的最终值两种写法需要仔细推敲我自己第一次用for...else版本时也在j的值上犯过迷糊。4. 实操过程测试环境、性能对比与复杂度分析4.1 环境准备与基础测试建议使用 Python 3.8 以上的版本不需要安装任何第三方库这三种排序算法的实现完全依赖标准库。开发工具选择上我比较推荐直接使用 Jupyter Notebook 来快速观察每一轮的中间结果它的单元格执行机制很适合教学展示。如果喜欢传统 IDEPyCharm 或者 VS Code 都可以。先做一个最基础的正确性验证使用包含正负数和小数的数组test_arr [3.2, -1, 4.5, 0, -2.5, 8, 1] print(bubble_sort_basic(test_arr[:])) print(selection_sort(test_arr[:])) print(insertion_sort(test_arr[:]))注意传递test_arr[:]而不是test_arr这是因为三种排序都是原地排序如果在同一个数组上连续调用第二次排序时数据已经是从小到大排好的无法真正检验算法的执行效果。切片[:]能快速生成一个副本。我建议新建一个专门的文件把三个排序函数和一个验证函数放在一起每次改动代码后直接运行。我平时写算法练习时会同步准备一个输出函数打印每一轮排序后的数组状态这样可以直观地看到元素是如何一步步被排到正确位置的。4.2 用随机数据做性能对比手写的算法需要和随机数据结合测试才能看出真实性能差距。我使用random模块生成规模不同的随机数数组import random import time def performance_test(sort_func, arr): start time.perf_counter() sort_func(arr) return time.perf_counter() - start sizes [500, 1000, 2000, 5000] for size in sizes: data [random.randint(0, 10000) for _ in range(size)] print(f数据规模: {size}) print(f冒泡: {performance_test(bubble_sort_basic, data[:]):.5f}s) print(f选择: {performance_test(selection_sort, data[:]):.5f}s) print(f插入: {performance_test(insertion_sort, data[:]):.5f}s) print(---)同样使用切片创建副本避免数据在第一个排序算法执行后就被打乱。由于随机数据对三种算法来说都是无序的测试结果能比较公平地反映出算法基本操作的常数因子差异。我在本地实测数据规模 5000 时冒泡排序大约需要 1.2 秒左右选择排序约 0.75 秒插入排序约 0.95 秒。到了数据规模 10000冒泡排序能跑到 4.5 秒以上选择约 3 秒插入约 3.8 秒。数据规模翻倍运行时间大约翻三到四倍这和 O(n²) 的时间复杂度变化趋势是吻合的。针对近乎有序的数据做一次单独测试更有意思almost_sorted list(range(5000)) for _ in range(50): i random.randint(0, 4999) j random.randint(0, 4999) almost_sorted[i], almost_sorted[j] almost_sorted[j], almost_sorted[i] print(f冒泡: {performance_test(bubble_sort_optimized, almost_sorted[:]):.5f}s) print(f选择: {performance_test(selection_sort, almost_sorted[:]):.5f}s) print(f插入: {performance_test(insertion_sort, almost_sorted[:]):.5f}s)在几乎有序的数据上插入排序的优势非常明显可能只需要 0.01 秒而选择排序依然需要接近完整排序的时间因为选择排序无论如何都要遍历完整个区间来找最小值无法提前终止。这个测试解释了为什么在很多实际项目中插入排序会作为高级排序算法的一种优化手段在数据规模不大或接近有序时被用作兜底方案。4.3 稳定性、原地性与复杂度对照整理一张对比表可以非常直观地看出三种算法的特性差异算法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性冒泡排序O(n²)O(n²)O(n)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(n)O(1)稳定空间复杂度 O(1) 意味着三者都是原地排序算法不需要额外分配与数据规模相关的存储空间。这一点在处理超大数组时非常重要因为内存占用不会成为瓶颈。稳定性这块我再说透一点。冒泡排序只在相邻元素比大小不符合预期时才交换相等的元素永远不会交换位置所以稳定。插入排序的元素依次向后挪动相等的元素不会越过前面的相等元素所以也稳定。选择排序则因为可能把远距离的最小值交换到前方很容易打乱相等元素的先后顺序所以不稳定。实际项目中什么场景需要稳定性最常见的是按多个字段排序。比如一个员工列表先按部门排序再按入职时间排序如果算法不稳定第二次排序会打乱第一次的结果。如果需要稳定的排序算法Python 内置的sorted()函数使用的 TimSort 就是稳定的这也解释了为什么你很少需要在业务代码里自己手写排序算法。5. 常见问题与错误排查实录5.1 索引越界和空数组处理写这三种排序时最容易碰到的运行时错误就是索引越界。拿插入排序举例while j 0 and arr[j] key:如果条件顺序写成while arr[j] key and j 0:当j变成-1时程序会先计算arr[-1]由于 Python 的列表索引支持负数它不会直接报越界错误而是读取列表的最后一个元素。这个行为比直接报错更隐蔽因为结果看起来没有崩溃但排序逻辑完全错乱。我之前帮人调试过这种问题代码跑起来不报错但输出结果莫名其妙排查了很久才发现是条件顺序的问题。空数组和只有一个元素的数组建议在函数开头加一个防御性判断def insertion_sort(arr): if len(arr) 1: return arr ...这段代码不算冗余。虽然不加它也能正常工作因为外层循环range(1, n)在n 1时不会执行任何迭代但加上判断后语义更清晰代码的鲁棒性更强尤其是当你的排序函数可能会被其他项目复用时防御性代码能减少很多隐患。5.2 返回值与原地排序的混淆这三个函数都是原地排序也就是说直接修改了传入的数组对象本身并没有生成新数组。函数末尾的return arr只是为了调用方便。有些新手会这样写new_list insertion_sort(old_list)然后惊讶地发现old_list也被修改了这不是 bug而是原地排序的本质特征。如果你需要一个新数组必须提前拷贝new_list insertion_sort(old_list[:])需要特别注意在 Python 中嵌套列表的拷贝需要copy.deepcopy简单的[:]只适用于一维的简单类型列表。如果你排序的是二维列表或者其他可变类型组成的列表浅拷贝会导致两个列表共享同一批子对象在排序过程中修改元素可能同时影响原始数据。5.3 数据类型不统一导致比较报错Python 的排序依赖和运算符如果列表中混入了不同类型的数据比如数字和字符串混在一起Python 3 会直接抛出TypeError: not supported between instances of str and int。这个问题在真实业务场景中经常出现。比如从 CSV 或者数据库中读取数据有些数值被读成了字符串类型直接丢进排序函数就会报错。我的建议是排序前先对数据类型做一次校验或者清洗def validate_numeric_list(arr): if any(not isinstance(x, (int, float)) for x in arr): raise ValueError(列表中必须全部为数值类型)也可以直接使用列表推导式把数据统一转换arr [float(x) for x in raw_data]不过这种强制转换要确认数据本身能被解析成数值格式不然会抛出新的异常。最稳妥的方式是在数据源阶段就做好类型检查而不是等排序函数报错后才回头看数据长什么样。5.4 排序算法不稳定带来的隐蔽问题稳定性问题在纯数值排序里看不见摸不着因为两个相等的数字不可区分。但当你排序的是元组、对象或者字典列表时稳定性就有了实际意义。我举个例子你有这样一个列表students [(A, 90), (B, 80), (C, 90)]你想先按分数排序如果分数相同希望保留原来的先后顺序。这时你用选择排序就可能出现相同分数的学生顺序被调换。这个调换在业务上是不可接受的比如学生名单本身有自己的编号顺序排序后编号被打乱就可能引发后续数据处理问题。如果必须使用不稳定的排序算法一个补救思路是给元素附加原始下标students_with_index [(s, i) for i, s in enumerate(students)]然后再排序时把下标也纳入比较逻辑当主要排序键相等时用下标作为次级排序键来保持原始顺序。这个方法在面试中也算是一个常见的延伸考点。5.5 优化过度导致的可读性问题最后一个要分享的经验是不要一开始就追求最复杂的优化写法。学习阶段应该先写能正确运行的清晰版本理清主逻辑后再引入优化。我见过很多新手在学冒泡排序时第一版就把提前退出标志位写进去了结果由于标志位的更新位置错误反而排错。等确认基础版本能正确排序后再添加swapped标志并且测试优化前后结果一致这才是稳妥的学习路径。插入排序也类似先用容易理解的while版本跑通再去琢磨for...else的写法。这三种算法是典型的看起来简单但你永远不知道哪里会出问题的代码。我个人在带项目时看到面试者能把插入排序一次写对、条件顺序正确、边界处理完整就会认为这个人的基本功比较扎实。建议你在阅读这篇内容的同时合上代码自己手动写一遍然后再对照文中的源码检查差异这样记忆会更深刻。另外这三个排序都不是终点。它们可以自然过渡到更多进阶排序算法的学习。比如理解了插入排序的局部有序和移位思想再去看希尔排序就不会太吃力理解了冒泡排序的相邻交换特性再去研究快速排序的划分过程也有帮助。先稳稳掌握这三大基础排序后续学高级算法会事半功倍。
