Python 算法基础篇之排序算法（一）：冒泡、选择、插入

1. 前言为什么从排序算法开始排序Sorting是计算机科学中最基础、最核心的算法问题之一。无论是数据库索引、搜索引擎结果展示还是日常开发中的数据展示都离不开排序。经典问题给定一个长度为 n 的整数数组如何将其按升序排列本文将深入讲解三种最基础的排序算法冒泡排序、选择排序、插入排序。它们虽然时间复杂度都是 O(n^2)但在特定场景下仍有应用价值更重要的是——它们是理解更高级排序算法快速排序、归并排序、堆排序的必经之路。本文学习目标✅ 理解三种排序算法的核心思想和执行流程✅ 能够手写完整代码并分析时间/空间复杂度✅ 通过可视化图示直观理解排序过程✅ 掌握算法稳定性、原地排序等核心概念排序算法分类总览2. 冒泡排序Bubble Sort2.1 算法思想冒泡排序的名字非常形象就像水中的气泡一样较大的元素会逐渐浮到数组的末尾。核心操作重复地走访要排序的序列一次比较两个相邻的元素如果它们的顺序错误就把它们交换过来。2.2 算法步骤详解初始数组[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]第1趟i0从左到右比较相邻元素将最大元素冒泡到最后3-44 44-38 38-5 5-47 47-15 47-36 47-26 47-27 47-2 47-46 47-4 47-19 47-50 50-48结果[3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50] - 50已就位第2趟i1在[0, n-2]范围内重复将次大元素放到倒数第2位…结果[3, 5, 38, 15, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50] - 48已就位…第n-1趟只剩一个元素自然有序2.3 可视化图示冒泡排序过程动态演示上图展示了冒泡排序的核心过程绿色方块当前正在比较/交换的元素对蓝色方块尚未排序的元素橙色方块已经排序到位的最大元素每一轮将当前未排序部分的最大值冒泡到正确位置2.4 完整代码实现defbubble_sort(arr:list)-list:nlen(arr)# 外层循环控制排序趟数共需 n-1 趟foriinrange(n-1):# 优化标志如果本趟没有交换说明已经有序swappedFalse# 内层循环控制每趟比较的次数# 第 i 趟只需比较到 n-i-1后面的 i 个元素已排好forjinrange(n-i-1):# 比较相邻元素ifarr[j]arr[j1]:# 交换位置arr[j],arr[j1]arr[j1],arr[j]swappedTrue# 优化如果本趟没有发生交换提前结束ifnotswapped:breakreturnarr# 测试与验证 if__name____main__:# 测试数据test_data[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]print(f原始数组:{test_data})sorted_databubble_sort(test_data.copy())print(f排序结果:{sorted_data})# 验证正确性assertsorted_datasorted(test_data)print(验证通过)2.5 复杂度分析指标复杂度说明最好时间O(n)数组已有序只需1趟比较最坏时间O(n^2)数组逆序需 n-1 趟平均时间O(n^2)随机数组空间复杂度O(1)原地排序稳定性稳定相等元素不交换2.6 算法优化鸡尾酒排序双向冒泡defcocktail_sort(arr:list)-list:nlen(arr)left,right0,n-1whileleftright:# 正向冒泡将最大值移到 right 位置new_rightleftforiinrange(left,right):ifarr[i]arr[i1]:arr[i],arr[i1]arr[i1],arr[i]new_righti rightnew_right# 反向冒泡将最小值移到 left 位置new_leftrightforiinrange(right,left,-1):ifarr[i]arr[i-1]:arr[i],arr[i-1]arr[i-1],arr[i]new_lefti leftnew_leftreturnarr3. 选择排序Selection Sort3.1 算法思想选择排序的核心思想非常直观每一趟从剩余未排序元素中选择最小或最大的元素放到已排序序列的末尾。就像打牌时每次从牌堆中选出最小的一张依次放到手中。3.2 算法步骤详解初始数组[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]第0趟在[0, 14]中找最小值 2与 a[0]3 交换- [2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]第1趟在[1, 14]中找最小值 3与 a[1]44 交换- [2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]第2趟在[2, 14]中找最小值 4与 a[2]38 交换- [2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]…第13趟在[13, 14]中找最小值 48与 a[13]50 交换- [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]3.3 可视化图示选择排序过程演示上图展示了选择排序的核心特征每轮从未排序区间中找到最小元素将其与未排序区间的第一个元素交换已排序区间逐渐扩大未排序区间逐渐缩小3.4 完整代码实现defselection_sort(arr:list)-list:nlen(arr)# 外层循环控制已排序部分的边界# i 表示当前要放置第 i 小元素的位置foriinrange(n-1):# 假设当前位置 i 的元素就是最小值min_idxi min_valuearr[i]# 内层循环在[i, n-1]范围内寻找真正的最小值forjinrange(i1,n):ifarr[j]min_value:min_valuearr[j]min_idxj# 将找到的最小值与位置 i 的元素交换# 注意如果 min_idx i说明 i 位置已经是最小值无需交换ifmin_idx!i:arr[i],arr[min_idx]arr[min_idx],arr[i]returnarr# 测试与验证 if__name____main__:test_data[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]print(f原始数组:{test_data})sorted_dataselection_sort(test_data.copy())print(f排序结果:{sorted_data})assertsorted_datasorted(test_data)print(验证通过)3.5 复杂度分析指标复杂度说明最好时间O(n^2)比较次数固定最坏时间O(n^2)比较次数固定平均时间O(n^2)比较次数固定空间复杂度O(1)原地排序稳定性不稳定跨距离交换破坏稳定性稳定性破坏示例[5, 8, 5, 2]第一次选择最小值 2 与第一个 5 交换两个 5 的相对顺序改变。3.6 双向选择排序每次找最大和最小defbidirectional_selection_sort(arr:list)-list:left,right0,len(arr)-1whileleftright:min_idx,max_idxleft,right# 在[left, right]范围内找最小和最大foriinrange(left,right1):ifarr[i]arr[min_idx]:min_idxiifarr[i]arr[max_idx]:max_idxi# 最小值放左边arr[left],arr[min_idx]arr[min_idx],arr[left]# 如果最大值恰好在 left 位置上面交换后它到了 min_idxifmax_idxleft:max_idxmin_idx# 最大值放右边arr[right],arr[max_idx]arr[max_idx],arr[right]left1right-1returnarr4. 插入排序Insertion Sort4.1 算法思想插入排序的灵感来自我们整理扑克牌的方式将未排序的元素逐个插入到已排序序列的合适位置。就像摸牌一样每次摸到一张新牌从后往前找到合适的位置插入。4.2 算法步骤详解初始数组[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]第1张牌 a[0]3手中只有一张牌自然有序手中[3] | 牌堆[44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]第2张牌 a[1]44比3大放后面手中[3, 44] | 牌堆[38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]第3张牌 a[2]38从后往前比较443844后移338停止手中[3, 38, 44] | 牌堆[5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]第4张牌 a[3]5445后移385后移35停止手中[3, 5, 38, 44] | 牌堆[47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]…第15张牌 a[14]48插入到合适位置手中[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] | 牌堆[]4.3 可视化图示插入排序过程演示上图展示了插入排序的核心过程已排序区间灰色背景已经排好序的部分当前元素蓝色高亮正在插入的元素后移操作将大于当前元素的已排序元素依次后移一位插入位置找到正确位置后插入当前元素4.4 完整代码实现definsertion_sort(arr:list)-list:nlen(arr)# 从第2个元素开始下标1逐个插入已排序部分foriinrange(1,n):# 当前要插入的元素摸到的牌currentarr[i]# 在已排序部分[0, i-1]中从后往前找插入位置ji-1# 将大于 current 的元素依次后移whilej0andarr[j]current:arr[j1]arr[j]# 后移j-1# 找到插入位置放入 currentarr[j1]currentreturnarr# 更直观的实现带注释版definsertion_sort_verbose(arr:list)-list:nlen(arr)foriinrange(1,n):# 第 i 张牌当前要处理的元素valuearr[i]insert_idx0# 默认插入到最前面# 从后往前扫描已排序部分 [0, i-1]forjinrange(i-1,-1,-1):ifarr[j]value:# 当前元素比 value 大需要后移arr[j1]arr[j]else:# 找到插入位置arr[j] value插在 j1 处insert_idxj1break# 插入元素arr[insert_idx]valuereturnarr# 测试与验证 if__name____main__:test_data[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]print(f原始数组:{test_data})sorted_datainsertion_sort(test_data.copy())print(f排序结果:{sorted_data})assertsorted_datasorted(test_data)print(验证通过)4.5 复杂度分析指标复杂度说明最好时间O(n)数组已有序最坏时间O(n^2)数组逆序平均时间O(n^2)随机数组空间复杂度O(1)原地排序稳定性稳定相等元素不移动4.6 插入排序的优势场景deftest_partial_sorted():importrandomimporttime# 生成几乎有序的数组90%元素已有序n10000arrlist(range(n))# 随机交换少量元素for_inrange(n//10):i,jrandom.randint(0,n-1),random.randint(0,n-1)arr[i],arr[j]arr[j],arr[i]# 测试插入排序starttime.time()insertion_sort(arr.copy())insert_timetime.time()-start# 测试快速排序starttime.time()sorted(arr.copy())quick_timetime.time()-startprint(f几乎有序数组 (n{n}):)print(f 插入排序耗时:{insert_time:.4f}s)print(f 快速排序耗时:{quick_time:.4f}s)# 插入排序通常更快# 实际应用Python 的 Timsortsorted() 底层# 当子数组长度较小时 64会退化为插入排序5. 三大基础排序算法对比总结5.1 核心特性对比表特性冒泡排序选择排序插入排序核心思想相邻比较大元素后移选最小元素放前面逐个插入已排序部分最好时间O(n)O(n^2)O(n)最坏时间O(n^2)O(n^2)O(n^2)平均时间O(n^2)O(n^2)O(n^2)空间复杂度O(1)O(1)O(1)稳定性稳定不稳定稳定比较次数O(n^2)固定 n(n-1)/2O(n^2)交换次数O(n^2)O(n)O(n^2)适用场景教学/小规模交换代价高时部分有序数据十大经典排序算法复杂度总览5.2 算法选择决策树数据规模小n 100 ├── 是 - 数据基本有序 │ ├── 是 - 插入排序O(n) │ └── 否 - 交换代价高如链表 │ ├── 是 - 选择排序O(n)次交换 │ └── 否 - 插入排序常数小 └── 否 - 使用高级排序快排/归并/堆排5.3 稳定性为什么重要稳定性排序后相等元素的相对顺序与排序前一致。实际应用示例# 学生成绩表先按班级排序再按成绩排序students[(A班,90),(B班,85),(A班,85),(C班,90),(B班,90),(A班,95)]# 使用稳定排序先按班级排# 再使用稳定排序按成绩排# 结果同成绩的学生班级顺序保持三大算法稳定性分析冒泡排序稳定。arr[j] arr[j1] 才交换相等不交换。选择排序不稳定。跨距离交换可能破坏相对顺序。插入排序稳定。arr[j] current 才后移相等不移动。6. 实战练习蓝桥云课 LQ3225 宝藏排序6.1 题目描述在一个神秘的岛屿上有一支探险队发现了一批宝藏这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字代表了其珍贵程度。然而由于某种神奇的力量这批宝藏的顺序被打乱了探险队需要将宝藏按照珍贵程度进行排序以便更好地研究和保护它们。作为探险队的一员肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。输入格式第一行整数 n宝藏数量第二行n 个整数表示每个宝藏的珍贵程度输出格式一行排序后的 n 个整数空格分隔样例输入 5 3 44 38 5 47 输出 3 5 38 44 476.2 三种算法 AC 代码解法一冒泡排序nint(input())alist(map(int,input().split()))foriinrange(1,n):forjinrange(n-i):ifa[j]a[j1]:a[j],a[j1]a[j1],a[j]print( .join(map(str,a)))解法二选择排序nint(input())alist(map(int,input().split()))foriinrange(0,n-1):min_valuea[i]min_idxiforjinrange(i,n):ifa[j]min_value:min_valuea[j]min_idxj a[i],a[min_idx]a[min_idx],a[i]print( .join(map(str,a)))解法三插入排序nint(input())alist(map(int,input().split()))foriinrange(1,n):valuea[i]insert_idx0forjinrange(i-1,-1,-1):ifa[j]value:a[j1]a[j]else:insert_idxj1breaka[insert_idx]valueprint( .join(map(str,a)))6.3 复杂度分析针对本题算法时间复杂度能否通过说明冒泡排序O(n^2)能n 10^3 时通常可过选择排序O(n^2)能同上插入排序O(n^2)能同上sorted()O(n log n)能Python 内置 Timsort推荐竞赛建议实际比赛中数据范围较大时n 10^4建议使用 sorted() 或手写快速排序。本文练习目的是掌握基础算法思想。结语本文详细讲解了三种基础排序算法算法核心口诀掌握要点冒泡排序“大元素往后冒泡”相邻比较、逐趟归位、提前终止优化选择排序“每趟选最小放前面”减少交换次数、但不稳定插入排序“像摸牌一样插入”部分有序时最优、稳定且高效思考题为什么快速排序最坏情况是 O(n^2)但实际应用中却比归并排序更常用下篇揭晓答案点赞 收藏 关注算法学习不迷路