冒泡算法的JavaScript实现

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

新老客户大回馈,云服务器低至5折

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

<!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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:vue内置指令详解——小白速会

下一篇:使用PostMan进行API自动化测试