本文实例讲述了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 轮
感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。
更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
RTX 5090要首发 性能要翻倍!三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB,每个模块容量为2GB。其速度预设为32 Gbps(PAM3),但也可以降至28 Gbps,以提高产量和初始阶段的整体性能和成本效益。
据三星表示,GDDR7内存的能效将提高20%,同时工作电压仅为1.1V,低于标准的1.2V。通过采用更新的封装材料和优化的电路设计,使得在高速运行时的发热量降低,GDDR7的热阻比GDDR6降低了70%。
更新日志
- 齐豫.2003-THE.UNHEARD.OF.CHYI.3CD【苏活音乐】【WAV+CUE】
- 黄乙玲1986-讲什么山盟海誓[日本东芝版][WAV+CUE]
- 曾庆瑜1991-柔情陷阱[台湾派森东芝版][WAV+CUE]
- 陈建江《享受男声》DTS-ES6.1【WAV】
- 群星《闪光的夏天 第5期》[FLAC/分轨][392.38MB]
- 徐小凤《三洋母带》1:1母盘直刻[WAV+CUE][981M]
- 王菲1995《菲靡靡之音》[香港首版][WAV+CUE][1G]
- 《双城之战》主题小游戏现已上线 扮演金克丝探索秘密基地
- 《霍格沃茨之遗》PS5Pro画面对比:光追性能显著提升
- 《怪猎荒野》PS5Pro主机版对比:B测性能都不稳定
- 黄宝欣.1992-黄宝欣金装精选2CD【HOMERUN】【WAV+CUE】
- 群星.1996-宝丽金流行爆弹精丫宝丽金】【WAV+CUE】
- 杜德伟.2005-独领风骚新歌精选辑3CD【滚石】【WAV+CUE】
- 安与骑兵《心无疆界》[低速原抓WAV+CUE]
- 柏菲唱片-群星〈胭花四乐〉2CD[原抓WAV+CUE]