冒泡排序算法

笔记 CPP

介绍

冒泡排序算法是一个经典的排序算法，待排序的数列会一个数一个数地按照大小确定好位置，宛如泡泡一个个地浮出水面。

原理

假设你要求 从小到大 排列数列 a，冒泡排序算法会一轮轮地比较相邻两个位置的数的大小，比如，拿位置 j 的数与位置 j + 1 的数相比较，如果 a[j] 大于 a[j + 1]，那么就使 a[j] 与 a[j + 1] 交换位置，反之则不操作。这样就能使大的数字靠后了。
先来用一个例子看看冒泡排序算法会在每一轮中干什么。 

假设有一个数列：[1, 3, 4, 5, 2]，需要排列成 [1, 2, 3, 4, 5]。
第 1 轮（把最大值冒泡到末尾）
比较 1 和 3 → 不交换 → [1, 3, 4, 5, 2]
比较 3 和 4 → 不交换 → [1, 3, 4, 5, 2]
比较 4 和 5 → 不交换 → [1, 3, 4, 5, 2]
比较 5 和 2 → 要交换 → [1, 3, 4, 2, 5] ✅ 5 冒泡到末尾，尘埃落定

我们来回顾一下第一轮里的几次比较：

比较 1 和 3 → 不交换 → [1, 3, 4, 5, 2]
比较 3 和 4 → 不交换 → [1, 3, 4, 5, 2]
比较 4 和 5 → 不交换 → [1, 3, 4, 5, 2]
比较 5 和 2 → 要交换 → [1, 3, 4, 2, 5] ✅ 5 冒泡到末尾，尘埃落定 

第 2 轮（把次大值冒泡到倒数第二个位置，每轮所需的比较次数都递减）
比较 1 和 3 → 不交换 → [1, 3, 4, 2, 5]
比较 3 和 4 → 不交换 → [1, 3, 4, 2, 5]
比较 4 和 2 → 交换 → [1, 3, 2, 4, 5] ✅ 4 到倒数第二个位置

第 3 轮（把第三大值冒泡到倒数第三个位置）
比较 1 和 3 → 不交换 → [1, 3, 2, 4, 5]
比较 3 和 2 → 交换 → [1, 2, 3, 4, 5] ✅ 3 到正确位置

第 4 轮（最后两元素检查）
比较 1 和 2 → 不交换 → [1, 2, 3, 4, 5] ✅ 已经有序

在 C++ 代码中的实现方式

在具体代码中，我们要用 for 的嵌套来实现轮数的递增以及轮内的比较。假设你要求 从小到大 排列数列 a，那么外部的 for 用于控制冒泡排序的轮数，内部的 for 用于让当前轮中的最大的数字“浮”到数组 a 的合适位置（随着一轮轮的“尘埃落定”，每轮所需的比较次数都递减）。
如果数组含有 5 个元素，那么我们只需要 4 轮排序，内层的循环次数从 4 开始，逐轮递减。

来看代码，我这里写的是 从大到小 排列：

#include <iostream>
using namespace std;

int main(){
    int a[5] = {1, 3, 4, 5, 2}; // 我想要从大到小排序
    for (int i = 0; i < 5 - 1; i++){ // 外层循环控制轮数
        for (int j = 0; j < 5 - 1 - i; j++){
            /*
            内层循环控制相邻的数的比较次数，每次都从头开始，但是每轮所需的比较次数都递减
            */
            if (a[j] < a[j + 1]){ // 如果前一个比后一个小，那么就交换
                swap(a[j], a[j + 1]);
                // swap 函数是一个用于 交换两个变量值 的标准库函数，可以直接拿来用
            }
        }
    }

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

    cout << endl;
    return 0;
}

5 4 3 2 1

有没有现成的函数呢？

有的兄弟有的。

#include <iostream>
#include <algorithm>  // std::sort
using namespace std;

int main() {
    int arr[5] = {5, 2, 8, 1, 3};
    int n{5};

    sort(arr, arr + n);  // 从小到大排序，这个 n 必须与数组元素个数一致

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

1 2 3 5 8

用 sort()，怎么从大到小排列呢？

你可以接着 sort() 再使用 reverse() 来反转！

#include <iostream>
#include <algorithm>  // std::sort
using namespace std;

int main() {
    int arr[5] = {5, 2, 8, 1, 3};
    int n{5};

    sort(arr, arr + n);  // 从小到大排序，这个 n 必须与数组元素个数一致
    reverse(arr, arr + n); // 反转！

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

8 5 3 2 1
← 返回首页