1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
---
abbrlink: 403994443
categories:
- 往昔
date: "2025-05-10 20:06:05"
tags:
- 数据结构与算法
title: 【数据结构与算法】冒泡排序
---
## 核心思想
通过相邻元素的两两比较，将较大的元素逐步“冒泡”到数组末尾，每轮排序确定一个最大元素的最终位置。
## 代码实现
```c
void bubble_sort(int arr[], int n) {
// 最外层控制循环轮数 n-1轮
for (int i = 0; i < n - 1; i++) {
// 内层循环处理相邻元素比较和交换
for(int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
// 调用
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d,", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {23, 232, 55, 2, 7, 0, 576, 342};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前：");
print_array(arr, n);
bubble_sort(arr, n);
printf("排序后");
print_array(arr, n);
}
```
## 原理分析
### 外层循环的 i < n - 1
- n个元素的数组最多需要n-1轮冒泡，如5元素数组需要4轮排序
- **数学依据**：每轮将一个最大值“沉底”，当完成n-1轮时，最后一个元素必然有序
示例验证：
```
原始数组：[3, 1, 4, 2]
第一轮：[1, 3, 2, 4] （确定最大值4）
第二轮：[1, 2, 3, 4]
```
用文字解释上面的函数，原理就是在循环中对比数组第i个元素和i+1（即后一位）元素的大小，若i > i +1 则把两者交换位置，随着循环的进行，数组就会被排序。
### 内层循环的 j < n - i - 1
- 动态缩小范围：每轮结束后末尾i个元素已有序
- 比较次数：第i轮需要比较(n-1)-i次相邻元素
想象一下数组的线性结构，实际上就是在计算排序后的一位的前一位，这样就不会处理已经排序好的元素，进入下一轮循环时可正常排序。
### 数组长度n的计算机制
在main函数中，对于n的计算，采用了`sizeof(arr) / sizeof(arr[0])`的方式。可以这么理解。
```c
int arr[] = {6,4,8,2};
假设int占用4字节，计算整个数组的内存占用
sizeof(arr) = 5 * 4 = 20
sizeof(arr[0]) = 4
n = 20 / 4 = 5
```
计算出数组的总占用，再除以单个占用，就可以得到元素个数了。
### 参数n的作用
- 循环控制：确定外层循环次数n-1次
- 边界保护，防止越界
- 效率优化：避免无效比较，如j<n-i-1
## 最坏情况
冒泡排序的最坏情况发生在**输入数组完全逆序情况下**，此时算法需要进行最大次数的比较和交换操作，时间复杂度达到最高。
当待排序数组的初始状态为完全逆序，如[5,4,3,2,1]，每一轮外层循环都要将当前为排序部分的最大元素冒泡到正确位置，而且每次比较都会发生交换，此时：
- **比较次数**： 共需要进行*(n - 1) + (n - 2) + ...*（等差数列求和）。
- **交换次数**： 每次比较均需要交换，总交换次数也为上式结果。
|
