目录
介绍
冒泡排序是一种简单直观的排序算法，其核心思想是通过相邻元素比较和交换，使较大（或较小）的元素逐渐"浮"到数列的一端。本文以升序排列讲解，即每次遍历都会找出当前未排序区的最大元素放到已排序区。
算法工作原理
相邻元素比较：从数组的第一个元素开始，依次比较相邻的两个元素
交换位置：如果前一个元素大于后一个元素，则交换它们的位置（升序排序）
重复遍历：对数组进行多轮遍历，每轮遍历都会使当前未排序部分的最大元素"冒泡"到正确位置
终止条件：当某一轮遍历中没有发生任何交换时，说明数组已完全有序
算法流程图
算法可视化展示
算法分步详解
流程图解析
接下来以数组arr[8] = { 29,42,34,28,34,29,16,41 }来分步详解。
数组arr；数组长度n=8；
外层循环下标i初始值为0，满足i < n-1,每结束一次外层循环i++,直至不满足外层循环条件退出；
内层循环下标j初始值为0，满足 j < n-1-i，没结束一次内层循环j++,直至不满足内层循环条件退出;
标志位swapped用来标记此次内层循环是否存在元素交换，swapped在开始新的内层循环前被初始值为false,在内层循环中只要有元素交换，则被赋值为swapped。需要强调的是，整个数组可以被划分为未排序区+已排序区，如果在一整个内层循环，都没有元素交换，那么说明未排序区已经是有序的了；已排序区肯定是有序的；继而整个数组也是有序的了。因此，swapped可以用来快速验证数组是否排序完成，退出外循环，从而不必遍历外循环的所有i。对于那些原本就已经是"接近排序完成的数组"，这可以缩短很多时间。
算法推演
以下是数组arr[8] = { 29,42,34,28,34,29,16,41 }初始化时的状态。
初始化i= 0,swapped=true，满足外循环条件，另swapped=false,j=0,开始一次内循环
在内循环中，此时j = 0,满足条件j < n - 1- i (此时i=0)
比较arr[0]和arr[1],29 < 42,不满足交换条件 swapped还是false
j++后变成1，继续比较arr[1]和arr[2]
此时42 > 34，满足交换条件，进行交换；同时令swapped=true
交换后如下所示
j++后变成2，继续比较arr[2]和arr[3]
42 > 28,满足交换条件，交换；同时令swapped=true
交换后如下图
j++后变成3，继续比较arr[3]和arr[4]
42 > 34 满足交换条件，执行交换；同时令swapped=true
交换后如下图
j++后变成4，继续比较arr[4]和arr[5]
42 > 29 满足交换条件，执行交换；同时令swapped=true
交换后如下图
j++后变成5，继续比较arr[5]和arr[6]
42 > 16 满足交换条件，执行交换；同时令swapped=true
交换后如下图
j++后变成6，继续比较arr[6]和arr[7]
42 > 41 满足交换条件，执行交换；同时令swapped=true
交换后如下图
j++后变成7 不满足j < n-1-i(n=8,i=0),则此次内循环结束；找到了未排序区中最大的一个，放置到已排序区中。接下来i++，(如果满足外循环条件)开启下一次外循环
最终排序完成后的数据顺序如下
算法特性分析
时间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最优情况 | O(n) | 当输入数组已经完全有序时，优化代码(带swapped标志)只需一次遍历即可完成 |
| 平均情况 | O(n²) | 需要执行 n(n-1)/2 次比较操作 |
| 最坏情况 | O(n²) | 当输入数组完全逆序时，需要完整执行所有遍历 总比较次数为：(n-1)+(n-2)+...+1 = n(n-1)/2 |
空间复杂度
| 复杂度 | 值 | 说明 |
|---|---|---|
| 空间复杂度 | O(1) | 原地排序算法，只需要常数级别的额外空间(i,j,swapped) |
稳定性
| 特性 | 结果 | 说明 |
|---|---|---|
| 稳定性 | 稳定 | 相等元素不会交换位置 |
// // 只有在前元素大于后元素时才交换(相等时，不会交换)
if (arr[j] > arr[j + 1])
{
// 交换操作
}当
arr[j] == arr[j+1]时，条件不成立，不会执行交换相等元素保持原有相对顺序
不会改变相同值元素的原始位置关系
C语言实现
#include <stdio.h>
#include <stdbool.h> // 使用布尔类型
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void BubbleSort(int arr[], int n) {
bool swapped; // 标记是否发生交换
for (int i = 0; i < n - 1; i++) {
swapped = false; // 每轮开始前重置标记
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 标记发生交换
}
}
// 如果本轮没有发生交换，说明数组已有序
if (!swapped) {
break;
}
}
}
int main() {
int arr[] = { 29,42,34,28,34,29,16,41 }; // 基本有序的数组
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组: ");
printArray(arr, n);
BubbleSort(arr, n);
printf("排序后数组: ");
printArray(arr, n);
return 0;
}代码输出
