# Bubble Sort 冒泡排序 · `BubbleSort.cpp`

最基础的比较排序：每轮把相邻两个元素比一遍，大的往右挪。每一轮都有一个最大值"冒"到末尾
当然也可以写成向左挪的

## 一、复杂度与特性

| 项目                | 值             | 说明                                                   |
| ------------------- | -------------- | ------------------------------------------------------ |
| 时间（最好）        | O(n)           | 数据已有序时，一轮下来没有交换，靠`swapped` 直接退出 |
| 时间（平均 / 最坏） | O(n²)         | 逆序是最坏情况，比较次数恰好 n(n-1)/2                  |
| 空间                | O(1)           | 原地排序，只有`swapped` 一个额外布尔量               |
| 稳定性              | **稳定** | 相等时不交换，同值元素的相对顺序不变                   |
| 最坏交换次数        | n(n-1)/2       | 每一对逆序都要换一次                                   |

## 二、代码

```cpp
void bubble_sort(std::vector<int> &a)
{
    const int n = static_cast<int>(a.size());
    for (int i = 0; i < n - 1; ++i)
    {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j)
        {
            if (a[j] > a[j + 1]) // 比较大小，如果该元素大于下一个元素就交换位置，得出的数组是升序的
            {
                std::swap(a[j], a[j + 1]);
                swapped = true; // 标记有交换操作
            }
        }
        if (!swapped)
            break; // 这一轮没有任何交换 ⇒ 已经有序，直接退出排序
    }
}
```

要点：

1. 内层边界是 **`n - 1 - i`**：末尾的 `i` 个元素已经就位，不用再进行比较
2. `swapped`提前退出
3. `a[j] > a[j+1]` 相等不交换，所以相同值的元素不会被交换