JS冒泡排序最基本的算法解释

马黑黑

冒泡算法用于给对象排序，其名称源于排序算法实现的过程：两两相邻的数字作比较并可能调整位置（条件成立才会调整），直至完成整个排序工作，过程中被排序对象犹如水泡一样一一浮出水面，故名之曰冒泡算法。

通常，我们将要排序的乱序数字存入一个数组中，然后对这个数组对象的数组元素进行排序操作。在JS里，声明一个数组可以是这样：

let myAr = [960,4513,2,0.3,57,169,75,6,102,-9];

数组名称是 myAr，中括号里的数字是组成数组的各个元素，称之为数组元素，它们现在是乱序的，我们的任务是将其从小到大排好序（反过来排序也是可以的）。中括号里的数字用逗号隔开，每一个数字都是数组 myAr 的组成元素，数组元素下标从 0 开始，我们读取和改变每一个数组元素都是通过数组下标来完成（用中括号表示数组下标）：

myAr[0] → 960
myAr[0] = 1000 → 改变数组值，此时 myAr[0] 从960变成了1000

下面，我们开始编写我们的冒泡算法函数：

function bubbleSort(ar) {
        let len = ar.length;
        let exch = 0;
        for (i=0; i<len; i++) {
                for (j=0; j<len -1 - i; j++) {
                        if (ar[j] > ar[j+1]) {
                                exch = ar[j+1];
                                ar[j+1] = ar[j];
                                ar[j] = exch;
                        }
                }
        }
        return ar;
}

函数我们命名为 bubbleSort，带有一个参数 ar，这个参数是个函数要处理的假定的数组对象。函数名称和参数都是我们自定义的。

函数中，一开始我们声明了两个变量：len 是读取数组长度的变量它将作为循环次数的依据，exch 是交换变量，它将行使二传手的权限，为数字两两比较时暂存和传输数字，它的初始值设定为0，没啥意思，仅表明这是一个数值变量，设定值不会影响将来的数字交换。

接着是重点也是难点：双循环算法。第一个 for 以 i 为变量依托，是外层循环，从 0 开始逐一循环下去，直到 i 增量到第 len 次（len是我们已赋值的变量，其值是数组长度）。外循环每一个循环都要运行一次内循环，即以 j 为步进变量依托的循环，j 也是从 0 开始循环，它的循环终止次数是第 len-1-i 次。为什么是这么多次？这是配合和跟进外循环变量 i 的变化而得出的结果，是冒泡算法长期实践推演出来的数值，这里不展开讨论。每一次循环都要做一个假设：如果 ar[j]（我） 大于下一个邻居 ar[j+1]，那么——

exch = ar[j+1] → 二传手 exch 暂时保管邻居的值
ar[j+1] = ar[j] → 邻居接管我的值
ar[j] = exch → 二传手把它代管的邻居的值交给我

看，如果我大于邻居，邻居就是比我小，他得往左边靠，我则往右边靠。但我和邻居交换位置的做法很奇怪，我们没有真正换位，而是换值，换的时候通过第三方也就是二传手 exch 帮忙。

数组元素通过双循环不断地在做比较、数值交换，最终冒泡任务完成，小的依次靠往左边去，大的则依次往右边挪。循环结束后，参数 ar 所代表的数组各元素值已经更改为从小到大的有序状态。函数可以返回一个东东给人家调用，return ar 就是把排好序后的参数 ar 输送出去让其他子程序或函数调用。

我们可以在控制台查看排序后 myAr 数组的情况：

let newAr = bubbleSort(myAr);
console.log(newAr);

或者如果不习惯使用控制台，可以这样查看结果：

let str = bubbleSort(myAr).toString(); //数组变为字串
alert(str);

【附】for语句双循环的进一步解释：

