C语言冒泡排序算法详解与实现

引言

排序算法是计算机科学中最基础也是最重要的算法之一。在众多排序算法中，冒泡排序（Bubble Sort）以其简单直观的特点，成为许多编程初学者的入门首选。本文将详细介绍C语言中冒泡排序的实现原理、代码实现以及相关的优化技巧。

算法原理

基本概念

冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行，直到没有再需要交换的元素为止。

工作原理

冒泡排序的工作原理可以通过以下步骤理解：

1. 比较相邻元素：从第一个元素开始，比较相邻的两个元素
2. 交换位置：如果前一个元素大于后一个元素（升序排序），则交换它们的位置
3. 重复过程：继续向下一对相邻元素重复此过程，直到到达数列末尾
4. 多轮排序：重复以上步骤，每次都会将最大的元素”冒泡”到正确的位置

示例演示

让我们通过一个具体的例子来理解冒泡排序的过程：

原始数组: [5, 2, 8, 1, 9]

第一轮:
- 比较 5 和 2: [2, 5, 8, 1, 9]
- 比较 5 和 8: [2, 5, 8, 1, 9] (不交换)
- 比较 8 和 1: [2, 5, 1, 8, 9]
- 比较 8 和 9: [2, 5, 1, 8, 9] (不交换)

第二轮:
- 比较 2 和 5: [2, 5, 1, 8, 9] (不交换)
- 比较 5 和 1: [2, 1, 5, 8, 9]
- 比较 5 和 8: [2, 1, 5, 8, 9] (不交换)

第三轮:
- 比较 2 和 1: [1, 2, 5, 8, 9]

结果: [1, 2, 5, 8, 9]

C语言实现

基础实现

#include <stdio.h>

// 冒泡排序基础版本
void bubbleSort(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;
            }
        }
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("排序后数组: ");
    printArray(arr, n);

    return 0;
}

输出结果:

原始数组: 64 34 25 12 22 11 90
排序后数组: 11 12 22 25 34 64 90

优化版本1：提前终止

#include <stdbool.h>  // 需要引入stdbool.h

// 优化版本：如果某轮没有发生交换，说明已经有序
void bubbleSortOptimized(int arr[], int n) {
    int i, j, temp;
    bool swapped;

    for (i = 0; i < n - 1; i++) {
        swapped = false;

        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 = true;
            }
        }

        // 如果没有发生交换，说明数组已经有序
        if (!swapped) {
            break;
        }
    }
}

优化版本2：记录最后交换位置

// 优化版本：记录最后交换的位置，减少比较次数
void bubbleSortAdvanced(int arr[], int n) {
    int i, j, temp;
    int lastSwapPos = 0;
    int sortBorder = n - 1;

    for (i = 0; i < n - 1; i++) {
        bool isSorted = true;

        for (j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false;
                lastSwapPos = j;
            }
        }

        sortBorder = lastSwapPos;
        if (isSorted) {
            break;
        }
    }
}

性能分析

时间复杂度

情况	时间复杂度	说明
最好情况	O(n)	数组已经有序，只需一轮遍历
平均情况	O(n²)	随机顺序的数组
最坏情况	O(n²)	数组完全逆序

空间复杂度

• 空间复杂度: O(1) - 冒泡排序是原地排序算法，只需要常数级别的额外空间

稳定性

• 稳定性: 稳定 - 相等元素的相对位置在排序后不会改变

完整示例程序

#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <stdlib.h>

// 函数声明
void bubbleSort(int arr[], int n);
void bubbleSortOptimized(int arr[], int n);
void bubbleSortAdvanced(int arr[], int n);
void printArray(int arr[], int size);
void generateRandomArray(int arr[], int n);
void copyArray(int source[], int dest[], int n);
void comparePerformance(int arr[], int n);

// 基础冒泡排序
void bubbleSort(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;
            }
        }
    }
}

// 优化版冒泡排序
void bubbleSortOptimized(int arr[], int n) {
    int i, j, temp;
    bool swapped;

    for (i = 0; i < n - 1; i++) {
        swapped = false;
        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 = true;
            }
        }
        if (!swapped) break;
    }
}

// 高级优化版冒泡排序
void bubbleSortAdvanced(int arr[], int n) {
    int i, j, temp;
    int lastSwapPos = 0;
    int sortBorder = n - 1;

    for (i = 0; i < n - 1; i++) {
        bool isSorted = true;

        for (j = 0; j < sortBorder; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false;
                lastSwapPos = j;
            }
        }

        sortBorder = lastSwapPos;
        if (isSorted) break;
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 生成随机数组
void generateRandomArray(int arr[], int n) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100;
    }
}

// 复制数组
void copyArray(int source[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = source[i];
    }
}

