Overview
Bubble Sort 会比较相邻元素，顺序错误就 swap。每一轮都会把当前最大的未确定元素推到右侧。
Analogy
像水里的气泡一样，较大的值会在每一轮逐步“浮”到右边。
Step-by-step
- 遍历数组，比较 arr[j] 和 arr[j+1]。
- 如果 arr[j] > arr[j+1]，就执行 swap。
- 一轮结束后，最大元素会固定在末尾。
- 下一轮缩小范围，因为尾部已经 sorted。
- 如果一轮没有 swap，提前结束。
Visual
Pass 1: [5,3,8,1,2] -> [3,5,1,2,8]，之后每轮扫描范围都会缩小。
Common mistakes
- 没有缩小 inner loop 的边界。
- 使用 >= 导致稳定性被破坏。
- 出现 0 swaps 的一轮却没有提前退出。
Practice questions
- 在已排序输入上比较有/无 early exit 的比较次数。
- 解释 Bubble Sort 为什么是 stable。
- 改成降序排序并验证结果。
Time
O(n²) worst/average, O(n) best with early exit