什么是冒泡排序，用C语言简单实现

冒泡排序是一种简单的排序算法，通过重复遍历数组并交换相邻元素来排序。其核心思想是将较大的元素逐渐“浮”到数组末端。以下是其原理和C语言实现：

**冒泡排序原理**
1. **比较相邻元素**：从数组第一个元素开始，比较相邻的两个元素。
2. **交换顺序**：如果前一个元素大于后一个元素，则交换它们。
3. **重复遍历**：每轮遍历会将当前未排序部分的最大元素“冒泡”到末尾。遍历次数逐渐减少（因末尾已排序部分无需再比较）。
4. **终止条件**：所有元素有序时结束。

时间复杂度：
- 最优情况（已有序）：\(O(n)\)
- 平均和最坏情况：\(O(n^2)\)

**C语言实现**
c #include <stdio.h> void bubble_sort(int arr[], int n) { int i, j, temp; for (i = 0; i < n - 1; i++) { // 控制遍历轮数 for (j = 0; j < n - i - 1; j++) { // 每轮比较次数递减 if (arr[j] > arr[j + 1]) { // 相邻元素比较 // 交换元素 temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度 bubble_sort(arr, n); // 调用排序函数 printf("Sorted array: \n"); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); // 输出排序结果 } return 0; }

**代码说明**
1. **外层循环**：共需 `n-1` 轮遍历（`i` 从 `0` 到 `n-2`）。
2. **内层循环**：每轮比较 `n-i-1` 次，避免重复比较已排序部分。
3. **元素交换**：通过临时变量 `temp` 完成相邻元素的交换。
4. **示例测试**：对数组 `{64, 34, 25, 12, 22, 11, 90}` 排序后输出有序结果。

**优化建议**
可增加标志变量 `swapped`，若某轮未发生交换则提前终止排序，优化时间复杂度至 \(O(n)\)（针对已有序数组）：
c void bubble_sort_optimized(int arr[], int n) { int i, j, temp, swapped; for (i = 0; i < n - 1; i++) { swapped = 0; for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = 1; } } if (!swapped) break; // 无交换则已有序，提前退出 } }

冒泡排序虽简单，但效率较低，适用于小规模数据或教学示例。