C 语言中如何进行冒泡排序？

🍅关注博主🎗️ 带你畅游技术世界，不错过每一次成长机会！
📙C 语言百万年薪修炼课程 通俗易懂，深入浅出，匠心打磨，死磕细节，6年迭代，看过的人都说好。

C 语言中的冒泡排序

冒泡排序（Bubble Sort）是排序算法里面比较简单的一个排序。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

一、冒泡排序的基本原理

冒泡排序的基本思想是通过相邻元素的两两比较，将最大（或最小）的元素逐步“浮”到数组的一端。

假设我们要对一个整数数组进行升序排序。在每一轮比较中，从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。这样，在第一轮比较结束后，最大的元素就会“浮”到数组的末尾。然后，对除了最后一个元素之外的其他元素进行同样的操作，在第二轮比较结束后，第二大的元素就会“浮”到数组的倒数第二个位置。以此类推，经过 n - 1 轮比较后，数组就会完成排序。

二、冒泡排序的代码实现

以下是用 C 语言实现冒泡排序的代码：

#include <stdio.h>

// 交换两个整数的函数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int 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;
}

在上述代码中：

• swap 函数用于交换两个整数的位置。
• bubbleSort 函数实现了冒泡排序的逻辑。外层循环控制排序的轮数，一共需要进行 n - 1 轮。内层循环用于每一轮比较相邻的元素并在需要时进行交换。
• printArray 函数用于打印数组中的元素。

在 main 函数中，我们定义了一个待排序的数组，调用 bubbleSort 函数进行排序，并打印排序前后数组的元素。

三、冒泡排序的时间复杂度和空间复杂度分析

（一）时间复杂度

在最坏情况下，数组完全逆序，每次比较都需要进行交换，此时冒泡排序的时间复杂度为 $O(n^2)$。这是因为外层循环要执行 n - 1 次，内层循环在最坏情况下要执行 n - i - 1 次，总的比较和交换次数约为 $\frac{n(n-1)}{2}$ ，所以时间复杂度为 $O(n^2)$。

在最好情况下，数组已经是有序的，此时内层循环不需要进行任何交换，时间复杂度为 $O(n)$。但平均情况下，时间复杂度仍然接近最坏情况，为 $O(n^2)$。

（二）空间复杂度

冒泡排序是一种原地排序算法，只需要几个固定的额外变量来辅助交换操作，空间复杂度为 $O(1)$。

四、冒泡排序的优化

原始的冒泡排序在某些情况下可能会做一些不必要的比较和交换。以下是两种常见的优化方法：

（一）添加标志位判断是否已经有序

void bubbleSortOptimized1(int arr[], int n) {
    int i, j;
    int swapped;

    for (i = 0; i < n - 1; i++) {
        swapped = 0;
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }

        // 如果在一轮比较中没有发生交换，说明数组已经有序，直接退出
        if (swapped == 0) {
            break;
        }
    }
}

在上述优化代码中，添加了一个标志位 swapped 。如果在一轮比较中没有进行任何交换，说明数组已经是有序的，就可以提前结束排序过程。

（二）记录最后一次交换的位置

void bubbleSortOptimized2(int arr[], int n) {
    int i, j;
    int lastSwap = n - 1;

    while (lastSwap > 0) {
        int newLastSwap = 0;
        for (j = 0; j < lastSwap; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                newLastSwap = j;
            }
        }
        lastSwap = newLastSwap;
    }
}

这种优化方法通过记录每一轮最后一次交换的位置，来缩小下一轮比较的范围，从而减少不必要的比较。

五、示例分析

假设我们有一个数组 {5, 1, 4, 2, 8} ，下面逐步分析冒泡排序的过程：

第一轮：

• 比较 5 和 1，因为 5 > 1，所以交换它们，数组变为 {1, 5, 4, 2, 8} 。
• 比较 5 和 4，因为 5 > 4，所以交换它们，数组变为 {1, 4, 5, 2, 8} 。
• 比较 5 和 2，因为 5 > 2，所以交换它们，数组变为 {1, 4, 2, 5, 8} 。
• 比较 5 和 8，因为 5 < 8，所以不交换，数组保持 {1, 4, 2, 5, 8} 。

第一轮结束后，最大的数 8 已经“浮”到了数组的末尾。

第二轮：

• 比较 1 和 4，因为 1 < 4，所以不交换，数组保持 {1, 4, 2, 5, 8} 。
• 比较 4 和 2，因为 4 > 2，所以交换它们，数组变为 {1, 2, 4, 5, 8} 。
• 比较 4 和 5，因为 4 < 5，所以不交换，数组保持 {1, 2, 4, 5, 8} 。

第二轮结束后，第二大的数 5 已经“浮”到了倒数第二个位置。

第三轮：

• 比较 1 和 2，因为 1 < 2，所以不交换，数组保持 {1, 2, 4, 5, 8} 。
• 比较 2 和 4，因为 2 < 4，所以不交换，数组保持 {1, 2, 4, 5, 8} 。

第三轮结束后，第三大的数 4 已经“浮”到了第三个位置。

第四轮：

比较 1 和 2，因为 1 < 2，所以不交换，数组保持 {1, 2, 4, 5, 8} 。

经过四轮比较，数组已经完成排序。

六、冒泡排序的适用场景

冒泡排序由于其简单性和易于理解，在小型数据集或者对性能要求不高的情况下可能会被使用。但在处理大型数据集时，由于其时间复杂度较高，通常会选择更高效的排序算法，如快速排序、归并排序等。

七、与其他排序算法的比较

（一）与插入排序比较

插入排序在部分有序的情况下性能较好，而冒泡排序在任何情况下的性能都相对稳定，但通常比插入排序慢。

（二）与选择排序比较

选择排序和冒泡排序的时间复杂度相同，但选择排序在每一轮中只进行一次交换，而冒泡排序可能进行多次交换，所以在实际应用中选择排序可能略优于冒泡排序。

（三）与快速排序比较

快速排序的平均时间复杂度为 $O(nlogn)$，远优于冒泡排序的 $O(n^2)$，适用于大规模数据的排序。

冒泡排序是一种简单但效率较低的排序算法，在实际应用中应根据具体情况选择合适的排序算法。

🎉相关推荐

• 📙C 语言百万年薪修炼课程 通俗易懂，深入浅出，匠心打磨，死磕细节，6年迭代，看过的人都说好。
• 🍅博客首页-关注博主🎗️ 带你畅游技术世界，不错过每一次成长机会！
• 📙CSDN专栏-C语言修炼
• 📙技术社区-墨松科技