C语言 冒泡排序算法详解及实例

冒泡排序算法详解及实例

什么是冒泡排序算法

冒泡排序是一种很基础的排序算法，它通过从序列的一端开始，依次比较相邻两个元素的大小，如果它们的顺序不对，就交换它们的位置，直到把整个序列排序完成。冒泡排序算法的时间复杂度为O(n^2)，所以它并不适合排序规模很大的序列。

冒泡排序算法的实现

冒泡排序算法的实现很简单，其核心代码如下：

void bubble_sort(int *a, int n)
{
    int i, j, tmp;
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

上面的代码中，a是待排序的数组，n是数组的长度。外层循环控制排序的轮数，内层循环控制每轮比较的次数。在每次比较时，如果前一个元素的值比后一个元素的值大，就交换它们的位置。

冒泡排序算法的示例

我们通过两个示例来说明冒泡排序算法的用法。

示例1：对整数数组进行排序

#include <stdio.h>

void bubble_sort(int *a, int n);

int main()
{
    int a[] = {3, 2, 7, 4, 1, 5, 8, 6};
    int n = sizeof(a) / sizeof(int);
    int i;

    printf("Before sorting: ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);

    bubble_sort(a, n);

    printf("\nAfter sorting: ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

void bubble_sort(int *a, int n)
{
    int i, j, tmp;
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

运行上面的代码，输出结果如下：

Before sorting: 3 2 7 4 1 5 8 6 
After sorting: 1 2 3 4 5 6 7 8

示例2：对字符串数组进行排序

#include <stdio.h>
#include <string.h>

void bubble_sort(char *a[], int n);

int main()
{
    char *a[] = {"apple", "orange", "banana", "kiwi", "grape"};
    int n = sizeof(a) / sizeof(char *);
    int i;

    printf("Before sorting: ");
    for (i = 0; i < n; i++)
        printf("%s ", a[i]);

    bubble_sort(a, n);

    printf("\nAfter sorting: ");
    for (i = 0; i < n; i++)
        printf("%s ", a[i]);

    return 0;
}

void bubble_sort(char *a[], int n)
{
    int i, j;
    char *tmp;
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            if (strcmp(a[j], a[j + 1]) > 0)
            {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

运行上面的代码，输出结果如下：

Before sorting: apple orange banana kiwi grape 
After sorting: apple banana grape kiwi orange

上面的代码将字符串数组按照字典序进行排序。

总结

冒泡排序算法虽然很简单，但是它是一种基础的排序算法，很多其他排序算法的实现都是在它的基础上做出改进的。在实际开发中，如果需要对规模比较小的数组进行排序，冒泡排序是一个不错的选择。