// 性能比较
void comparePerformance(int arr[], int n) {
    int arr1[n], arr2[n], arr3[n];
    clock_t start, end;
    double cpu_time_used;

    // 复制数组用于不同版本的测试
    copyArray(arr, arr1, n);
    copyArray(arr, arr2, n);
    copyArray(arr, arr3, n);

    printf("性能比较 (数组大小: %d):\n", n);
    printf("----------------------------------------\n");

    // 基础版本
    start = clock();
    bubbleSort(arr1, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("基础版本耗时: %.6f 秒\n", cpu_time_used);

    // 优化版本
    start = clock();
    bubbleSortOptimized(arr2, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("优化版本耗时: %.6f 秒\n", cpu_time_used);

    // 高级优化版本
    start = clock();
    bubbleSortAdvanced(arr3, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("高级优化版本耗时: %.6f 秒\n", cpu_time_used);
    printf("----------------------------------------\n");
}

// 主函数
int main() {
    int choice, n;

    printf("C语言冒泡排序算法演示程序\n");
    printf("=====================================\n");

    while (1) {
        printf("\n请选择操作:\n");
        printf("1. 手动输入数组并排序\n");
        printf("2. 随机生成数组并排序\n");
        printf("3. 性能测试\n");
        printf("4. 退出程序\n");
        printf("请输入选择 (1-4): ");
        scanf("%d", &choice);

        switch (choice) {
            case 1: {
                printf("请输入数组大小: ");
                scanf("%d", &n);
                int arr[n];

                printf("请输入 %d 个整数:\n", n);
                for (int i = 0; i < n; i++) {
                    scanf("%d", &arr[i]);
                }

                printf("\n原始数组: ");
                printArray(arr, n);

                bubbleSortOptimized(arr, n);

                printf("排序后数组: ");
                printArray(arr, n);
                break;
            }

            case 2: {
                printf("请输入数组大小: ");
                scanf("%d", &n);
                int arr[n];

                generateRandomArray(arr, n);

                printf("\n原始数组: ");
                printArray(arr, n);

                bubbleSortOptimized(arr, n);

                printf("排序后数组: ");
                printArray(arr, n);
                break;
            }

            case 3: {
                printf("请输入测试数组大小: ");
                scanf("%d", &n);
                int arr[n];

                generateRandomArray(arr, n);
                comparePerformance(arr, n);
                break;
            }

            case 4:
                printf("感谢使用，再见！\n");
                return 0;

            default:
                printf("无效选择，请重新输入！\n");
        }
    }

    return 0;
}

使用场景与局限性

适用场景

1. 教学演示: 算法简单易懂，适合教学
2. 小数据集: 对于少量数据（n < 100），性能差异不明显
3. 基本有序数据: 当数据基本有序时，优化版本效率较高

局限性

1. 时间复杂度高: O(n²) 的时间复杂度不适合大数据集
2. 性能较差: 相比快速排序、归并排序等现代算法，性能较差
3. 实际应用有限: 在实际工程中很少使用

调试与可视化

添加调试信息

// 带调试信息的冒泡排序
void bubbleSortWithDebug(int arr[], int n) {
    int i, j, temp;
    int pass = 1;

    printf("开始排序过程:\n");

    for (i = 0; i < n - 1; i++) {
        printf("\n第 %d 轮排序:\n", pass++);
        printf("排序前: ");
        printArray(arr, n);

        for (j = 0; j < n - i - 1; j++) {
            printf("比较 %d 和 %d", arr[j], arr[j+1]);
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                printf(" -> 交换");
            } else {
                printf(" -> 不交换");
            }
            printf("\n");
        }

        printf("排序后: ");
        printArray(arr, n);
    }
}

扩展阅读

相关算法

1. 选择排序: 另一种简单的O(n²)排序算法
2. 插入排序: 对于小数据集和基本有序数据表现良好
3. 快速排序: 平均O(n log n)的高效排序算法
4. 归并排序: 稳定的O(n log n)排序算法

优化思路

1. 双向冒泡（鸡尾酒排序）: 从两个方向同时进行冒泡
2. 结合其他算法: 当子数组较小时切换到插入排序
3. 并行化: 利用多线程同时处理不同的比较

总结

冒泡排序虽然简单，但理解它对学习更复杂的排序算法很有帮助。通过本文的学习，你应该掌握了：

1. 算法原理: 理解冒泡排序的基本工作原理
2. 代码实现: 能够用C语言实现基础的冒泡排序
3. 优化技巧: 掌握常见的优化方法
4. 性能分析: 了解算法的时间和空间复杂度
5. 实际应用: 知道何时适合使用冒泡排序

关键要点

• 简单易懂: 适合编程初学者入门
• 稳定排序: 相等元素的相对位置不变
• 原地排序: 不需要额外的存储空间
• 效率较低: 不适合大规模数据排序
• 实际应用少: 主要用于教学和演示

学习建议

1. 先理解原理: 不要死记硬背代码
2. 动手实践: 多写几遍，加深理解
3. 尝试优化: 思考如何改进算法
4. 比较学习: 对比其他排序算法的优劣

---

希望这篇教程对你学习C语言和排序算法有所帮助！如果你有任何问题或建议，欢迎在评论区留言讨论。

参考资源:

• 《算法导论》- Thomas H. Cormen
• 《数据结构与算法分析》- Mark Allen Weiss
• LeetCode 排序算法练习题