JavaScript冒泡算法原理与实现方法深入理解

文实例讲述了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 轮

WordPress主题下载,WordPress免费主题下载,网站源码模板下载


下载说明:
1. 本站所有资源来源于网络和用户上传,如有侵权请联系站长
2. 本站分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,商用请支持正版!不得违反国家法律,否则后果自负!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!

本站的资源均来自于互联网,仅为资源共享、学习参考之目的,其版权均归原作者及其网站所有,如有侵权请留言联系:admin,转转请注明出处:http://zhanmr.com/6958.htm

发表评论

电子邮件地址不会被公开。 必填项已用*标注