冒泡排序
在交换排序中，冒泡排序是最直观的一种，它经过相邻元素的两两比较和交换，让值较大的元素像水中的气泡一样逐步“上浮”到数组末尾，最终实现整个数组的有序排列。这种排序方式的核心是“逐趟筛选最大元素”，每完成一趟排序，就有一个最大元素被固定在正确的位置，后续排序无需再处理该元素。
1. 冒泡排序的核心思想与执行流程
冒泡排序的核心逻辑可能概括为“相邻比较、逆序交换、逐趟上浮”：
- 从数组的第一个元素开始，依次比较相邻的两个元素；
- 若前一个元素的值大于后一个元素的值（逆序），则交换这两个元素的位置；
- 每达成一轮（一趟）比较，数组中未排序部分的最大元素会“上浮”到未排序部分的末尾，成为已排序部分的第一个元素；
- 重复上述过程，直到某一趟排序中没有发生任何交换（说明数组已完全有序），或完成n-1趟排序（n为数组长度）。
我们以数组arr = {49, 38, 65, 97, 76, 13, 27, 49}为例，详细展示冒泡排序的每一趟执行过程：
初始数组：
[49, 38, 65, 97, 76, 13, 27, 49]（未排序部分为整个数组，长度8）第一趟排序（目标：将最大元素97上浮到末尾）：
- 比较49和38（逆序）→ 交换 →
[38, 49, 65, 97, 76, 13, 27, 49]； - 比较49和65（顺序）→ 不交换；
- 比较65和97（顺序）→ 不交换；
- 比较97和76（逆序）→ 交换 →
[38, 49, 65, 76, 97, 13, 27, 49]； - 比较97和13（逆序）→ 交换 →
[38, 49, 65, 76, 13, 97, 27, 49]； - 比较97和27（逆序）→ 交换 →
[38, 49, 65, 76, 13, 27, 97, 49]； - 比较97和49（逆序）→ 交换 →
[38, 49, 65, 76, 13, 27, 49, 97]。
第一趟结束，97被固定在末尾（已排序部分：[97]，未排序部分长度7）。
- 比较49和38（逆序）→ 交换 →
第二趟排序（目标：将未排序部分的最大元素76上浮到倒数第二位）：
按同样逻辑比较相邻元素，最终未排序部分的最大元素76会“上浮”到倒数第二位，数组变为[38, 49, 65, 13, 27, 49, 76, 97]（已排序部分：[76, 97]，未排序部分长度6）。后续趟次：
第三趟将65上浮到倒数第三位，数组变为[38, 49, 13, 27, 49, 65, 76, 97]；
第四趟将49（第一个49）上浮到倒数第四位，数组变为[38, 13, 27, 49, 49, 65, 76, 97]；
第五趟将38上浮到倒数第五位，数组变为[13, 27, 38, 49, 49, 65, 76, 97]；
第六趟比较时，所有相邻元素均为顺序，无任何交换，说明数组已完全有序，排序提前结束。
2. 冒泡排序的代码实现（带优化）
通过为了避免数组已有序时仍进行多余趟次的比较，我们能够添加一个“交换标志”（flag）：若某一趟排序中没有发生交换，则直接终止排序。以下是优化后的C语言达成，代码精简且注释详细：
void BubbleSort(int arr[], int n) {
int i, j, flag; // flag=1表示有交换，0表示无交换
for (i = 0; i < n-1; i++) { // 最多需n-1趟（每趟固定一个元素）
flag = 0; // 初始化为无交换
for (j = 0; j < n-1-i; j++) { // 未排序部分：0~n-1-i
if (arr[j] > arr[j+1]) { // 相邻元素逆序，交换
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1; // 标记有交换
}
}
if (flag == 0) break; // 无交换，数组已有序，提前终止
}
}代码说明：
- 外层循环
i控制排序趟次，最多执行n-1趟（每趟固定一个最大元素）； - 内层循环
j遍历未排序部分（范围0~n-1-i，因每趟后已排序部分增加1个元素）； - 交换标志
flag：若某趟无交换（flag=0），说明数组已完全有序，直接跳出循环，避免多余计算。
3. 冒泡排序的性能与特性
时间复杂度：
- 最好情况（数组已完全有序）：仅需1趟排序，无交换，时间复杂度为
O(n)； - 最坏情况（数组完全逆序）：需n-1趟排序，每趟比较n-1-i次，总比较次数为
n(n-1)/2，时间复杂度为O(n²)； - 平均情况：时间复杂度为
O(n²)。
- 最好情况（数组已完全有序）：仅需1趟排序，无交换，时间复杂度为
空间复杂度：仅需一个临时变量（temp）和交换标志（flag），空间复杂度为
O(1)，属于“原地排序”。稳定性：当相邻元素值相等时（如示例中的两个49），不会发生交换，因此相同元素的相对顺序不会改变，冒泡排序是稳定的排序算法。
4. 适用场景
冒泡排序适合以下场景：
- 数据量较小的数组（如n<100）：此时
O(n²)的时间复杂度可接受，且代码实现简单易维护； - 数组基本有序的场景：优化后的冒泡排序能通过“交换标志”快速终止，效率接近
O(n)； - 对排序稳定性有要求，且内存资源有限的场景：其稳定性和原地排序特性可满足需求。
综上，冒泡排序是一种逻辑直观、实现简单的交换排序算法，核心是通过相邻元素的比较与交换逐步筛选最大元素。虽然平均时间复杂度为O(n²)，但通过“交换标志”的优化，在基本有序数组上能表现出较高效率，且具备稳定、原地排序的优势，是学习交换排序思想的基础。