冒泡排序Bubble sort

比较相邻元素并交换逆序对，让较大元素逐轮移向尾部。

核心约束: 每轮确定一个未排序区间的最大元素。
适用问题: 基础教学与理解相邻交换。
边界与取舍: 一般不是工程中通用排序的合适选择。

时间与空间#

n 为元素数；每轮比较相邻元素。

时间复杂度: 平均 / 最坏 $O(n^{2})$ ；带提前退出时最好 $O(n)$
辅助空间: $O(1)$

只有一轮未交换就退出的实现才能在已排序输入上达到线性时间。只交换严格逆序元素时稳定；“近乎有序”本身不足以保证所有冒泡实现都接近线性。

基础原理参考资料

NIST · Bubble sort相邻交换、无交换退出和二次时间分析。