C语言冒泡排序算法原理与完整代码示例

Cora

发布时间：2026-10-14 | 4人浏览过

原创

冒泡排序（Bubble Sort）是一种基础的计算机排序算法，其核心逻辑是通过重复走访数列，比较相邻元素并在顺序错误时进行交换，使较小或较大的元素逐渐“浮”至顶端。本文将结合C语言代码，详细展示该算法的标准实现、无临时变量交换技巧以及如何通过标志位优化性能。

冒泡排序的核心逻辑

冒泡排序的工作原理非常简单直观：它从序列的一端开始，依次比较相邻的两个元素。如果它们的顺序（如大小关系）与期望的顺序相反，就交换这两个元素的位置。这一过程会反复进行，直到在某次遍历中没有发生任何交换操作为止，此时表明整个数列已经按升序或降序排列完成。由于较小的元素像气泡一样慢慢“浮”到数列顶端，因此得名。

鉴于其算法结构的简洁性，冒泡排序常被用作计算机程序设计入门课程中介绍算法概念的典型案例，帮助学生建立对数据结构和控制流的基本认知。

代码实现与关键技术解析

以下 C 语言代码示例展示了如何实现一个带有性能优化的冒泡排序函数。代码主要包含三个部分：

swap 函数：实现了不使用临时变量的元素交换方法。
mao_pao 主函数：执行外层和内层循环，完成排序逻辑。
main 函数：初始化测试数组并输出结果。

第1步：定义无临时变量交换函数

在标准的交换操作中，通常需要引入第三个临时变量来暂存数据。但在本例中，利用了算术运算的特性，在不借助额外内存空间的情况下完成了两个整数的值互换。这种方法虽然节省了一个变量的内存开销，但在处理极大数值时需注意防止整数溢出。

#include <stdio.h>
int swap(int *a, int *b)
{
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
    return 0;
}

第2步：构建带优化标志的排序主逻辑

常规的冒泡排序即使在全已排序的情况下也会执行 $O(n^2)$ 次比较。为了优化性能，引入了 flag 标志位：
- 在外层循环开始前，设置 flag = 1。
- 进入内层比较后，若发现需要交换，则设置 flag = 1；否则保持为 0。
- 若某轮遍历结束 flag 仍为 0，说明没有发生任何交换，数组已有序，外层循环提前终止。这种优化使得在最好情况下（数组原本有序），时间复杂度可降至 $O(n)$。

int mao_pao(int *a, int n)
{
    int i, j, flag;
    // i表示当前需要比较的最大索引，flag用于记录是否发生交换
    for(i = n - 1, flag = 1; i > 0 && flag ; --i)
    {
        flag = 0;
        for(j = 0; j < i; ++j)
        {
            if(a[j] > a[j + 1])
            {
                flag = 1;
                swap(a + j, a + j + 1);
            }
        }
    }
    return 0;
}

第3步：初始化数据并调用执行

在 main 函数中，我们定义了一个包含10个整数的乱序数组，调用 mao_pao 进行排序，并使用 printf 格式化打印排序后的结果，以便直观验证算法的正确性。

int main(int argc, const char *argv[])
{
    int i;
    int a[] = {7,8,6,2,9,4,3,1,5,10};
    
    // 执行排序
    mao_pao(a, 10);
    
    // 打印排序结果，%4d用于对齐输出
    for(i = 0; i < 10; ++i)
    {
        printf("%4d", a[i]);
    }
    printf("\n");
    
    return 0;
}