冒泡排序（Bubble Sort）是最简单和最通用的排序方法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序 [2]。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像气泡一样，于是将这种排序算法形象地称为冒泡排序 。
❓怎么排的
从数组开头开始，依次比较相邻两个元素，如果前一个比后一个大就交换位置，每轮遍历结束后最大的元素会沉到末尾，重复这个过程直到整个数组有序。
❓性能怎么样
平均和最坏时间复杂度：O(n²)，数据完全逆序时需要最多比较次数。
最好情况：O(n)，当数组已经有序时只需遍历一次。
空间复杂度：O(1)，是原地排序算法。
稳定性：稳定排序，相同元素的相对位置不会改变。
❓啥时候用它
适合小规模数据排序（n≤100）或教学演示，数据基本有序时效率较高，大规模数据建议用快速排序、归并排序等更高效算法。
动画怎么看：以 [5, 1, 4, 2] 为例
第一轮从左向右比较相邻元素：5 与 1 交换，得到 [1, 5, 4, 2]；5 与 4 交换，得到 [1, 4, 5, 2]；5 与 2 再交换，得到 [1, 4, 2, 5]。这一轮结束后，当前最大值 5 已经“冒”到最右侧，后续无需再参与比较。第二轮只处理前 3 个位置，最终得到 [1, 2, 4, 5]。
带提前退出的伪代码
for end = n - 1 down to 1:
swapped = false
for i = 0 to end - 1:
if a[i] > a[i + 1]:
swap(a[i], a[i + 1])
swapped = true
if swapped == false:
break
加入 swapped 后，已排序输入只检查一轮，最好时间复杂度为 O(n)；平均和最坏情况仍为 O(n²)，额外空间为 O(1)。只在前一个元素“严格大于”后一个元素时交换，相等元素不会互换先后顺序，因此它是稳定排序。冒泡排序的教学价值很高，但处理大量数据时通常不如标准库中的高效排序算法。
算法原理
假定序列中有n个数，要进行从小到大的排序。若参与排序的数组元素共有n个，则需要n-1轮排序。在第í轮排序中，从左端开始，相邻两数比较大小，若反序则将两者交换位置，直到比较第n+1-i个数为止。第1个数与第2个数比较，第2个数和第3个数比较，一直到第n-i个数与第n+1-i个数比较，一共处理 n-i次。此时，第n+1-i个位置上的数已经有序，后续就不需要参加以后的排序。
（1）第1轮冒泡排序先从第1个数和第2个数开始比较，若第1个数大于第2个数，则需要交换两者的位置；否则保持不变。重复这一过程，直到处理完本轮数列中最后两个数。
（2）第2轮冒泡排序与第1轮冒泡排序进行相同的排序，使大的数交换到n-2的位置上。
（3）重复以上过程，共需经过n-1轮冒泡排序后，数据实现升序排序。