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

1. 前言：为什么从排序算法开始？

排序（Sorting）是计算机科学中最基础、最核心的算法问题之一。无论是数据库索引、搜索引擎结果展示，还是日常开发中的数据展示，都离不开排序。

经典问题：给定一个长度为 n 的整数数组，如何将其按升序排列？

本文将深入讲解三种最基础的排序算法：冒泡排序、选择排序、插入排序。它们虽然时间复杂度都是 O(n^2)，但在特定场景下仍有应用价值，更重要的是——它们是理解更高级排序算法（快速排序、归并排序、堆排序）的必经之路。

本文学习目标：

• ✅ 理解三种排序算法的核心思想和执行流程
• ✅ 能够手写完整代码并分析时间/空间复杂度
• ✅ 通过可视化图示直观理解排序过程
• ✅ 掌握算法稳定性、原地排序等核心概念

排序算法分类总览：

2. 冒泡排序（Bubble Sort）

2.1 算法思想

冒泡排序的名字非常形象：就像水中的气泡一样，较大的元素会逐渐浮到数组的末尾。

核心操作：重复地走访要排序的序列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

2.2 算法步骤详解

初始数组：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

第1趟（i=0）：从左到右比较相邻元素，将最大元素冒泡到最后
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趟（i=1）：在[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:n=len(arr)# 外层循环控制排序趟数，共需 n-1 趟foriinrange(n-1):# 优化标志：如果本趟没有交换，说明已经有序swapped=False# 内层循环控制每趟比较的次数# 第 i 趟只需比较到 n-i-1（后面的 i 个元素已排好）forjinrange(n-i-1):# 比较相邻元素ifarr[j]>arr[j+1]:# 交换位置arr[j],arr[j+1]=arr[j+1],arr[j]swapped=True# 优化：如果本趟没有发生交换，提前结束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_data=bubble_sort(test_data.copy())print(f"排序结果:{sorted_data}")# 验证正确性assertsorted_data==sorted(test_data)print("验证通过！")

2.5 复杂度分析

2.6 算法优化：鸡尾酒排序（双向冒泡）

defcocktail_sort(arr:list)->list:n=len(arr)left,right=0,n-1whileleft<right:# 正向冒泡：将最大值移到 right 位置new_right=leftforiinrange(left,right):ifarr[i]>arr[i+1]:arr[i],arr[i+1]=arr[i+1],arr[i]new_right=i right=new_right# 反向冒泡：将最小值移到 left 位置new_left=rightforiinrange(right,left,-1):ifarr[i]<arr[i-1]:arr[i],arr[i-1]=arr[i-1],arr[i]new_left=i left=new_leftreturnarr

3. 选择排序（Selection Sort）

3.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:n=len(arr)# 外层循环：控制已排序部分的边界# i 表示当前要放置第 i 小元素的位置foriinrange(n-1):# 假设当前位置 i 的元素就是最小值min_idx=i min_value=arr[i]# 内层循环：在[i, n-1]范围内寻找真正的最小值forjinrange(i+1,n):ifarr[j]<min_value:min_value=arr[j]min_idx=j# 将找到的最小值与位置 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_data=selection_sort(test_data.copy())print(f"排序结果:{sorted_data}")assertsorted_data==sorted(test_data)print("验证通过！")

3.5 复杂度分析

稳定性破坏示例：[5, 8, 5, 2]，第一次选择最小值 2 与第一个 5 交换，两个 5 的相对顺序改变。

3.6 双向选择排序（每次找最大和最小）

defbidirectional_selection_sort(arr:list)->list:left,right=0,len(arr)-1whileleft<right:min_idx,max_idx=left,right# 在[left, right]范围内找最小和最大foriinrange(left,right+1):ifarr[i]<arr[min_idx]:min_idx=iifarr[i]>arr[max_idx]:max_idx=i# 最小值放左边arr[left],arr[min_idx]=arr[min_idx],arr[left]# 如果最大值恰好在 left 位置，上面交换后它到了 min_idxifmax_idx==left:max_idx=min_idx# 最大值放右边arr[right],arr[max_idx]=arr[max_idx],arr[right]left+=1right-=1returnarr

4. 插入排序（Insertion Sort）

4.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：从后往前比较，44>38，44后移；3<38，停止
手中：[3, 38, 44] | 牌堆：[5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

第4张牌 a[3]=5：44>5后移，38>5后移，3<5停止
手中：[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:n=len(arr)# 从第2个元素开始（下标1），逐个插入已排序部分foriinrange(1,n):# 当前要插入的元素（摸到的牌）current=arr[i]# 在已排序部分[0, i-1]中从后往前找插入位置j=i-1# 将大于 current 的元素依次后移whilej>=0andarr[j]>current:arr[j+1]=arr[j]# 后移j-=1# 找到插入位置，放入 currentarr[j+1]=currentreturnarr# ========== 更直观的实现（带注释版）==========definsertion_sort_verbose(arr:list)->list:n=len(arr)foriinrange(1,n):# 第 i 张牌（当前要处理的元素）value=arr[i]insert_idx=0# 默认插入到最前面# 从后往前扫描已排序部分 [0, i-1]forjinrange(i-1,-1,-1):ifarr[j]>value:# 当前元素比 value 大，需要后移arr[j+1]=arr[j]else:# 找到插入位置：arr[j] <= value，插在 j+1 处insert_idx=j+1break# 插入元素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_data=insertion_sort(test_data.copy())print(f"排序结果:{sorted_data}")assertsorted_data==sorted(test_data)print("验证通过！")

4.5 复杂度分析

4.6 插入排序的优势场景

deftest_partial_sorted():importrandomimporttime# 生成几乎有序的数组（90%元素已有序）n=10000arr=list(range(n))# 随机交换少量元素for_inrange(n//10):i,j=random.randint(0,n-1),random.randint(0,n-1)arr[i],arr[j]=arr[j],arr[i]# 测试插入排序start=time.time()insertion_sort(arr.copy())insert_time=time.time()-start# 测试快速排序start=time.time()sorted(arr.copy())quick_time=time.time()-startprint(f"几乎有序数组 (n={n}):")print(f" 插入排序耗时:{insert_time:.4f}s")print(f" 快速排序耗时:{quick_time:.4f}s")# 插入排序通常更快！# 实际应用：Python 的 Timsort（sorted() 底层）# 当子数组长度较小时（<< 64），会退化为插入排序

5. 三大基础排序算法对比总结

5.1 核心特性对比表

十大经典排序算法复杂度总览：

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[j+1] 才交换，相等不交换。
• 选择排序：不稳定。跨距离交换可能破坏相对顺序。
• 插入排序：稳定。arr[j] > current 才后移，相等不移动。

6. 实战练习：蓝桥云课 LQ3225 宝藏排序

6.1 题目描述

在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩需要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。

输入格式：

• 第一行：整数 n（宝藏数量）
• 第二行：n 个整数，表示每个宝藏的珍贵程度

输出格式：

• 一行，排序后的 n 个整数，空格分隔

样例：

输入： 5 3 44 38 5 47 输出： 3 5 38 44 47

6.2 三种算法 AC 代码

解法一：冒泡排序

n=int(input())a=list(map(int,input().split()))foriinrange(1,n):forjinrange(n-i):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]print(' '.join(map(str,a)))

解法二：选择排序

n=int(input())a=list(map(int,input().split()))foriinrange(0,n-1):min_value=a[i]min_idx=iforjinrange(i,n):ifa[j]<min_value:min_value=a[j]min_idx=j a[i],a[min_idx]=a[min_idx],a[i]print(' '.join(map(str,a)))

解法三：插入排序

n=int(input())a=list(map(int,input().split()))foriinrange(1,n):value=a[i]insert_idx=0forjinrange(i-1,-1,-1):ifa[j]>value:a[j+1]=a[j]else:insert_idx=j+1breaka[insert_idx]=valueprint(' '.join(map(str,a)))

6.3 复杂度分析（针对本题）

竞赛建议：实际比赛中，数据范围较大时（n > 10^4）建议使用 sorted() 或手写快速排序。本文练习目的是掌握基础算法思想。

结语

本文详细讲解了三种基础排序算法：

思考题：为什么快速排序最坏情况是 O(n^2)，但实际应用中却比归并排序更常用？下篇揭晓答案！

点赞 + 收藏 + 关注，算法学习不迷路！