冒泡算法的JavaScript实现

2018-06-24 01:48:53来源：未知阅读 ()

用户按照指定格式输入数字，点击排序返回对应的结果：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>js实现冒泡排序</title>
    <style type="text/css">
        *{
            margin: 0;
            padding: 0;
        }
        .wrapper{
            width: auto;
            min-width: 990px;
        }
        .main{
            overflow: hidden;
            width: 500px;
            line-height: 30px;
            margin: 200px auto;
        }
        .main *{
            float: left;
        }
        .text_box{
            box-sizing: border-box;
            height: 30px;
            width: 400px;
            border:1px solid #999;
        }
        .right{
            height: 30px;
            width: 50px;
            border:1px solid #999;
            border-left: none;
        }
    </style>
</head>
<body>
    <div class="wrapper">
        <div class="main">
            <input class="text_box" type="text" name="text_box" placeholder="输入数字，并用','号分隔">
            <input id="up_counter" class="right" type="button" value="增序">
            <input id="down_counter" class="right" type="button" value="减序">
            <p id="sorted"></p>
        </div>
    </div>
<script>
    var text = document.querySelector(".main>input");
    var upCounter = document.getElementById("up_counter");
    var downCounter = document.getElementById("down_counter");
    var sorted = document.getElementById("sorted");
    function getNum() {
        if(!text.value||isNaN(text.value.replace(/,/g,""))){
            alert("输入数字，并用','号分隔");
            return [];
        }else{
            return text.value.split(",").map(function (value) { return +value });
        };
    };
    upCounter.onclick = function (ev) {
        var numArray = getNum();
        for(var i=0; i<numArray.length-1; i++){
            for(var j = i+1; j<numArray.length; j++){
                if(numArray[i]>numArray[j]){
                    var temp = numArray[i];
                    numArray[i] = numArray[j];
                    numArray[j] = temp;
                }
            }
        };
        sorted.innerText = numArray.join("——");
    };
    downCounter.onclick = function (ev) {
        var numArray = getNum();
        for(var i=0; i<numArray.length-1; i++){
            for(var j = i+1; j<numArray.length; j++){
                if(numArray[i]<numArray[j]){
                    var temp = numArray[i];
                    numArray[i] = numArray[j];
                    numArray[j] = temp;
                }
            }
        };
        sorted.innerText = numArray.join("——");
    };
</script>
</body>
</html>

1，冒泡是一个两两相比的过程，若预定索引0的位置放最小值（从小到大排序），那么数组索引为0的元素就去和剩下所有元素依次比较，当遇到比自己小的，就交换位置，始终保持0位是最小的值。按照复杂程度最大做如下解释：

　　①假设数组A长度为 n，外部循环需要进行n-1次，而每次外部循环，它的内部循环就要进行n-i次比较(1≤i≤n-1)，平均值为n/2次，一共就是 n(n-1)/2 次，时间复杂度为O(n^2）

　　②每次内部循环需要进行三次操作：

　　　　　　　　　　　　var temp = numArray[i];　　//1
                    numArray[i] = numArray[j];　　//2
                    numArray[j] = temp;　　//3
　 因此最终需要进行 3n(n-1)/2次操作时间复杂度为O(n^2）
ps：决定算法复杂度的是执行次数最多的语句，而且数量级差别过大的时候，会忽略影响不大的常量，所以n(n-1)/2的复杂度和3n(n-1)/2的复杂度都表示为O(n^2）

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有