冒泡排序

一、排序问题的基本概念

在计算机科学中，排序（Sorting）是最基础且最重要的一类问题。简单来说，排序就是将一组杂乱无章的数据元素，按照某种预定的规则（例如，数值从小到大、字典序等）重新排列成一个有序序列的过程。

例如，给定一个整数数组 A={5,2,8,1,9}A = \{5, 2, 8, 1, 9\}，我们希望将其按照从小到大的顺序排序，得到的结果将是 B={1,2,5,8,9}B = \{1, 2, 5, 8, 9\}。这个从数组 AA 到数组 BB 的过程，就是一个排序过程。

排序算法的优劣通常由其运行效率来衡量，主要体现在两个方面：

  1. 时间复杂度 (Time Complexity)：算法执行所需的时间。这通常用比较次数和交换次数来衡量。
  2. 空间复杂度 (Space Complexity)：算法执行过程中额外占用的内存空间。

冒泡排序是众多排序算法中最简单、最直观的一种，非常适合作为理解排序思想的起点。

二、冒泡排序的核心思想

冒泡排序的核心思想可以概括为：通过重复地遍历待排序序列，依次比较相邻的两个元素，如果它们的顺序错误（例如，在升序排列中，前一个比后一个大），就交换它们的位置。

这个过程会一直重复，直到在某一次遍历中没有发生任何元素交换，这意味着整个序列已经变得有序。

为什么叫“冒泡”排序呢？我们可以想象序列中的元素就像水中的气泡。在从小到大排序的过程中，较小的元素会经过交换，慢慢地“浮”到序列的顶部（即数组的低索引端），而较大的元素则会“沉”到序列的底部（即数组的高索引端），这个过程酷似水中气泡上浮的景象。

具体来说，冒泡排序的每一轮遍历（称为一次“趟”或“pass”）都完成一个任务：将当前未排序部分中的最大元素放置到其最终的正确位置上。

  • 第一趟：从第一个元素开始，比较它和第二个元素，如果第一个大，就交换。然后比较第二个和第三个，以此类推，直到比较倒数第二个和最后一个元素。这一趟结束后，整个序列中的最大元素必然被移动到了最后一位。
  • 第二趟：由于最后一个元素已经是最大的了，我们只需要对前面 n−1n-1 个元素重复上述过程。这一趟结束后，次大的元素会被移动到倒数第二位。
  • 依此类推：每一趟都将一个当前未排序部分的最大值放到其最终位置。如果一个序列有 nn 个元素，最多需要进行 n−1n-1 趟排序。

三、冒泡排序的分步图解

我们用一个具体的例子来完整地走一遍冒泡排序的流程。假设待排序的数组为 A={6,5,3,1,8,7,2,4}A = \{6, 5, 3, 1, 8, 7, 2, 4\}。

第一趟：目标是将当前序列的最大值 8 移动到最后。

  1. 比较 AA 和 AA（6 和 5）。6>56 > 5，交换。序列变为 {5,6,3,1,8,7,2,4}\{5, 6, 3, 1, 8, 7, 2, 4\}。
  2. 比较 AA 和 AA（6 和 3）。6>36 > 3，交换。序列变为 {5,3,6,1,8,7,2,4}\{5, 3, 6, 1, 8, 7, 2, 4\}。
  3. 比较 AA 和 AA（6 和 1）。6>16 > 1，交换。序列变为 {5,3,1,6,8,7,2,4}\{5, 3, 1, 6, 8, 7, 2, 4\}。
  4. 比较 AA 和 AA（6 和 8）。6<86 < 8，不交换。序列不变。
  5. 比较 AA 和 AA（8 和 7）。8>78 > 7，交换。序列变为 {5,3,1,6,7,8,2,4}\{5, 3, 1, 6, 7, 8, 2, 4\}。
  6. 比较 AA 和 AA（8 和 2）。8>28 > 2，交换。序列变为 {5,3,1,6,7,2,8,4}\{5, 3, 1, 6, 7, 2, 8, 4\}。
  7. 比较 AA 和 AA（8 和 4）。8>48 > 4，交换。序列变为 {5,3,1,6,7,2,4,8}\{5, 3, 1, 6, 7, 2, 4, 8\}。

第一趟结束，最大元素 8 已经“沉”到了数组的末尾。此时，数组最后一位已有序。

