冒泡排序 Bubble Sort
交换排序 · 最好懂的排序入门
什么是冒泡排序
冒泡排序的名字来自水里的气泡：相邻两个数两两比较，谁大就往后挪，一趟扫下来，最大的那个数就像气泡一样一路「冒」到数组末尾。下一趟在剩下的范围里再冒出次大的……如此重复，数组从右往左逐渐排好。它几乎不需要额外空间、也最容易在脑子里跑通，是理解「比较—交换」这类排序的起点。
它怎么做
每一趟从左到右走：比较位置 j 和 j+1，如果左边比右边大就交换。走到本趟末尾，最大值必然落到最右的未排序位置——它就「就位」变绿、退出后续比较。点「下一步」看下面这组 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：留意右侧绿色区域每趟长一格，而黄色的比较对一路向右推。
第 1 轮
1function bubbleSort(a: number[]): number[] {
2 const n = a.length;
3 for (let end = n - 1; end > 0; end--) {
4 for (let j = 0; j < end; j++) {
5 if (a[j] > a[j + 1]) {
6 [a[j], a[j + 1]] = [a[j + 1], a[j]];
7 }
8 }
9 }
10 return a;
11}
n10
pass1
j0
a[j]7
a[j+1]6
swapCount0
sortedFrom10
1 / 145
复杂度与适用
时间 O(n²)（n 趟、每趟约 n 次比较）、只用常数额外空间、稳定（相等元素不会交换、保持原序）。它慢在交换太频繁，实际工程几乎不用；价值全在教学——把「排序」这件事拆到最直观。加一个「本趟没发生交换就提前结束」的小判断，可让近乎有序的数据快到 O(n)。
冒泡的短板：只从一个方向扫，尾部的小元素（「乌龟」）每趟只能往前挪一格，很慢。
改进：鸡尾酒排序来回双向冒泡、两端一起收缩，乌龟一趟就能回家。
改进：鸡尾酒排序来回双向冒泡、两端一起收缩，乌龟一趟就能回家。
想看双向版怎么改进它，去鸡尾酒排序页对照着走一遍；两页用的是同一套比较—交换动作，差别只在扫描方向。