冒泡排序（Bubble Sort）详解
1. 什么是冒泡排序？
冒泡排序是一种基于比较的交换排序算法。
它的核心思想是：重复遍历待排序序列，依次比较相邻的两个元素，若顺序错误（逆序）则交换，直到没有逆序对为止。
每一轮遍历都会将当前未排序部分中的最大（或最小）元素“冒泡”到序列的末端，如同气泡从水底浮起，因此得名。
2. 算法步骤（以升序为例）
- 从数组第一个元素开始，依次比较相邻元素
arr[i]和arr[i+1]。 - 若
arr[i] > arr[i+1]，则交换两者位置。 - 继续向后比较，直到数组末尾。此时，整个序列的最大值已被交换到最后一位。
- 忽略已排好的最后一个元素，对剩余的前
n-1个元素重复上述过程。 - 每一轮结束后，未排序部分的最大值都会“冒泡”到正确位置。
- 重复
n-1轮（或直到某一轮未发生任何交换），排序结束。
3. 动态演示
4. 算法复杂度与稳定性
| 特性 | 值 |
|---|---|
| 最好时间复杂度 | O(n) —— 数组已有序（优化版） |
| 最坏时间复杂度 | O(n²) —— 数组完全逆序 |
| 平均时间复杂度 | O(n²) |
| 空间复杂度 | O(1) —— 原地排序，无需额外数组 |
| 稳定性 | 稳定—— 相等元素的相对顺序不变 |
5. 优缺点
优点
- 算法逻辑简单，易于理解和实现。
- 稳定排序，适合对稳定性有要求的场景。
- 原地排序，内存占用极低。
- 经过优化后，对近乎有序的数组效率很高（O(n)）。
缺点
- 平均和最坏时间复杂度均为 O(n²)，处理大规模数据时效率低下。
- 实际工程中几乎不被采用（仅作为教学或小规模数据排序）。
6. 示例代码
#include<stdio.h>#include<stdbool.h>// 优化版冒泡排序voidbubbleSort(intarr[],intn){for(inti=0;i<n-1;i++){bool flag=false;for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;flag=true;}}if(!flag)break;}}intmain(){intarr[]={5,8,6,3,9,2,1,7};intn=sizeof(arr)/sizeof(arr[0]);bubbleSort(arr,n);for(inti=0;i<n;i++)printf("%d ",arr[i]);// 输出：123456789return0;}
