登录
JS算法入门：图解“冒泡排序”，彻底搞懂双重循环的奥义
1. 前言：为什么我们需要排序？
哈喽大家好，我是心连欣。在上一篇文章中，我们做了一个“成绩管理系统”，能算出最高分和平均分。但是，如果老师想看一个 “从高分到低分” 的排名表，我们的程序就傻眼了，因为数组里的数据是乱序的。
虽然 JavaScript 提供了现成的 array.sort() 方法，但作为一名有追求的程序员，我们必须知道：排序的底层到底是怎么实现的？
今天，我们就来攻克排序算法的“Hello World”——冒泡排序。
2. 核心思想：像气泡一样“上浮”
冒泡排序的名字非常形象。想象一下水底的气泡，越轻的气泡（数值越小的元素）会慢慢浮到水面，而越重的气泡（数值越大的元素）会沉在水底。
但在我们的代码逻辑里（升序排列），我们通常反其道而行之：让最大的元素，像“重石头”一样，通过不断的交换，一步步“沉”到数组的末尾。
算法口诀：
- 两两比较： 从第一个开始，挨个比较相邻的两个数。
- 逆序交换： 如果前一个比后一个大，就交换它们。
- 一轮结束： 每一轮跑完，当前这一堆数里最大的那个，一定会被移到最右边。
3. 图解演示
假设我们要对 [5, 2, 9, 1] 进行升序排序：
第一轮（找出最大的9）：
- 比较 5 和 2：5 > 2，交换 →
[2, 5, 9, 1] - 比较 5 和 9：5 < 9，不换 →
[2, 5, 9, 1] - 比较 9 和 1：9 > 1，交换 →
[2, 5, 1, 9] - 结果： 9 已经就位（沉底了）。
第二轮（找出剩下的最大的5）：
- 比较 2 和 5：不换 →
[2, 5, 1, 9] - 比较 5 和 1：5 > 1，交换 →
[2, 1, 5, 9] - 结果： 5 也就位了。（注意：这一轮不需要再比 9 了，因为它已经是最大的）。
4. 代码实现：双重循环的奥义
冒泡排序的核心在于两层循环。
结果如下：
5. 深度解析：为什么是 length - 1 - i？
这是面试中最常考的细节，也是新手最容易晕的地方。
-
length - 1：因为我们是拿arr[j]和arr[j+1]比较。如果j走到了最后一个元素，j+1就会越界（undefined）。所以内层循环必须比数组长度少 1。 -
- i：这是性能优化的关键。- 当
i=0（第一轮）结束时，数组最后 1 个元素已经是最大值了。 - 当
i=1（第二轮）结束时，数组最后 2 个元素已经有序了。 - 所以，内层循环不需要每次都从头跑到尾，每过一轮，就可以少跑一步。
- 当
6. 进阶优化：如何让它更聪明？
上面的代码有个小缺陷：如果数组本来就是有序的（比如 [1, 2, 3, 4]），它还是会傻傻地跑完所有循环。
我们可以加一个 “哨兵” （标志位）来优化它。
7. 总结
冒泡排序虽然在实际工程中（处理海量数据时）效率不如快速排序，但它教会了我们两个极其重要的编程思想：
- 双重循环： 外层控制轮次，内层处理细节。这是处理二维数据、矩阵、复杂遍历的基础。
-
交换算法： 利用临时变量
temp交换数据，是链表操作、数组重排的基础。
课后思考：
目前的排序是从小到大（升序）。如果我想让成绩从高到低（降序）排列，只需要修改代码中的哪一行？（提示：就在 if 判断里）。
写算法就像搭积木，理解了冒泡排序，你就拿到了通往高级算法世界的第一把钥匙！加油！