i 从 0 开始：i=0 时，内循环 j 的第一次循环执行时 j 从 0 开始，它比较并可能调整第一个 ar[j] 和第二个ar[j+1] 数组元素；接着，j=1，这次它比较并可能调整第二和第三个数组元素；j=2时，处理第三和第四个数组元素，……，直至 j=len -1 - i (i此时是0）时终止第一个循环。i步进为1，内循环又演变一次，……，直至 i=len 时终止并退出循环，任务完成。

红影

这个双循环的确有点难的。

马黑黑

红影 发表于 2022-2-12 11:50
这个双循环的确有点难的。

双循环其实经常用到。例如，用JS写一个表格，就必须用到至少双循环。

红影

马黑黑 发表于 2022-2-12 11:52
双循环其实经常用到。例如，用JS写一个表格，就必须用到至少双循环。

以这个数组为例，你一共设置了10组数据。
i看懂了，for (i=0; i<len; i++)，因为len=10，所以i的值是0-9共10组数据，
下面一个判断没懂。
for (j=0; j<len -1 - i; j++)，j也是按条件累加的，当ar[j] > ar[j+1])，那么用j+1的位置来替换，也就是后移。
但是如何这样能去比对出全部呢？比如0位的960是小于1位的4513的，那么它的位置不动，再跟2位的2相比，则960大于2，960的位置要后移。这时，只是960和2换位了，4513呢？它的位置在哪呢？
接下来是2和0.3相比，同样需要换位，那么原本的960和4513在哪个位置？

马黑黑

红影 发表于 2022-2-12 13:09
以这个数组为例，你一共设置了10组数据。
i看懂了，for (i=0; i

关于j的步进边界，或说上限范围，它是动态的，作为内循环，它每一次发生都不一样，这是通过推演得出的变化规律：

lent - 1 - i

j不论如何，与外循环的 i 一样，每一次循环都在步进，意思就是说，第一回循环，比较 ar[0] 和 ar[1]，第二次循环 比较 ar[1] 和 [ar2]，最后会遍历所有的数组元素。lent - 1 - i 次的遍历恰好不多不少完成遍历。

加林森

慢慢学习

红影

马黑黑 发表于 2022-2-12 16:17
关于j的步进边界，或说上限范围，它是动态的，作为内循环，它每一次发生都不一样，这是通过推演得出的变 ...

这里面感觉省了好多步骤的感觉。

马黑黑

红影 发表于 2022-2-12 18:29
这里面感觉省了好多步骤的感觉。

没有的。外循环 i 的每一次循环，j 都做从 0 到 len - 1 - i 次循环，一次都没拉下。i 的 第一次循环（i为0时），j 做了从 0 到 len - 1 次，一次类推，每一次i的循环，j都能遍历一次数字比较。

红影

马黑黑 发表于 2022-2-12 20:13
没有的。外循环 i 的每一次循环，j 都做从 0 到 len - 1 - i 次循环，一次都没拉下。i 的 第一次循环（i ...

这样的嵌套很巧妙

马黑黑

红影 发表于 2022-2-12 20:27
这样的嵌套很巧妙

但弄不好会无限循环，就是传说中的死循环，退不出来，只好强行中断（而不是关闭）浏览器

红影

马黑黑 发表于 2022-2-12 20:52
但弄不好会无限循环，就是传说中的死循环，退不出来，只好强行中断（而不是关闭）浏览器

进入无限循环后，对内存影响比较大吧。

马黑黑

红影 发表于 2022-2-13 11:40
进入无限循环后，对内存影响比较大吧。

会把内存耗尽

红影

马黑黑 发表于 2022-2-13 19:39
会把内存耗尽

还是挺可怕的呢。

马黑黑

红影 发表于 2022-2-13 20:07
还是挺可怕的呢。

重启计算机就行

红影

马黑黑 发表于 2022-2-13 20:15
重启计算机就行

然后不再碰死循环的东东。

马黑黑

红影 发表于 2022-2-13 20:30
然后不再碰死循环的东东。

修改再运行，不怕的

红影

马黑黑 发表于 2022-2-13 20:58
修改再运行，不怕的

对哦，自己知道是哪个，就可以针对性地修改。呵呵，我的第一反应是避开而不是去解决

马黑黑

红影 发表于 2022-2-14 13:43
对哦，自己知道是哪个，就可以针对性地修改。呵呵，我的第一反应是避开而不是去解决

鸵鸟主义是安全的

红影

马黑黑 发表于 2022-2-14 13:51
鸵鸟主义是安全的

这是我常用共的政策，就如看不到的苦难也都不存在一样。

马黑黑

红影 发表于 2022-2-14 14:58
这是我常用共的政策，就如看不到的苦难也都不存在一样。

挺好的