JavaScript冒泡算法原理與實(shí)現(xiàn)方法深入理解
本文實(shí)例講述了JavaScript冒泡算法。分享給大家供大家參考,具體如下:
在面試中經(jīng)常會(huì)遇到面試官問到冒泡算法。今天總結(jié)一下。
###概念
有一組數(shù),依次比較兩個(gè)相鄰的數(shù),如果他們的順序(如從大到小或從小到大等)錯(cuò)誤就把他們交換過來。
我們先假設(shè)這一組數(shù)是有順序的,那么我們找出它的規(guī)則。
我們按照從小到大的順序依次交換長方形,得到以下的結(jié)果。
第一輪交換結(jié)果:CBAD 交換次數(shù):3次
第二輪交換結(jié)果:BACD 交換次數(shù):3次
第三輪交換結(jié)果:ABCD 交換次數(shù):3次
結(jié)果:
1.比較輪數(shù) n-1
2.每次比較次數(shù) n-1
###簡單的冒泡算法
<script> var arr = [1,2,3,4]; var temp = null; var m = null; var n = null; // 雙重for循環(huán) for(var i=0;i<arr.length-1;i++){ //指定交換論數(shù)和交換次數(shù)(內(nèi)循環(huán)控制交換次數(shù)) for(var a=0;a<arr.length-1;a++){ if(arr[a]<arr[a+1]){ //判斷是否符合標(biāo)準(zhǔn) temp = arr[a+1]; arr[a+1] = arr[a]; arr[a] = temp; } m++; } n++; } console.log(arr); console.log(m); console.log(n); </script>
得到結(jié)果
[4,3,2,1] 排序后
9 交換次數(shù)
3 輪數(shù)
在上述的例子中,有重復(fù)交換的數(shù)據(jù),我們?cè)賮矸治鱿隆?/p>
第一輪交換:
第一次: 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
總結(jié):
每一輪都會(huì)比較出一個(gè)最大值或最小值,然后后一輪沒有必要再比較了
所以每比較一輪,就少比較一次。在第二輪的時(shí)候,有一個(gè)數(shù)不參與交換。
在第三輪的時(shí)候,有兩個(gè)數(shù)不參與交換。依次類推。
所以,對(duì)上述代碼優(yōu)化。
var arr = [1,2,3,4]; var temp = null; var m = null; var n = null; // 雙重for循環(huán) for(var i=0;i<arr.length-1;i++){ //指定交換論數(shù)和交換次數(shù)(內(nèi)循環(huán)控制交換次數(shù)) for(var a=0;a<arr.length-1-i;a++){ if(arr[a]<arr[a+1]){ //判斷是否符合標(biāo)準(zhǔn) temp = arr[a+1]; arr[a+1] = arr[a]; arr[a] = temp; } m++; } n++; } console.log(arr); console.log(m); console.log(n);
得到結(jié)果。
[4,3,2,1] 排序后
6 交換次數(shù)
3 輪數(shù)
再來個(gè)稍微復(fù)雜點(diǎn)的例子。
<script> var arr = [66,22,23,39,77,25,88]; var temp = null; var m = null; var n = null; // 雙重for循環(huán) for(var i=0;i<arr.length-1;i++){ //指定交換論數(shù)和交換次數(shù)(內(nèi)循環(huán)控制交換次數(shù)) for(var a=0;a<arr.length-1;a++){ if(arr[a]<arr[a+1]){ //判斷是否符合標(biāo)準(zhǔn) temp = arr[a+1]; arr[a+1] = arr[a]; arr[a] = temp; } m++; } n++; } console.log(arr); console.log(m); console.log(n); </script>
結(jié)果:
[88, 77, 66, 39, 25, 23, 22]
21 少交換了15次
6
結(jié)果其實(shí)已經(jīng)提前完成,有重復(fù)交換次數(shù)。這次,我們加個(gè)判斷,就是比較本次沒有移動(dòng)任何元素,那么說明已經(jīng)完成結(jié)果。
<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循環(huán) for(var i=0;i<arr.length-1;i++){ //指定交換論數(shù)和交換次數(shù)(內(nèi)循環(huán)控制交換次數(shù)) flag = true; for(var a=0;a<arr.length-1-i;a++){ if(arr[a]<arr[a+1]){ //判斷是否符合標(biāo)準(zhǔn) 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>
結(jié)果:
[88, 77, 66, 39, 33, 25, 23, 23, 22, 11]
42 少交換了 39次
7 少交換了2 輪
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運(yùn)行工具:http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
- 通過js示例講解時(shí)間復(fù)雜度與空間復(fù)雜度
- Javascript校驗(yàn)密碼復(fù)雜度的正則表達(dá)式
- JS算法教程之字符串去重與字符串反轉(zhuǎn)
- 如何通過JS實(shí)現(xiàn)日歷簡單算法
- 基于JS實(shí)現(xiàn)計(jì)算24點(diǎn)算法代碼實(shí)例解析
- 基于原生js實(shí)現(xiàn)九宮格算法代碼實(shí)例
- JS求解兩數(shù)之和算法詳解
- js實(shí)現(xiàn)無限層級(jí)樹形數(shù)據(jù)結(jié)構(gòu)(創(chuàng)新算法)
- 如何用JavaScript學(xué)習(xí)算法復(fù)雜度
相關(guān)文章
全面解析Bootstrap中tab(選項(xiàng)卡)的使用方法
這篇文章主要為大家全面解析Bootstrap中tab(選項(xiàng)卡)的使用方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-06-06微信小程序getLocation 需要在app.json中聲明permission字段
這篇文章主要介紹了微信小程序getLocation 需要在app.json中聲明permission字段,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03javascript面向?qū)ο笾畉his關(guān)鍵詞用法分析
這篇文章主要介紹了javascript面向?qū)ο笾畉his關(guān)鍵詞用法分析,以實(shí)例形式分析了在不同場(chǎng)合下this使用中的特性及相關(guān)使用技巧,需要的朋友可以參考下2015-01-01javascript中的數(shù)字與字符串相加實(shí)例分析
javascript中的數(shù)字與字符串相加實(shí)例分析,學(xué)習(xí)js的朋友可以參考下。2011-08-08微信小程序網(wǎng)絡(luò)請(qǐng)求模塊封裝的具體實(shí)現(xiàn)
大家做小程序項(xiàng)目的時(shí)候肯定會(huì)遇到數(shù)據(jù)對(duì)接需求,下面這篇文章主要給大家介紹了關(guān)于微信小程序網(wǎng)絡(luò)請(qǐng)求模塊封裝的具體實(shí)現(xiàn),文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-03-03js循環(huán)中使用正則失效異常的踩坑實(shí)戰(zhàn)
這篇文章主要給大家介紹了關(guān)于js循環(huán)中使用正則失效異常的踩坑實(shí)戰(zhàn),文中通過實(shí)例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2023-05-05