programming

冒泡排序算法：最基础的交换排序技术

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历待排序序列，比较相邻元素并在顺序错误时交换它们。这个过程会持续进行，直到没有需要交换的元素为止，此时序列已经完全排序。

算法原理

基本思想

冒泡排序的名称来源于较小的元素会通过交换”冒泡”到数组的顶端，就像水中的气泡向上浮起一样。算法的核心思想是：

  1. 比较相邻元素：从数组开始位置依次比较相邻的两个元素
  2. 交换位置：如果前一个元素大于后一个元素，则交换它们的位置
  3. 重复遍历：重复这个过程，每次遍历都会将当前最大的元素移到正确位置
  4. 逐步完成：每次遍历后，已排序部分会增加一个元素

算法步骤

  1. 从第一个元素开始，比较相邻的两个元素
  2. 如果第一个比第二个大，就交换它们
  3. 继续对每一对相邻元素做同样的工作，直到最后一对
  4. 此时最大的元素已经”冒泡”到了最后位置
  5. 重复上述步骤，但每次减少一个比较（因为最大元素已确定位置）
  6. 持续到没有元素需要交换为止

优缺点分析

优点

  1. 实现简单：算法逻辑清晰，代码易于理解和实现
  2. 稳定排序：相等元素的相对位置不会改变
  3. 原地排序：只需要常数级额外空间
  4. 自适应性：对于已排序或近似排序的数据，优化版本可以提前终止

缺点

  1. 时间复杂度高：平均和最坏情况下都是O(n²)
  2. 效率低下：大量不必要的比较和交换操作
  3. 不适合大数据：对于大规模数据集性能很差
  4. 交换次数多：相比其他算法，需要更多的交换操作

使用场景

适用场景

  1. 教学目的：作为排序算法的入门教学
  2. 小规模数据：数据量很小时（通常小于20个元素）
  3. 近似有序数据：使用优化版本可以快速处理
  4. 内存严格限制：只需要O(1)额外空间的场景
  5. 稳定性要求：需要保持相等元素相对位置的应用

实际应用

  • 算法教学和演示
  • 简单的数据整理工具
  • 嵌入式系统中的小数据排序
  • 作为复杂排序算法的组成部分

C语言实现

基础版本

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

/**
 * 基础冒泡排序实现
 * @param arr 待排序数组
 * @param n 数组长度
 */
void bubble_sort_basic(int arr[], int n) {
    printf("执行基础冒泡排序...\n");
    
    for (int i = 0; i < n - 1; i++) {
        printf("第 %d 轮排序: ", 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 k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

/**
 * 优化版冒泡排序（添加提前终止条件）
 * @param arr 待排序数组
 * @param n 数组长度
 */
void bubble_sort_optimized(int arr[], int n) {
    printf("执行优化冒泡排序...\n");
    
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        printf("第 %d 轮排序: ", 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;
                swapped = true;
            }
        }
        
        // 打印每轮结果
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
        
        // 如果没有发生交换，数组已有序，提前退出
        if (!swapped) {
            printf("数组已有序，提前终止！\n");
            break;
        }
    }
}

/**
 * 双向冒泡排序（鸡尾酒排序）
 * @param arr 待排序数组
 * @param n 数组长度
 */
void cocktail_sort(int arr[], int n) {
    printf("执行双向冒泡排序（鸡尾酒排序）...\n");
    
    int left = 0;
    int right = n - 1;
    int round = 1;
    
    while (left < right) {
        bool swapped = false;
        
        // 向右冒泡（找最大值）
        printf("第 %d 轮向右冒泡: ", round);
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        right--; // 最大值已到位
        
        // 打印结果
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
        
        if (!swapped) break;
        
        // 向左冒泡（找最小值）
        printf("第 %d 轮向左冒泡: ", round);
        swapped = false;
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                swapped = true;
            }
        }
        left++; // 最小值已到位
        
        // 打印结果
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
        
        if (!swapped) break;
        round++;
    }
}

/**
 * 递归版本冒泡排序
 * @param arr 待排序数组
 * @param n 数组长度
 */
void bubble_sort_recursive(int arr[], int n) {
    // 基础情况：如果数组长度为1或0，已经有序
    if (n <= 1) return;
    
    // 执行一轮冒泡，将最大元素移到末尾
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
    
    // 递归处理前n-1个元素
    bubble_sort_recursive(arr, n - 1);
}

/**
 * 比较不同冒泡排序版本的性能
 */
void performance_comparison() {
    printf("=== 性能比较测试 ===\n");
    
    const int sizes[] = {100, 500, 1000};
    const int num_sizes = sizeof(sizes) / sizeof(sizes[0]);
    
    for (int s = 0; s < num_sizes; s++) {
        int size = sizes[s];
        printf("\n数组大小: %d\n", size);
        
        // 生成随机数据
        int* arr1 = (int*)malloc(size * sizeof(int));
        int* arr2 = (int*)malloc(size * sizeof(int));
        
        srand((unsigned int)time(NULL));
        for (int i = 0; i < size; i++) {
            arr1[i] = rand() % 1000;
            arr2[i] = arr1[i]; // 复制相同数据
        }
        
        // 测试基础版本
        clock_t start = clock();
        bubble_sort_basic(arr1, size);
        clock_t end = clock();
        double time_basic = ((double)(end - start)) / CLOCKS_PER_SEC;
        
        // 测试优化版本
        start = clock();
        bubble_sort_optimized(arr2, size);
        end = clock();
        double time_optimized = ((double)(end - start)) / CLOCKS_PER_SEC;
        
        printf("基础版本用时: %.6f 秒\n", time_basic);
        printf("优化版本用时: %.6f 秒\n", time_optimized);
        printf("性能提升: %.2f%%\n", 
               ((time_basic - time_optimized) / time_basic) * 100);
        
        free(arr1);
        free(arr2);
    }
}

