算法排序

算法

冒泡排序

冒泡排序：小的往前排，打的往后排，实现从小到大。
两两比较，若前一项比后面一项小则保持排列位置，若前一项比后一项大，交换位置。

// 注释的写法的规范写法:

// bubble：冒泡排序
//  @parameter
//    ary：[array]需要实现排序的数组
//  @return
//    [array]排序后的数组(升序)
// by team on 2018/02/02

function bubble(ary) {
    //->外层循环控制的是比较的轮数
    for (var i = 0; i < ary.length - 1; i++) {
        //->里层循环控制每一轮比较的次数
        for (var j = 0; j < ary.length - 1 - i; j++) {
            //ary[j]:当前本次拿出来这一项
            //ary[j+1]:当前项的后一项
            if (ary[j] > ary[j + 1]) {
                //->当前这一项比后一项还要大,我们让两者交换位置
                var temp = ary[j];
                ary[j] = ary[j + 1];
                ary[j + 1] = temp;
            }
        }
    }
    return ary;
}
var ary = [12, 13, 23, 14, 16, 11];
console.log(bubble(ary));

递归

(函数自己调用自己)

function fn(num) {
    console.log(num);
    if(num ==0){
        return;
    }
    fn(num - 1);
}
fn(10);


//=>需求：1~10以内的所有偶数乘积
function fn(num) {
    if (num <= 1) {
        return 1;
    }
    if (num % 2 === 0) {
        return num * fn(num - 1);
    }
    return fn(num - 1);
}
var result = fn(10);
console.log(result);

求1一直加到100之间和？
 function sum(n){
        if(n ==1){//调用边界
            return 1;
        }
        return n+sum(n-1) //在return后再执行方法本身
    }
   var result = sum(100);
    console.log(result);
   /*100+sum(99)
   100+99+sum(98)
    100+99+98+sum(97)
              //....
    100+99+98+...+1*/

   //求1到10之间奇数之和  1,3,5,7
    function fn(n){
        if(n==1){
            return 1;
        }
        if(n%2==0){
            return fn(n-1)
        }else{
            return n+fn(n-2)  //不断调用fn的逻辑，这时可以在return 后面返回函数执行，再次调用方法本身
        }
    }

面试题：1~100之间，把所有能被3并且能被5整除的获取到，然后累加求和

//=> 方案一:
var total = null;
for (var i = 0; i <= 100; i++) {
    if (i % 3 == 0 && i % 5 == 0) {
       total += i;
    }
}
console.log(total); //315

//=>方案二:
function fn(num) {
    if (num > 100) {
        return 0
    }
    if (num % 15 == 0) {
        return num + fn(num + 1);
    }
    return fn(num + 1)
}
var res = fn(1);
console.log(res);

快速排序

原理：先找中间项，把剩余项中的每一个值和中间项进行比较，比他小的放在左边（新数组），比他大的放在右边（新数组）；

function quick(ary) {
    //->如果传递进来的数组只有一项或者是空的,我们则不再继续取中间项拆分
    if (ary.length <= 1) {
        return ary;
    }

    //->获取中间项的索引：把中间项的值获取到，在原有数组中删除中间项
    var centerIndex = Math.floor(ary.length / 2),
        centerValue = ary.splice(centerIndex, 1)[0];//->splice返回的是个数组,数组中包含了删除的那个内容值，把内容值获取到;

    //->用剩余数组中的每一项和中间项进行比较，比中间项大的放在右边，比他小的放在左边（左右两边都是新数组）
    var aryLeft = [],
        aryRight = [];
    for (var i = 0; i < ary.length; i++) {
        var cur = ary[i];
        cur < centerValue ? aryLeft.push(cur) : aryRight.push(cur);
    }
    return quick(aryLeft).concat(centerValue, quick(aryRight));
}
console.log(quick([12, 15, 14, 13, 16, 11]));


  var ary = [3,65,7,12,56];
  
  function quickSort(ary) {
       if(ary.length<=1){
           return ary;
       }
        var pointIndex=Math.floor(ary.length/2);
       var pointValue=ary.splice(pointIndex,1)[0];
       var left=[];
       var right=[];
       for (var i = 0;i<ary.length;i++) {
           var cur= ary[i];
           if(cur<=pointValue){
               left.push(cur)
           }else {
               right.push(cur)
           }
       }
return quickSort(left).concat(pointValue,quickSort(right));
   }

    console.log(quickSort(ary));

插入排序

//倒序
function insert(ary) {
    //->先抓一张牌(一般都抓第一张)
    var handAry = [];//->存储的是手里已经抓取的牌
    handAry.push(ary[0]);

    //->依次循环抓取后面的牌
    for (var i = 1; i < ary.length; i++) {
        var item = ary[i];//->本次新抓的这张牌

        //->拿新抓的牌和手里现有的牌比较
        for (var j = handAry.length - 1; j >= 0; j--) {
            //handAry[j]:当前比较的手里的这张牌
            //->新抓的牌比当前比较的这张牌大了,我们把新抓的牌放在它的后面
            if (item > handAry[j]) {
                handAry.splice(j + 1, 0, item);
                break;
            }
            if (j === 0) {
                //->新抓的牌是最小的,我们把新抓的牌放在最开始的位置
                handAry.unshift(item);
            }
        }
    }
    return handAry;
}
console.log(insert([1, 2, 3, 2, 1, 2, 3, 4, 5, 23, 34, 4]));

//从左到右插入排序
<script>
    //left 从小到大排列
    var ary = [5, 8, 10, 35, 3, 9],
        left = ary.splice(0, 1);//删除的这一项放入一个新数组里返回[5]
    for (var i = 0; i < ary.length; i++) {//依次把原有数组中的内容拿出来
        var curR = ary[i];
        for (var j = 0; j < left.length;) {//顺着和左手的牌依次进行比较
            if (curR <= left[j]) {
                left.splice(j, 0, curR);
                break;
            } else {
                j++;
                if (j == left.length) {
                    left.push(curR);
                    break;
                }
            }
        }
    }
    console.log(left);
</script>

9*9乘法表

<style>
ul li{
    list-style: none;
}
ul li span{
    display: inline-block;
    width: 100px;
    height: 40px;
    line-height: 40px;
    border:1px solid #333;
    text-align: center;}
    </style>
</head>
<body>
<ul id="list"></ul>
<script type="text/javascript">
var oUl=document.getElementById("list");
var str="";
for (var i = 1; i<=9; i++) {
str +="<li>";
    for (var j = 1; j <=i; j++) {
str+=j+"*"+i+"="+j*i+"&nbsp;";

    }
    str+="</li>"
}
oUl.innerHTML=str;
</script>