c++如何实现冒泡排序算法_c++基础排序代码演示【入门】

冒泡排序核心是外层控制轮数、内层控制比较范围且上限递减；升序时若arr[j] > arr[j+1]则交换，降序则改为arr[j]

冒泡排序的核心逻辑怎么写才不出错

冒泡排序本质是重复遍历数组，每次比较相邻两个元素，把较大（升序）的“冒”到末尾。关键不是嵌套循环本身，而是边界控制——外层循环控制轮数，内层循环控制每轮比较范围，且每轮后最大值已就位，所以内层上限要递减。

常见错误是内层循环写成 for (int j = 0; j ，导致越界访问或重复比较；正确写法是 <code>j （<code>i 为外层轮数索引）。

• 升序时：若 arr[j] > arr[j + 1]，交换
• 降序时：改为 arr[j]
• 数组长度为 n，最多需 n-1 轮，第 i 轮只需比较前 n - i - 1 对

用 std::vector 还是原生数组？参数传递要注意什么

新手常直接传 int arr[]，但 C++ 中数组名退化为指针，无法在函数内用 sizeof 算长度。推荐用 std::vector<int>&</int> 引用传参，既安全又支持动态大小。

如果坚持用原生数组，必须额外传入长度参数，比如 void bubbleSort(int arr[], int n)，否则函数内部根本不知道数组多长。

立即学习“C++免费学习笔记（深入）”；

灵图AI

灵图AI辅助设计平台

下载

• 用 vector：可直接调用 vec.size()，且自动管理内存
• 避免值传递 vector，否则拷贝开销大；务必加 & 引用
• 若函数声明为 void bubbleSort(const vector<int>& vec)</int>，则无法修改原数组——冒泡排序必须可变，所以不能加 const

如何提前终止优化性能

冒泡排序最差时间复杂度是 O(n²)，但最好情况（已有序）可以优化到 O(n)。做法是在每轮遍历时设置一个标志位，记录本轮是否发生交换；若全程没交换，说明已有序，直接 break。

这个优化不改变最坏复杂度，但对部分有序数据很实用，而且代码只多两行，值得加。

• 定义 bool swapped = false 在外层循环开始前
• 每次交换后设 swapped = true
• 内层循环结束后，若 !swapped，直接 return
• 注意：不要在内层循环里一发现没交换就 break——那只是当前这一对，不代表整轮无交换

完整可运行示例（含测试输出）

下面是一个带提前终止、使用 vector 的最小可用版本：

#include <iostream>
#include <vector>
using namespace std;
<p>void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}</p><p>int main() {
vector<int> nums = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(nums);
for (int x : nums) cout << x << " ";
cout << endl; // 输出：11 12 22 25 34 64 90
}</p>

真正容易被忽略的是：swap 函数来自 <utility></utility>，但 #include <iostream></iostream> 在某些编译器下会间接包含它，不报错；但严格起见，应显式加 #include <utility></utility>，否则换编译器可能失败。