js笔记二十二之数组排序算法-冒泡,递归,快速,插入

冒泡排序

原理: 让数组中的当前项和后一项进行比较, 如果当前项大于后一项,我们让两者交换位置(小 -> 大)

var ary = [12,13,23,14,16,11]

// 第一轮比较: 
//      12 13 [12,13,23,14,16,11]
//      13 23 [12,13,23,14,16,11]
//      23 14 [12,13,14,23,16,11]
//      23 16 [12,13,14,16,23,11]
//      23 11 [12,13,14,16,11,23]
// 第二轮比较: 
//      12 13 [12,13,14,16,11,23]
//      13 14 [12,13,14,16,11,23]
//      14 16 [12,13,14,16,11,23]
//      16 11 [12,13,14,11,16,23]
// ...

// 每一轮从前到后两两比较,虽然不一定实现最后的排序效果,但是可以把当前最大的放到末尾
// 具体比较轮数: ary.length-1; 数组有多长,我们只需把总长度-1个数分别放在末尾,即可实现最后的排序

// 第一轮比较5次: 一共6个,不需要和自己比较
// 第二轮比较4次: 一共6个,不用和自己比较,也不用和第一轮放在末尾的那个最大值比较
// 第三轮比较3次: 
// ...

// 每一轮比较的次数:
//ary.length-1(不用和自己比较) - 当前已经执行的轮数(执行一轮向末尾放一个最大值,这些值不需要再比较)

// a = 12;
// b = 13;
// a和b交换值

// 借用第三个变量先存储一个值,然后替换
// c = a;
// a = b;
// b = c;

// 不借用三个变量
// a = a+b; // -> 25
// b = a-b; // -> 12 -> b = 12;
// a = a-b; // -> 13 -> a = 13;

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

// 升序
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;
}
console.log(bubble(ary))

// 降序
function bubble(ary){
    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]) {
                var temp = ary[j];
                ary[j] = ary[j+1];
                ary[j + 1] = temp;
            }
        }
    }
    return ary;
}
console.log(bubble(ary))

递归排序

自己调用自己

// 死递归
function fn(num){
    console.log(num)
    fn()
}
fn(10)


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

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

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

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

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)

快速排序

先找中间这一项
把剩余项的每一个值和中间项进行比较,比他小的放在左边,比他大的放在右边(新数组)
...

var ary = [12,15,14,13,16,11];
function quick(ary){
    // 如果传递进来的数组只有一项或者是空的,我们则不再继续取中间项拆分
    if(ary.length <= 1){
        return ary;
    }
    // 获取中间项的索引: 把中间项的值获取到,在原有数组中删除中间项
    var centerIndex = Math.floor(ary.length/2),
        // splice返回的是个数组,数组中包含了删除的那个内容
        centerValue = ary.splice(centerIndex,1)[0];

    // 用剩余数组中的每一项和中间项比较,比中间项大的放在右边,比中奖项小的放在左边(左右两边都是新数组)
    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(ary))

插入排序

var ary = [12,15,14,13,16,11];
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(ary))