JavaScript冒泡算法原理與實(shí)現(xiàn)方法的詳細(xì)解析

發(fā)布時(shí)間：2020-07-18 15:23:32 來(lái)源：億速云閱讀：167 作者：小豬欄目：web開發(fā)

這篇文章主要講解了JavaScript冒泡算法原理與實(shí)現(xiàn)方法的詳細(xì)解析，內(nèi)容清晰明了，對(duì)此有興趣的小伙伴可以學(xué)習(xí)一下，相信大家閱讀完之后會(huì)有幫助。

本文實(shí)例講述了JavaScript冒泡算法。分享給大家供大家參考，具體如下：

在面試中經(jīng)常會(huì)遇到面試官問(wèn)到冒泡算法。今天總結(jié)一下。

###概念

有一組數(shù)，依次比較兩個(gè)相鄰的數(shù)，如果他們的順序（如從大到小或從小到大等）錯(cuò)誤就把他們交換過(guò)來(lái)。

我們先假設(shè)這一組數(shù)是有順序的，那么我們找出它的規(guī)則。

JavaScript冒泡算法原理與實(shí)現(xiàn)方法的詳細(xì)解析

我們按照從小到大的順序依次交換長(zhǎng)方形，得到以下的結(jié)果。

第一輪交換結(jié)果：CBAD     交換次數(shù)：3次
第二輪交換結(jié)果：BACD     交換次數(shù)：3次
第三輪交換結(jié)果：ABCD     交換次數(shù)：3次

結(jié)果：

1.比較輪數(shù) n-1
2.每次比較次數(shù) n-1

###簡(jiǎn)單的冒泡算法

<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è)賮?lái)分析下。

第一輪交換：
第一次： 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è)最大值或最小值，然后后一輪沒(méi)有必要再比較了
所以每比較一輪，就少比較一次。在第二輪的時(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ù)

再來(lái)個(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è)判斷，就是比較本次沒(méi)有移動(dòng)任何元素，那么說(shuō)明已經(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 輪

看完上述內(nèi)容，是不是對(duì)JavaScript冒泡算法原理與實(shí)現(xiàn)方法的詳細(xì)解析有進(jìn)一步的了解，如果還想學(xué)習(xí)更多內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道。

向AI問(wèn)一下細(xì)節(jié)

JavaScript冒泡算法原理與實(shí)現(xiàn)方法的詳細(xì)解析

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