【算法】小白也能懂 · 第 7 节：排序算法入门（冒泡、选择、插入）

在前几节中，我们学习了时间与空间复杂度、双指针、链表反转、栈与队列、递归以及二分查找。这一节我们来认识一个最基础、最重要的算法类别——排序算法。掌握排序不仅能帮你解决大量实际问题，还能加深你对「比较」和「交换」这两个核心操作的理解。

1. 什么是排序

排序，就是把一组数据按照某种规则（通常是从小到大或从大到小）重新排列。比如考试成绩从高到低排名、通讯录按姓名拼音排序，本质上都是排序问题。接下来我们会学习三种最经典的入门排序算法：冒泡排序、选择排序和插入排序。

2. 冒泡排序

2.1 直觉理解

想象一排大小不一的气泡从水底往上冒。轻的（小的）气泡会不断和旁边重的（大的）气泡交换位置，最终重的气泡沉到下面，轻的浮到上面。冒泡排序的核心就是：反复比较相邻元素，如果顺序不对就交换，每一轮都会把当前未排序部分中最大的元素「冒」到最后。

2.2 手动模拟

以数组[5, 3, 8, 1, 2]为例：

第 1 轮：比较相邻元素，把最大值送到末尾

• 5 和 3 比 → 交换 →[3, 5, 8, 1, 2]
• 5 和 8 比 → 不换 →[3, 5, 8, 1, 2]
• 8 和 1 比 → 交换 →[3, 5, 1, 8, 2]
• 8 和 2 比 → 交换 →[3, 5, 1, 2, 8]，8 归位

第 2 轮：对前 4 个元素重复，把次大值送到倒数第二位

• 3 和 5 比 → 不换
• 5 和 1 比 → 交换 →[3, 1, 5, 2, 8]
• 5 和 2 比 → 交换 →[3, 1, 2, 5, 8]，5 归位

以此类推，直到所有元素有序。

2.3 C++ 实现

voidbubbleSort(vector<int>&arr){intn=arr.size();for(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1])