这篇文章主要讲解了JavaScript冒泡算法原理与实现方法的详细解析,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。
本文实例讲述了JavaScript冒泡算法。分享给大家供大家参考,具体如下:
在面试中经常会遇到面试官问到冒泡算法。今天总结一下。
###概念
有一组数,依次比较两个相邻的数,如果他们的顺序(如从大到小或从小到大等)错误就把他们交换过来。
我们先假设这一组数是有顺序的,那么我们找出它的规则。
我们按照从小到大的顺序依次交换长方形,得到以下的结果。
第一轮交换结果: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 轮
看完上述内容,是不是对JavaScript冒泡算法原理与实现方法的详细解析有进一步的了解,如果还想学习更多内容,欢迎关注亿速云行业资讯频道。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。