/**
 * 验证排序正确性
 */
bool is_sorted(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

void print_array(int arr[], int size, const char* title) {
    printf("%s: ", title);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 测试函数
void test_bubble_sort_algorithms() {
    printf("=== 冒泡排序算法测试 ===\n\n");
    
    // 测试数据
    int test_data[] = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50};
    int size = sizeof(test_data) / sizeof(test_data[0]);
    
    // 测试基础冒泡排序
    printf("1. 基础冒泡排序测试\n");
    int* arr1 = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) arr1[i] = test_data[i];
    
    print_array(arr1, size, "排序前");
    bubble_sort_basic(arr1, size);
    print_array(arr1, size, "排序后");
    printf("排序正确性: %s\n\n", is_sorted(arr1, size) ? "正确" : "错误");
    free(arr1);
    
    // 测试优化冒泡排序
    printf("2. 优化冒泡排序测试\n");
    int* arr2 = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) arr2[i] = test_data[i];
    
    print_array(arr2, size, "排序前");
    bubble_sort_optimized(arr2, size);
    print_array(arr2, size, "排序后");
    printf("排序正确性: %s\n\n", is_sorted(arr2, size) ? "正确" : "错误");
    free(arr2);
    
    // 测试双向冒泡排序
    printf("3. 双向冒泡排序测试\n");
    int* arr3 = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) arr3[i] = test_data[i];
    
    print_array(arr3, size, "排序前");
    cocktail_sort(arr3, size);
    print_array(arr3, size, "排序后");
    printf("排序正确性: %s\n\n", is_sorted(arr3, size) ? "正确" : "错误");
    free(arr3);
    
    // 测试递归版本
    printf("4. 递归冒泡排序测试\n");
    int* arr4 = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) arr4[i] = test_data[i];
    
    print_array(arr4, size, "排序前");
    bubble_sort_recursive(arr4, size);
    print_array(arr4, size, "排序后");
    printf("排序正确性: %s\n\n", is_sorted(arr4, size) ? "正确" : "错误");
    free(arr4);
}

int main() {
    test_bubble_sort_algorithms();
    return 0;
}

算法复杂度分析

时间复杂度

  • 最好情况：O(n) - 数组已经有序（优化版本）
  • 平均情况：O(n²) - 随机排列的数组
  • 最坏情况：O(n²) - 数组逆序排列

空间复杂度

  • 空间复杂度：O(1) - 只需要常数级额外空间用于交换

稳定性

冒泡排序是稳定的排序算法，因为相等的元素不会被交换，保持了它们的相对位置。

算法改进和变种

1. 记录最后交换位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bubble_sort_last_exchange(int arr[], int n) {
    int last_exchange_pos = n - 1;
    
    while (last_exchange_pos > 0) {
        int new_pos = 0;
        for (int i = 0; i < last_exchange_pos; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                new_pos = i; // 记录最后交换位置
            }
        }
        last_exchange_pos = new_pos;
    }
}

2. 奇偶排序

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
void odd_even_sort(int arr[], int n) {
    bool sorted = false;
    
    while (!sorted) {
        sorted = true;
        
        // 奇数位置的比较
        for (int i = 1; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                sorted = false;
            }
        }
        
        // 偶数位置的比较
        for (int i = 0; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                sorted = false;
            }
        }
    }
}

实际应用示例

学生成绩排序系统

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
#include <stdio.h>
#include <string.h>

typedef struct {
    char name[50];
    int score;
    int id;
} Student;

void bubble_sort_students(Student students[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (students[j].score < students[j + 1].score) {
                // 交换学生记录
                Student temp = students[j];
                students[j] = students[j + 1];
                students[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

void print_students(Student students[], int n) {
    printf("学生排名:\n");
    printf("排名\t姓名\t\t学号\t成绩\n");
    printf("------------------------------------\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%s\t\t%d\t%d\n", 
               i + 1, students[i].name, students[i].id, students[i].score);
    }
}

void test_student_sorting() {
    Student students[] = {
        {"张三", 85, 1001},
        {"李四", 92, 1002},
        {"王五", 78, 1003},
        {"赵六", 95, 1004},
        {"孙七", 88, 1005}
    };
    
    int n = sizeof(students) / sizeof(students[0]);
    
    printf("排序前:\n");
    print_students(students, n);
    
    bubble_sort_students(students, n);
    
    printf("\n排序后:\n");
    print_students(students, n);
}

总结

冒泡排序虽然在实际应用中很少使用，但它是理解排序算法的重要基础。通过学习冒泡排序，我们可以：

  1. 理解排序的基本概念：比较、交换、稳定性等
  2. 掌握算法优化思想：如何通过简单的改进提升性能
  3. 学习复杂度分析：时间和空间复杂度的概念
  4. 为学习高级排序算法打基础：为快速排序、归并排序等做准备

冒泡排序的价值在于其教学意义，它帮助初学者建立对排序算法的直观理解，是学习更复杂排序算法的重要踏脚石。

版权所有，如有侵权请联系我