冒泡排序通过相邻元素比较交换使较大元素逐步移到末尾,每轮确定一个最大值位置,共执行n-1轮,内层循环范围递减,若某轮无交换则提前结束,C++实现包含优化机制,时间复杂度最坏O(n²)、最好O(n),空间复杂度O(1),适用于小数据量或教学场景。

冒泡排序是一种基础的排序算法,核心思想是通过相邻元素的比较和交换,将较大(或较小)的元素逐步“浮”到数组末尾。虽然效率不高,适合小数据量排序,但它是理解排序逻辑的良好起点。
冒泡排序的基本逻辑
冒泡排序的过程就像气泡上升一样:每一轮比较相邻两个元素,如果前一个比后一个大(假设升序排列),就交换它们的位置。这样每一趟遍历后,最大的元素就会移动到当前未排序部分的最后位置。
重复这个过程,直到整个数组有序。总共需要进行 n-1 趟比较,每趟比较的范围逐渐缩小。
实现步骤与关键点
要正确实现冒泡排序,需注意以下几点:
- 外层循环控制排序轮数:共执行 n-1 次,每轮确定一个最大值的位置
- 内层循环进行相邻比较:从第一个元素开始,比较到未排序部分的倒数第二个元素
- 交换条件判断:当前元素大于下一个元素时执行交换
- 优化机制可选:若某轮没有发生交换,说明数组已有序,可以提前结束
C++代码实现示例
下面是一个完整的C++冒泡排序实现,包含基础版本和优化版本:
#include <iostream>
#include <vector><p>void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
bool swapped;</int></p>
<pre class="brush:php;toolbar:false;">for (int i = 0; i arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// 如果这一轮没有发生交换,说明已经有序
if (!swapped) break;
}
}
int main() {
std::vector
std::cout <p>}</p>
该程序输出结果为:
排序前: 64 34 25 12 22 11 90排序后: 11 12 22 25 34 64 90
时间复杂度与适用场景
冒泡排序在最坏情况下的时间复杂度是 O(n²),最好情况(已有序)下为 O(n),空间复杂度为 O(1)。由于其简单直观,常用于教学演示或对极小规模数据排序。实际项目中更推荐使用标准库中的 std::sort 函数。
基本上就这些,理解了比较和交换的核心机制,就能轻松掌握冒泡排序的实现逻辑。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