第二趟：目标是将剩余 n−1n-1 个元素中的最大值 7 移动到倒数第二位。比较范围是 AA 到 AA。

  1. 比较 AA 和 AA（5 和 3）。5>35 > 3，交换。序列变为 {3,5,1,6,7,2,4,8}\{3, 5, 1, 6, 7, 2, 4, 8\}。
  2. 比较 AA 和 AA（5 和 1）。5>15 > 1，交换。序列变为 {3,1,5,6,7,2,4,8}\{3, 1, 5, 6, 7, 2, 4, 8\}。
  3. 比较 AA 和 AA（5 和 6）。5<65 < 6，不交换。
  4. 比较 AA 和 AA（6 和 7）。6<76 < 7，不交换。
  5. 比较 AA 和 AA（7 和 2）。7>27 > 2，交换。序列变为 {3,1,5,6,2,7,4,8}\{3, 1, 5, 6, 2, 7, 4, 8\}。
  6. 比较 AA 和 AA（7 和 4）。7>47 > 4，交换。序列变为 {3,1,5,6,2,4,7,8}\{3, 1, 5, 6, 2, 4, 7, 8\}。

第二趟结束，次大元素 7 已经就位。此时，数组最后两位已有序。

这个过程会继续下去。每一趟排序的比较次数都会比前一趟少一次。

优化思路

如果在某一趟遍历中，没有发生任何一次交换，这说明整个序列已经完全有序，我们就可以提前结束排序，而不必执行完所有 n−1n-1 趟。这是一个非常重要的优化。

例如，如果初始数组是 {1,2,3,5,4}\{1, 2, 3, 5, 4\}。 第一趟后，序列变为 {1,2,3,4,5}\{1, 2, 3, 4, 5\}。 在进行第二趟遍历时，我们会发现没有任何元素需要交换。此时，就可以断定排序已经完成，直接终止算法。

四、C++ 代码实现

下面我们来看冒泡排序的C++代码实现，包括基础版本和优化版本。

1. 基础实现

这是最直接的冒泡排序实现，通过两层循环来完成。外层循环控制总共需要进行的“趟数”，内层循环负责在每一趟中进行相邻元素的比较和交换。

题意概括：对一个整型数组进行从小到大排序。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void bub(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]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    bub(a, n);

    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

  • 代码解释:

    • i 循环：控制排序的趟数。从 0 到 n-2，共 n-1 趟。
    • j 循环：控制每一趟中相邻元素的比较。j 的上界是 n-1-i，因为每经过一趟，末尾的 i 个元素就已经是有序的了，无需再参与比较。
    • swap(a[j], a[j+1]): 是C++ STL提供的标准交换函数，用于交换两个变量的值。

  • 复杂度分析:

    • 时间复杂度: O(n2)O(n^2)。在最坏情况下（例如，序列完全逆序），比较次数和交换次数都是 O(n2)O(n^2) 级别的。总的比较次数为 (n−1)+(n−2)+...+1=(n−1)n2(n-1) + (n-2) + ... + 1 = \frac{(n-1)n}{2}。
    • 空间复杂度: O(1)O(1)。排序过程中只使用了常数个额外变量（如 i, j），没有使用与输入规模 n 相关的额外内存空间。这种在原数组上直接进行修改的排序称为“原地排序” (in-place)。

2. 优化实现

我们可以加入一个标志位来记录每一趟是否发生了交换。如果没有，则说明序列已经有序，可以提前终止。

