CSP-J算法基础 冒泡排序

前言

冒泡排序（Bubble Sort）是经典的排序算法之一，它通过反复遍历待排序序列，比较相邻的元素并交换它们的位置，使较大的元素逐步“冒泡”到序列的末尾。尽管它的实现相对简单，适合初学者入门算法和理解排序的基本思想，但它的效率较低，特别是在处理大型数据集时。该算法的时间复杂度为 O(n²)，由于它的逐步交换机制，适用于数据规模较小且对性能要求不高的场景。本文将介绍冒泡排序的原理及其应用，帮助初学者掌握算法的核心思路。

冒泡排序是什么

冒泡排序（Bubble Sort）是一种简单的排序算法，通过反复比较相邻的元素并交换它们的位置，将较大的元素逐步“冒泡”到数组的末尾。这个过程重复多次，直到整个数组有序。

冒泡排序的过程（使用字符串展示每一步）：

假设我们有一个数组 [5, 3, 8, 4, 2]，使用冒泡排序对它进行升序排序。

1. 初始数组：
   [5, 3, 8, 4, 2]

2. 第1轮：

   • 比较 5 和 3，由于 5 > 3，交换：
     [3, 5, 8, 4, 2]
   • 比较 5 和 8，不用交换：
     [3, 5, 8, 4, 2]
   • 比较 8 和 4，由于 8 > 4，交换：
     [3, 5, 4, 8, 2]
   • 比较 8 和 2，由于 8 > 2，交换：
     [3, 5, 4, 2, 8]

   第1轮结果：最大值 8 已经排到最后。

3. 第2轮：

   • 比较 3 和 5，不用交换：
     [3, 5, 4, 2, 8]
   • 比较 5 和 4，由于 5 > 4，交换：
     [3, 4, 5, 2, 8]
   • 比较 5 和 2，由于 5 > 2，交换：
     [3, 4, 2, 5, 8]

   第2轮结果：次大值 5 已经排到倒数第二位。

4. 第3轮：

   • 比较 3 和 4，不用交换：
     [3, 4, 2, 5, 8]
   • 比较 4 和 2，由于 4 > 2，交换：
     [3, 2, 4, 5, 8]

   第3轮结果：第三大值 4 已经排到倒数第三位。

5. 第4轮：

   • 比较 3 和 2，由于 3 > 2，交换：
     [2, 3, 4, 5, 8]

   第4轮结果：剩余元素已排好序。

最终结果：
经过四轮比较和交换，数组从 [5, 3, 8, 4, 2] 排序为 [2, 3, 4, 5, 8]。

通过以上过程，冒泡排序逐步将较大的元素“冒泡”到数组的末尾，每一轮的操作让数组更接近有序状态。

实现冒泡排序函数

在冒泡排序中：外层循环控制总轮数、内层循环进行相邻元素的比较与交换

1. 外层循环控制总轮数需要进行元素个数-1次
2. 内层循环需要元素个数-外层控制变量-1次

然后在每次循环里面执行比较和交换操作即可：

// 冒泡排序函数（添加了变量信息的打印）
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    // 外层循环控制总轮数
    for (i = 0; i < n - 1; i++) {
        printf("第 %d 轮排序开始:\n", i + 1);
        // 内层循环进行相邻元素的比较与交换
        for (j = 0; j < n - i - 1; j++) {
            printf("  比较 arr[%d] 和 arr[%d] -> %d 和 %d\n", j, j + 1, arr[j], arr[j + 1]);
            if (arr[j] > arr[j + 1]) {
                // 交换 arr[j] 和 arr[j + 1]
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                printf("    交换后: arr[%d] = %d, arr[%d] = %d\n", j, arr[j], j + 1, arr[j + 1]);
            }
        }
        
        // 打印每轮结束后的数组状态
        printf("  第 %d 轮结束，数组状态: ", i + 1);
        for (int k = 0; k < n; k++) {
            printf("%d ", arr[k]);
        }
        printf("\n");
    }
}

总结

冒泡排序是一种直观易懂的排序算法，通过反复比较和交换相邻元素，最终将数组排序。虽然冒泡排序在实际应用中由于其 O(n²) 的时间复杂度效率较低，但它为理解更复杂的排序算法提供了基础。掌握冒泡排序不仅能帮助我们巩固对算法的理解，还能为进一步学习如快速排序、归并排序等更高效的排序算法打下良好的基础。在数据规模较小时，冒泡排序仍可以作为一种简单、易实现的排序方案。