C 语言算法详解：冒泡排序从原理到优化的完整实现

1. 算法原理与命名由来

冒泡排序（Bubble Sort） 是一种最基础的交换类排序算法。其核心思想是通过多次遍历数组，比较相邻元素并交换位置，使较大的元素逐步 “冒泡” 到数组的末尾。

核心步骤：

2. 基础版冒泡排序实现

#include <stdio.h>

int main() {
int arr[] = {5, 3, 8, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);

// 外层循环控制排序轮数
for (int i = 0; i < n – 1; i++) {
// 内层循环进行相邻元素比较与交换
// 每轮结束后，最大的i+1个元素已归位，无需再比较
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;
}
}
}

// 输出排序后的数组
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

3. 带标志位的优化版本

基础版冒泡排序存在效率问题：即使数组在某一轮遍历后已经完全有序，算法仍会继续执行后续的无用轮次。通过引入一个标志位（Flag），可以检测本轮是否发生了交换，从而提前终止排序。

#include <stdio.h>

int main() {
int arr[] = {1, 2, 3, 4, 5}; // 已排序数组
int n = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < n – 1; i++) {
int swapped = 0; // 标志位，0表示本轮无交换
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 = 1; // 标记本轮发生了交换
}
}
if (swapped == 0) {
break; // 数组已完全有序，提前退出
}
}

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}

4. 时间复杂度分析

冒泡排序是一种稳定的排序算法，但由于其平方级的时间复杂度，通常仅适用于小规模数据的排序场景。

5. 总结与应用场景

• 核心优势：实现简单，逻辑直观，是理解排序算法的入门首选。

• 主要缺点：时间复杂度高，不适用于大数据量。

• 适用场景：