题意概括：对一个整型数组进行从小到大排序，并在数组已有序时提前终止。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void bub(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool flg = false; // 交换标志，默认为false
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                flg = true; // 发生了交换，置为true
            }
        }
        // 如果这一趟没有发生任何交换，说明已经有序
        if (!flg) {
            break; // 提前退出循环
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int a[] = {1, 2, 3, 5, 4};
    int n = sizeof(a) / sizeof(a[0]);

    bub(a, n);

    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

  • 代码解释:

    • flg 变量：在每趟排序开始前被设为 false。如果在该趟的内层循环中发生了任何一次交换，flg 就会被设为 true。
    • if (!flg) break;：在该趟排序结束后，检查 flg。如果它仍然是 false，意味着没有发生交换，序列已有序，break 语句会立即跳出外层循环，结束整个排序过程。

  • 复杂度分析:

    • 时间复杂度:
      • 最坏情况: O(n2)O(n^2)。当输入序列是完全逆序时，每一趟都会发生交换，flg 优化不起作用，复杂度与基础版本相同。
      • 最好情况: O(n)O(n)。当输入序列已经排好序时，算法只会执行一趟（i=0），比较 n-1 次后发现没有交换，然后就退出了。
      • 平均情况: O(n2)O(n^2)。
    • 空间复杂度: O(1)O(1)。增加的 flg 变量只占用了常数空间。

五、算法复杂度与性质分析

1. 时间复杂度详解

我们来更深入地分析冒泡排序的时间开销，主要由元素之间的比较次数和交换次数构成。

  • 比较次数 (Comparisons)

    • 无论序列的初始状态如何，基础版本的冒泡排序的内层循环都会完整地执行。
    • 第一趟比较 n−1n-1 次。
    • 第二趟比较 n−2n-2 次。
    • ...
    • 最后一趟比较 11 次。
    • 总比较次数 C(n)C(n) 为：$$C(n) = (n-1) + (n-2) + \dots + 1 = \sum_{i=1}^{n-1} i = \frac{(n-1)n}{2} $$
    • 这是一个关于 nn 的二次函数，因此时间复杂度为 O(n2)O(n^2)。优化版本在最好情况下（已排序序列）比较次数为 n−1n-1，属于 O(n)O(n)。

  • 交换次数 (Swaps)

    • 最坏情况：序列完全逆序，例如 {5, 4, 3, 2, 1}。
      • 第一趟，元素5需要与所有其他元素交换，移动到末尾，交换 n−1n-1 次。
      • 第二趟，元素4需要与前面所有元素交换，移动到次末尾，交换 n−2n-2 次。
      • 总交换次数 Smax(n)S_{max}(n) 与比较次数相同：Smax(n)=(n−1)n2=O(n2)S_{max}(n) = \frac{(n-1)n}{2} = O(n^2)
    • 最好情况：序列已经有序，例如 {1, 2, 3, 4, 5}。
      • 交换次数为 00。
    • 平均情况：对于一个随机排列，平均交换次数约为 Smax(n)S_{max}(n) 的一半，即 (n−1)n4\frac{(n-1)n}{4}，仍然是 O(n2)O(n^2)。

2. 算法性质

  • 稳定性 (Stability)

    • 冒泡排序是稳定的排序算法。
    • 稳定性的定义是：如果序列中有两个相等的元素 AA 和 BB，并且在排序前 AA 出现在 BB 的前面，那么在排序后的序列中，AA 仍然会出现在 BB 的前面。
    • 在冒泡排序的比较逻辑 if (a[j] > a[j + 1]) 中，只有当 a[j] 严格大于 a[j+1] 时才会发生交换。如果两个元素相等（a[j] == a[j+1]），它们不会交换位置。因此，相等元素的相对顺序在整个排序过程中不会改变，保证了算法的稳定性。稳定性在某些应用场景中非常重要，例如需要按多个关键字排序时。

  • 空间复杂度 (Space Complexity)

    • 冒泡排序是原地排序 (in-place) 算法。
    • 它的空间复杂度是 O(1)O(1)，因为它只需要一个或两个额外的变量用于循环计数和可能的交换（或标志位），这些额外空间不随待排序数据规模 nn 的增长而增长。

六、题型精练

1. 选择题

例1：使用冒泡排序对序列 {6, 1, 2, 7, 9, 3, 4, 5, 10, 8} 进行从小到大排序，第一趟排序结束后，序列变为？ A. {1, 6, 2, 7, 3, 4, 5, 9, 8, 10} B. {1, 2, 6, 7, 3, 4, 5, 9, 8, 10} C. {6, 1, 2, 7, 3, 4, 5, 9, 8, 10} D. {1, 2, 6, 7, 9, 3, 4, 5, 8, 10}

解析： 第一趟冒泡排序的目标是将当前序列中的最大元素通过相邻交换移动到序列的末尾。我们来逐步模拟这个过程：

  • 初始序列: {6, 1, 2, 7, 9, 3, 4, 5, 10, 8}
  1. 比较 a[0](6) 和 a[1](1)：6>16>1，交换。序列变为 {1, 6, 2, 7, 9, 3, 4, 5, 10, 8}。
  2. 比较 a[1](6) 和 a[2](2)：6>26>2，交换。序列变为 {1, 2, 6, 7, 9, 3, 4, 5, 10, 8}。
  3. 比较 a[2](6) 和 a[3](7)：6<76<7，不交换。
  4. 比较 a[3](7) 和 a[4](9)：7<97<9，不交换。
  5. 比较 a[4](9) 和 a[5](3)：9>39>3，交换。序列变为 {1, 2, 6, 7, 3, 9, 4, 5, 10, 8}。
  6. 比较 a[5](9) 和 a[6](4)：9>49>4，交换。序列变为 {1, 2, 6, 7, 3, 4, 9, 5, 10, 8}。
  7. 比较 a[6](9) 和 a[7](5)：9>59>5，交换。序列变为 {1, 2, 6, 7, 3, 4, 5, 9, 10, 8}。
  8. 比较 a[7](9) 和 a[8](10)：9<109<10，不交换。
  9. 比较 a[8](10) 和 a[9](8)：10>810>8，交换。序列变为 {1, 2, 6, 7, 3, 4, 5, 9, 8, 10}。

第一趟比较全部结束，最终序列为 {1, 2, 6, 7, 3, 4, 5, 9, 8, 10}。此结果与选项B完全匹配。 正确答案是 B。

例2：对于一个长度为 nn 的序列，冒泡排序在最坏情况下的时间复杂度是？ A. O(log⁡n)O(\log n) B. O(n)O(n) C. O(nlog⁡n)O(n \log n) D. O(n2)O(n^2)

解析： 最坏情况通常指待排序序列完全逆序。此时，需要执行完整的 n−1n-1 趟排序，且每一趟中的每一次比较都可能导致一次交换。总的比较次数是 n(n−1)2\frac{n(n-1)}{2}，这是一个关于 nn 的二次多项式。根据大O表示法，我们忽略低阶项和常数系数，得到时间复杂度为 O(n2)O(n^2)。 正确答案是 D。

例3：下列关于冒泡排序的说法，错误的是？ A. 冒泡排序是稳定的排序算法。 B. 冒泡排序是一种原地排序算法，空间复杂度为 O(1)O(1)。 C. 对于已经有序的序列，使用优化后的冒泡排序，其时间复杂度为 O(n)O(n)。 D. 冒泡排序的平均时间复杂度为 O(nlog⁡n)O(n \log n)。

解析： A：正确。冒泡排序在比较 a[j] 和 a[j+1] 时，只有 > 的时候才交换，= 的时候不交换，能保证相等元素的相对顺序不变。 B：正确。冒泡排序仅需常数个额外变量，是原地排序。 C：正确。优化后的冒泡排序，若序列已有序，则第一趟遍历不会发生任何交换，flag 标志使其提前退出，总共只比较了 n−1n-1 次，时间复杂度为 O(n)O(n)。 D：错误。冒泡排序的平均时间复杂度（对于随机序列）是 O(n2)O(n^2)，而非 O(nlog⁡n)O(n \log n)。O(nlog⁡n)O(n \log n) 是更高效的排序算法（如归并排序、快速排序）的平均时间复杂度。 正确答案是 D。

2. 判断题

例1：对任意 nn 个整数进行冒泡排序，至少需要进行 n−1n-1 次比较。 (√) 解析：即使是最好的情况（序列已经有序），为了确认它是有序的，优化后的冒泡排序也必须完整地进行第一趟遍历，这需要 n−1n-1 次比较。

例2：冒泡排序的每一趟都能保证将一个元素放到其最终位置上。 (√) 解析：第 ii 趟冒泡排序（ii 从 1 开始计数）能保证将当前未排序部分的最大值放到倒数第 ii 个位置，这个位置就是该元素在整个有序序列中的最终位置。

3. 程序阅读题

题目：阅读下面的C++代码，写出其对输入数组 a = {3, 1, 4, 2} 执行后的输出结果。

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a[] = {3, 1, 4, 2};
    int n = 4;
    int cnt = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - 1 - i; ++j) {
            cnt++;
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

解析： 该程序对数组 a 执行了标准的冒泡排序，并用变量 cnt 记录了总的比较次数。我们需要计算 cnt 的最终值，而不需要关心数组 a 的变化。 n = 4。 外层循环 i 的取值为 0, 1, 2。

  • 当 i = 0 时，内层循环 j 的取值为 0, 1, 2 (因为 j < 4 - 1 - 0，即 j < 3)。执行3次比较，cnt 变为 3。
  • 当 i = 1 时，内层循环 j 的取值为 0, 1 (因为 j < 4 - 1 - 1，即 j < 2)。执行2次比较，cnt 变为 3+2=53 + 2 = 5。
  • 当 i = 2 时，内层循环 j 的取值为 0 (因为 j < 4 - 1 - 2，即 j < 1)。执行1次比较，cnt 变为 5+1=65 + 1 = 6。

总的比较次数 cnt = 3+2+1=63 + 2 + 1 = 6。程序最终会输出 cnt 的值。 输出结果：

6

4. 程序补全题

题目：下面是一个实现优化冒泡排序的函数，请将空缺部分的代码补充完整。

#include<bits/stdc++.h>
using namespace std;

void bub(int a[], int n) {
    bool flg;
    for (int i = 0; i < n - 1; i++) {
        flg = false;
        for (int j = 0; j < ______ ; j++) { // 空缺1
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                ______; // 空缺2
            }
        }
        if (flg == false) {
            ______; // 空缺3
        }
    }
}

解析与答案：

  1. 空缺1：内层循环的边界。每一趟排序后，末尾的 i 个元素已经有序，所以比较的范围是 n - 1 - i。因此，循环条件是 j < n - 1 - i。
  2. 空缺2：当发生交换时，需要将 flg 标志位置为 true，以表明本趟排序中数据的位置发生了变动。
  3. 空缺3：如果一整趟下来 flg 仍然是 false，说明序列已经有序，应该提前跳出最外层循环，结束排序。使用 break 语句。

完整答案：

  1. n - 1 - i
  2. flg = true
  3. break
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 陕ICP备2025061476号
  3. Worker 0, 191ms
  4. Powered Dong Dong