前端简单算法

冒泡排序

1. 从第一个元素开始，比较每两个相邻元素，如果前者大，就交换位置
2. 每次遍历结束，能够找到该次遍历过的元素中的最大值
3. 如果还有没排序过的元素，继续1

 var a =[48,95,23,16,1];
        // 轮数
        for(var i=0;i<a.length-1;i++){
            // 次数
            for(var j=0;j<a.length-1-i;j++)
                // 判断前一个数大于后一个数时进行交换
                if (a[j]>a[j+1]) {
                    // 借助第三方变量交换两个变量的值
                    var b = a[j];
                    a[j] = a[j+1];
                    a[j+1] = b;
                }
        }
        console.log(a)

image.png

https://user-gold-cdn.xitu.io/2019/3/29/169c901fbe75639b?imageslim

    var ary = [789,6,7,5,9,3,90,456,999];
             // 循环的趟数要比总个数少一        // 总次数少一次
         for (var i = 0; i<ary.length-1;i++) {
           // 每趟的次数  每循环一次减少一次 // 使用循环执行要比较的趟数(要比总数少一次)
            for (var j =0;j<ary.length-1-i;j++) {
               // 交换位置   索引的下一个值
               // 如果当前的值小于下一个值就交换位置
               if (ary[j] < ary[j+1]) {
                   // 第三方变量
                   // ary[j]赋值给d 依次类推 js基础变量中的交换两个值
                  var d = ary[j];

                  ary[j] = ary[j+1];

                  ary[j+1] = d;
               }
            }
         }
         console.log(ary);

斐波那契数列

从数列中可以发现从第三个数开始的值是前两个值的和。
0, 1, 1, 2, 3, 5, 8, 13, 21, 24, 55, ...
从数列中可以发现从第三个数开始的值是前两个值的和。

递归解法

function fib(n){
    if(n < 2){
        return n;
    }else{
        return fib(n - 1) + fib(n - 2);
    }
}
console.log(fib(10));   // 55

动态规划解法

function fibDyn(n){
    var temp = [];
    for(var i = 0; i <= n; i++){
        temp[i] = 0
    }
    if(n == 1 || n == 2){
        return 1;
    }else{
        temp[1] = 1;
        temp[2] = 2; 
        for(var i = 3; i < n; i++){
            temp[i] = temp[i - 1] + temp[i -2];
        }
        return temp[i - 1];
    }
}
fibDyn(10)  // 55

优化斐波那契数列的动态规划算法

function fibDyn(n){
    var prev = 1;
    var middle = 1;
    var result = 1;

    for(var i = 2; i < n; i++){
        result = prev + middle;
        prev = middle;
        middle = result;
    }
    return result;
}
fibDyn(10)  // 55