正确冒泡排序需两层循环，内层上限为n-1-i防越界，用std::swap保类型安全，加swapped标志提前退出；模板版应支持迭代器和自定义比较，但实际项目应优先用std::sort。
冒泡排序在 C++ 里写起来很简单，但直接套模板容易出错——尤其边界条件、优化逻辑和类型安全这三块最容易翻车。
怎么写一个基础但正确的 bubble_sort 函数
核心是两层循环：外层控制轮数（最多 n-1 轮），内层做相邻比较与交换。关键点不是“能跑”，而是“不越界、不漏排”：
- 内层循环上限必须是
n - 1 - i（i是外层轮数），否则每轮都扫到底，浪费且可能访问arr[n] - 用
std::swap而不是手写交换，避免自赋值问题和类型不兼容（比如std::string） - 数组长度建议用
size_t或带符号类型明确处理，别混用int和size_t做减法，否则i > n时会绕成极大正数
示例：
void bubble_sort(std::vector<int>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
for (size_t j = 0; j < n - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}怎么加提前退出优化（避免 O(n²) 变成真 O(n²)）
冒泡排序的天然优势是「发现已有序时可提前结束」，但很多人加了 bool swapped 却忘了重置它：
立即学习“C++免费学习笔记（深入）”；
- 每轮开始前必须设
swapped = false，否则一次没换就永远不进下一轮 - 只在发生交换时才置
true，不能靠if外部变量判断 - 这个优化对几乎有序的数据效果明显，但对随机数据影响不大，别误以为它能“大幅提速”
改写片段：
for (size_t i = 0; i < n - 1; ++i) {
bool swapped = false;
for (size_t j = 0; j < n - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}用模板写通用版本要注意什么
想让它支持 double、std::string 甚至自定义类？模板没问题，但有三个硬约束：
- 必须要求类型支持
operator>（或传入比较函数），否则arr[j] > arr[j + 1]编译不过 - 容器不能只假设
std::vector，最好用迭代器接口，比如接受RandomIt first, RandomIt last - 别在模板里用
using namespace std，会导致 ADL（参数依赖查找）异常或命名冲突
最小可用模板签名：
template <typename RandomIt, typename Compare = std::less<>>
void bubble_sort(RandomIt first, RandomIt last, Compare comp = {}) {
for (auto i = first; i != last; ++i) {
bool swapped = false;
for (auto j = first; j < last - 1 - (i - first); ++j) {
if (comp(*(j + 1), *j)) {
std::swap(*j, *(j + 1));
swapped = true;
}
}
if (!swapped) break;
}
}为什么你不该在实际项目里用它
不是代码写得不对，而是场景错配：
- STL 的
std::sort平均 O(n log n)，且对小数组自动切到插入排序，比手写冒泡稳得多 - 即使你只排 20 个元素，
std::sort的常数因子也更小；而冒泡的缓存不友好（频繁跨距访问）在现代 CPU 上代价更高 - 唯一合理用途：教学演示算法思想，或嵌入式环境禁用 STL 且数据量极小（
真正要动手写排序时，先问自己：是不是非得手写？是不是非得冒泡？这两个“是”同时成立的情况，比想象中少得多。
