JavaScript冒泡算法原理与实现方法深入理解
文实例讲述了JavaScript冒泡算法。分享给大家供大家参考，具体如下：
在面试中经常会遇到面试官问到冒泡算法。今天总结一下。
有一组数，依次比较两个相邻的数，如果他们的顺序（如从大到小或从小到大等）错误就把他们交换过来。
我们先假设这一组数是有顺序的，那么我们找出它的规则。
1
我们按照从小到大的顺序依次交换长方形，得到以下的结果。
| 第一轮交换结果：CBAD 交换次数：3次 第二轮交换结果：BACD 交换次数：3次 第三轮交换结果：ABCD 交换次数：3次 |
结果：
| 1.比较轮数 n-1 2.每次比较次数 n-1 |
简单的冒泡算法
| <script>
var arr = [1,2,3,4]; var temp = null; var m = null; var n = null; // 双重for循环 for(var i=0;i<arr.length-1;i++){ //指定交换论数和交换次数（内循环控制交换次数） for(var a=0;a<arr.length-1;a++){ if(arr[a]<arr[a+1]){ //判断是否符合标准 temp = arr[a+1]; arr[a+1] = arr[a]; arr[a] = temp; } m++; } n++; } console.log(arr); console.log(m); console.log(n); </script> |
得到结果
| [4,3,2,1] 排序后 9 交换次数 3 轮数 |
在上述的例子中，有重复交换的数据，我们再来分析下。
| 第一轮交换： 第一次： 2 1 3 4 第二次： 2 3 1 4 第三次： 2 3 4 1 第二轮交换： 第一次： 3 2 4 1 第二次： 3 4 2 1 第三次： 3 4 2 1 第三轮交换： 第一次： 4 3 2 1 第二次： 4 3 2 1 第三次： 4 3 2 1 |
总结：
每一轮都会比较出一个最大值或最小值，然后后一轮没有必要再比较了
所以每比较一轮，就少比较一次。在第二轮的时候，有一个数不参与交换。
在第三轮的时候，有两个数不参与交换。依次类推。
所以，对上述代码优化。
| var arr = [1,2,3,4];
var temp = null; var m = null; var n = null; // 双重for循环 for(var i=0;i<arr.length-1;i++){ //指定交换论数和交换次数（内循环控制交换次数） for(var a=0;a<arr.length-1-i;a++){ if(arr[a]<arr[a+1]){ //判断是否符合标准 temp = arr[a+1]; arr[a+1] = arr[a]; arr[a] = temp; } m++; } n++; } console.log(arr); console.log(m); console.log(n); |
得到结果。
| [4,3,2,1] 排序后 6 交换次数 3 轮数 |
再来个稍微复杂点的例子。
| <script>
var arr = [66,22,23,39,77,25,88]; var temp = null; var m = null; var n = null; // 双重for循环 for(var i=0;i<arr.length-1;i++){ //指定交换论数和交换次数（内循环控制交换次数） for(var a=0;a<arr.length-1;a++){ if(arr[a]<arr[a+1]){ //判断是否符合标准 temp = arr[a+1]; arr[a+1] = arr[a]; arr[a] = temp; } m++; } n++; } console.log(arr); console.log(m); console.log(n); </script> |
结果：
| [88, 77, 66, 39, 25, 23, 22] 21 少交换了15次 6 |
结果其实已经提前完成，有重复交换次数。这次，我们加个判断，就是比较本次没有移动任何元素，那么说明已经完成结果。
| <script>
var arr = [66,22,23,39,77,25,88,11,33,23]; var temp = null; var m = null; var n = null; var flag = true; // 双重for循环 for(var i=0;i<arr.length-1;i++){ //指定交换论数和交换次数（内循环控制交换次数） flag = true; for(var a=0;a<arr.length-1-i;a++){ if(arr[a]<arr[a+1]){ //判断是否符合标准 temp = arr[a+1]; arr[a+1] = arr[a]; arr[a] = temp; flag = false; } m++; } n++; if(flag){ break; } } console.log(arr); console.log(m); console.log(n); </script> |
结果：
| [88, 77, 66, 39, 33, 25, 23, 23, 22, 11] 42 少交换了 39次 7 少交换了2 轮 |
发表评论