×

Web前端开发:JavaScript冒泡算法

作者:andy0012020.07.31来源:Web前端之家浏览:126评论:0
关键词:js

Web前端开发:JavaScript冒泡算法。

有一组数,依次比较两个相邻的数,如果他们的顺序(如从大到小或从小到大等)错误就把他们交换过来。

我们先假设这一组数是有顺序的,那么我们找出它的规则。

20206491532626.png

我们按照从小到大的顺序依次交换长方形,得到以下的结果。

第一轮交换结果: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 轮

温馨提示:本文作者系 ,经Web前端之家编辑修改或补充,转载请注明出处和本文链接:
https://jiangweishan.com/article/js20200731a2.html

网友评论文明上网理性发言 已有0人参与

发表评论:

最新留言

  • 访客

    你可以加群去问...

  • 访客

    怎么注册?不会...

  • ajoy

    说法可以是一样的,毕竟JS和JQ都是有“血缘关系”的,你可以自己改下不就可以了吗,哈哈!...

  • 访客

    标题是JS用了JQ误人子弟呢...

  • absoy

    vue居然还能这么玩,期待你们vue3.0中文版教程。...

  • caij2

    github也中了新冠病毒了吧,哈哈!...

  • 访客

    收藏啦...

  • Web前端之家

    当然都可以被import,如何去设置,还要看你的具体项目要求。...

首页|JavaScript|HTML|HTML4|HTML5|CSS3|开发工具|性能优化|移动开发|前端教程|性能优化|开发工具|酷站欣赏|UI设计|前端教程

Copyright © 2020 Web前端之家(www.jiangweishan.com) 版权所有 All Rights Reserved.
粤ICP备12067512号-1

Copyright Your WebSite.Some Rights Reserved.

Powered By Z-BlogPHP 1.6.4 Valyria