C语言冒泡排序实现代码：原理与优化

算法核心原理

冒泡排序的名称源于其视觉特征：较大的元素如同气泡一般，经由多次交换逐渐移动到数列的顶端（或底端）。算法的基本策略是遍历待排序数组，不断比较相邻的两个数。若顺序错误（如希望从小到大排序但前一个数大于后一个数），则交换这两个数的位置。经过一轮完整的遍历，当前未排序部分的最大值会被确定并移动到正确位置。随后，对剩余未排序部分重复此过程，直至整个数组有序。

手动推导排序过程

为了直观理解算法执行流程，以下以数组 [3, 2, 4, 1] 为例，演示如何完成从小到大的排序：

第一轮比较：确定最大值

初始状态：3, 2, 4, 1

• 比较 3 和 2：3 > 2，交换位置 → 2, 3, 4, 1
• 比较 3 和 4：3 < 4，不交换 → 2, 3, 4, 1
• 比较 4 和 1：4 > 1，交换位置 → 2, 3, 1, 4

第一轮结束，最大的数字 4 已经位于数组末尾。下一轮只需比较前三个元素。

第二轮比较：确定次大值

当前状态：2, 3, 1, 4

• 比较 2 和 3：2 < 3，不交换 → 2, 3, 1, 4
• 比较 3 和 1：3 > 1，交换位置 → 2, 1, 3, 4

第二轮结束，第二大的数字 3 已就位。下一轮仅需比较前两个元素。

第三轮比较：完成排序

当前状态：2, 1, 3, 4

• 比较 2 和 1：2 > 1，交换位置 → 1, 2, 3, 4

至此，数组完全有序，排序结束。对于 N 个元素的数组，通常需要进行 N-1 轮比较。

C语言代码实现

在实际开发中，我们通常会提供两种实现方式：一种是标准的教科书式实现，另一种是引入标志位以优化性能的版本。

标准实现

这是最直接的逻辑表达，无论数组是否已经有序，都会执行完所有轮次的比较。适用于小规模数据或对性能要求不极高的场景。

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

#define N 8

/**
 * 冒泡排序 - 标准实现
 * @param a 待排序数组
 * @param n 数组元素个数
 */
void bubble_sort(int a[], int n)
{
    // 外层循环控制比较轮数，共需 n-1 轮
    for (int i = 0; i < n - 1; i++)
    {
        // 内层循环进行相邻元素比较
        // 每次外循环结束后，最后 i 个元素已有序，无需再比较
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                // 交换相邻元素
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

int main()
{
    int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
    
    bubble_sort(num, N);
    
    for (int i = 0; i < N; i++)
        printf("%d ", num[i]);
    printf("\n");
    
    system("pause");
    return 0;
}

优化实现

在标准实现中，即使输入数组已经是有序的，算法仍会执行所有必要的比较操作，导致时间复杂度始终为 O(N^2)。优化版引入布尔变量 isSorted 作为标记。如果在某一轮遍历中没有发生任何交换，说明数组已经完全有序，可以提前跳出循环，显著提升最佳情况下的性能。

/**
 * 冒泡排序 - 优化实现
 * @param a 待排序数组
 * @param n 数组元素个数
 */
void bubble_sort_better(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool isSorted = true; // 假设本轮已有序
        
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                isSorted = false; // 发现逆序，标记为未排序
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        
        // 如果本轮没有发生交换，说明数组已排好序，提前结束
        if (isSorted) break;
    }
}

以上关于C语言冒泡排序算法的原理分析与代码实现的详细内容，更多关于C语言数据结构与算法的资料请关注本站其它相关文章！