5.算法&设计模式

原文链接：https://github.com/helloyoucan/knowledge

算法

1、冒泡排序

比较两个相近的项，如果前一个大于后一个则交换位置。

时间复杂度O(n²)

function bubbleSort(arr){
    const _arr = [...arr]; //copy array
    const length = _arr.length;
    for(let i = 0; i<length; i++){
        for(let j = 0; j<length; j++){
            if(_arr[j] > _arr[j+1]){//从小到大排序
                const temp = _arr[j]
                _arr[j] = _arr[j+1]
                _arr[j+1] = temp
                // [_arr[j+1],_arr[j]] = [_arr[j],_arr[j+1]]; //es6解构的写法
            }
        }
    }
}
改进后的冒泡排序

每次最大值放到最右后，会将本轮最后一个操作的位置作为下一轮的终点，可以减少不必要的一些冒泡

function buddleSort (arr) {
   let i = arr.length - 1
   while(i>0){
        let pos =0;
        for (let j=0;j<i; j++) {
            if(arr[j] > arr[j+1]){
                pos = j;
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
            }
        }
        i = pos;
   }
   return arr
}

2、快速排序

选择一个元素为基准，把小于等于基准的放到一个数组1，大于基准的放另外一个数组2，递归调用，直到数组被分割成只有一个元素，结束递归。连接按基准划分的数组。

时间复杂度O(n²)

function quickSort(arr){
    //如果数组<=1,则直接返回
    if(arr.length<=1){return arr;} //递归结束条件
    const _arr = [...arr];
    const pivotIndex = Math.floor(_arr.length/2); //取中间的索引，不是整数则舍去小数
    const pivot = _arr.splice(pivotIndex,1)[0]; //找到基准并从源数组中移除
    const left_arr = [];
    const right_arr = [];
    // 遍历，把比基准小的放在left_arr，比基准大的放在right_arr
    for(let i = 0; i<_arr.length; i++){
        if(_arr[i] <= pivot){
            left_arr.push(_arr[i]);
        }else{
            right_arr.push(_arr[i]);
        }
    }
    // 递归调用,并连接数组
    return [...quickSort(left_arr), pivot, ...quickSort(right_arr)];
}

3、选择排序

找到最小的元素放在第一位，第二小的放在第二位，如此类推。

时间复杂度O(n²)

function selectionSort(arr){
    const _arr = [...arr];
    const length =  _arr.length;
    let minIndex = 0;
    for(let i = 0; i<length -1; i++){
        for(let j = i+1; j<length; j++){
            if(_arr[j] < _arr[minIndex]){ // 寻找最小的数
                minIndex = j; // 保存最小数的索引
            }
        }
        [_arr[i], _arr[minIndex]] = [_arr[minIndex],_arr[i]]; //交换位置
    }
    return _arr
}

4、插入排序

  1. 从第一个元素开始，该元素可以被认为已经被排序
  2. 取出下一个元素，在已经排好序的序列中从后往前扫描
  3. 直到找到小于或者等于该元素的位置
  4. 将该位置后面的所有已排序的元素从后往前依次移一位
  5. 将该元素插入到该位置
  6. 重复步骤2~5

时间复杂度O(n²)

function insertionSort(arr){
    const _arr = [...arr];
    let j;
    for(let i = 1; i<_arr.length; i++){
        j = i - 1;
        const temp = _arr[i] //为该元素找到合适的位置插入
        while(j >= 0 && _arr[j] > temp){
            _arr[j+1] = _arr[j]
            j--;
        }
        _arr[j+1] = temp; //j+1最后为元素适合的位置
    }
    return _arr
}

5、归并排序

归并排序是一种分治算法。本质上就是把一个原始数组切分成较小的数组，直到每个小数组只有一个位置，接着把小数组归并成较大的数组，在归并过程中也会完成排序，直到最后只有一个排序完毕的大数组。

时间复杂度O(nlog^n)

// 分割数组，直到每个数组的元素只有一个
function mergeSort(arr){//采用自上而下的递归方法
    const _arr = [...arr];
    let length = _arr.length;
    if(length<2){
        return arr;
    }
    let middle = Math.floor(length/2);
    let left_arr = _arr.slice(0,middle);
    let right_arr = _arr.slice(middle);
    return merge(mergeSort(left_arr),mergeSort(right_arr));
}
// 从数组中挑选小的元素插入到result[],实现排序（实际上是一个个挑选进行排序）
function merge(left,right){
    let left_arr = [...left];
    let right_arr = [...right];
    let result = [];
    while(left_arr.length && right_arr.length){
        if(left_arr[0]<=right_arr[0]){//对比挑选小的元素进入result[]
            result.push(left_arr.shift());
        }else{
            result.push(right_arr.shift());
        }
    }
    result.push(...left_arr);
    result.push(...right_arr);
    return result;
}

6、堆排序

堆排序：堆排序把数组当中二叉树来排序而得名。

1）索引0是树的根节点；

2）除根节点为，任意节点N的父节点是N/2；

3）节点L的左子节点是2L；

4）节点R的右子节点为2R + 1。

本质上就是先构建二叉树，然后把根节点与最后一个进行交换，然后对剩下对元素进行二叉树构建，进行交换，直到剩下最后一个。

function heapSort(arr){
    let _arr = [...arr];
    // 初始化大顶堆（所有父节点都是与子节点比较中最大的节点），从第一个非叶子节点开始
    for(let i = Math.floor(_arr.length/2 - 1); i>= 0; i--){
        _arr = shiftDown(_arr,i,_arr.length);
    }
    // 排序，每一次for循环找出一个最大值，数组长度减一，然后继续找第二个最大的，如此类推
    for(let i = Math.floor(_arr.length - 1); i>0; i--){
        [_arr[0], _arr[i]] = [_arr[i], _arr[0]]; //根节点与最后一个节点交换
        /*
         从根节点开始调整，并且最后一个节点已经为当前最大值，
         不需要再参与比较，所以第三个参数为i，即比较到最后一个节点的前一个即可
        */
        _arr = shiftDown(_arr,0,i);
    }
    return _arr;
}
/*
将i节点以下的堆整理为大顶堆，
主要这一步实现的基础上是：假设节点i以后的子对已经是一个大顶堆
该函数的实际功能是:
找到节点i的堆中的正确位置。
后面将写一个for循环,从第一个非叶子节点开始，
对每一个非叶子节点都执行shiftDown操作，
所以就满足了节点i以下的子堆已经是一大堆顶
*/
//每次对比三个节点，将最大的节点换到父节点的位置
function shiftDown(arr,i,length){
    const _arr = [...arr];
    let temp = _arr[i] // 当前父节点
    // j<length 的目的是对节点i以下的节点全部按顺序调整
    for(let j = 2*i+1; j<length; j = 2*j+1){
        temp = _arr[i]; //将arr[i]取出，整个过程相当于找到arr[i]应处的位置
        if(j+1<length && _arr[j] < _arr[j+1]){
            j++; //找到两个孩子中较大的一个，再与父节点比较
        }
        if(temp < _arr[j]){ //如果父节点小于子节点：
            [_arr[i], _arr[j]] = [_arr[j], _arr[i]]; //交换
            i = j; //交换后，temp的下标变为j
        }else{//否则，退出
            break;
        }
    }
    return _arr;
}

7、希尔排序

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

简单插入排序的改进版，它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

O(nlog n)

function shellSort(arr){
    const _arr = [...arr];
    const length = _arr.length;
    let temp = 0;
    let gap = 1;
    while(gap < length / 5){ //动态定以间隔序列
        gap = gap*5+1;
    }
    while(gap > 0){
        for(let i = gap; i< length; i++){
            temp = _arr[i];
            let j = 0;
            for(j = i - gap; j >= 0 && _arr[j] > temp; j-=gap){
                _arr[j+gap] = _arr[j];
            }
            _arr[j+gap] = temp;
        }
        gap = Math.floor(gap / 5);
    }
    return _arr;
}

8、二分查找

（1）首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。

（2）如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。

（3）如果某一步数组为空，则表示找不到目标元素。

非递归算法

function  binarySearch(arr , key){
    let low = 0;
    let high = arr.length - 1;
    while(low <= high){
        let mid = parseInt((high + low) / 2);
        if(key === arr[mid]){
            return mid;
        }else if(key > arr[mid]){
            low = mid + 1;
        }else if(key < arr[mid]){
            high = mid - 1;
        }
    }
    return - 1;
}

递归算法

function  binarySearch(arr , key, low, high){
    low = low||0;
    high =high||arr.length - 1;
    if(low > high){
        return -1
    }
    let mid = parseInt((low + high ) /2);
    if(key ===arr[mid]){
        return mid
    }else if(key> arr[mid]){
        low  = mid + 1;
        return binarySearch(arr,key,low,high);
    }else if(key < arr[mid]){
        high  = mid - 1;
        return binarySearch(arr,key,low,high);
    }
}
9、深度优先遍历（DFS）

DFS就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。

10、广度优先遍历（BFS）

BFS从一个节点开始，尝试访问尽可能靠近它的目标节点。本质上这种遍历在图上是逐层移动的，首先检查最靠近第一个节点的层，再逐渐向下移动到离起始节点最远的层。

设计模式

1. 单例模式
function Singleton(){}
function getInstance(){
    var instance = null;
    return function(){
        if(!instance){
            instance = new Singleton()
        }
        return instance
    }
}
2. 简单工厂模式
function CarFactory(color,price){
    var car = new Object();
    car.color = color;
    car.price = price;
    car.getPrice = function(){ return this.price; } 
    return car
}
var car1 = CarFactory('red',5000);
var car2 = CarFactory('white',7000);
3. 模块模式
var singleMode = (function(){
    // 创建有变量
    var privateNum = 122
    // 创建私有方法
    function privateFunc(){}
    //创建公有方法
    function publicMethod1(){}
    function publicMethod2(){}
    // 返回一个对象包含公有方法和属性
    return {
        publicMethod1:publicMethod1,
        publicMethod2:publicMethod2
    }
})();
4.观察者模式 & 发布-订阅模式

观察者模式 在软件设计中是一个对象，维护一个依赖列表，当任何状态发生改变自动通知它们。

const subject = {
    observers: [],// 观察者
    notify() { // 通知
        this.observers.forEach(observer =>{
            observer.update()
        })
    },
    attach (observer) { //添加观察者
        this.observers.push(observer)
    }
}
const observer = {
    update(){
        // 观察的人提供的通知调用的函数
        console.log('updated')
    }
}
subject.attach(observer) // 加入观察
subject.notify()// 通知

发布-订阅模式，消息的发送方，叫做发布者（publishers），消息不会直接发送给特定的接收者，叫做订阅者。

const Event = (()=>{
    const list = {};
    let listen, trigger, remove;
    listen = function(key,fn){
        if(!list[key]){
            // 未订阅此类消息，则给该类消息创建一个缓存列表
            list[key] = [];
        }
        // 订阅消息添加到缓存列表
        list[key].push(fn);
    };
    trigger = function(key,...params){
        // 取出改消息对应的回调函数的集合
        var fns = list[key];
        // 如果没有订阅过该消息，则返回
        if(!fns||fns.length === 0){
            return false
        }
        for(let i = 0,l=fns.length; i<l; i++){
            fns[i].apply(this, params);//params是发布消息的传递的参数
        }
    };
    remove = function(key, fn){
        // 如果key对应的消息没有订阅过的话，则返回
         var fns = list[key];
        if(!fns) {
            return false;
        }
        // 如果没有传入具体的回调函数，表示需要取消key对应消息的所有订阅
        if(!fn) {
            fns && (fns.length = 0);
        }else {
            for(var i = 0, l = fns.length; i < l; i++){
                var _fn = fns[i];
                if(_fn === fn) {
                    fns.splice(i,1);// 删除订阅者的回调函数
                }
            }
        }
    }
    return {
        listen: listen,
        trigger: trigger,
        remove: remove
    }
})();
// 测试代码如下：
Event.listen("eventName",function(param) {
    console.log("params:"+param); // 打印出尺码为42
});
Event.trigger("eventName",'555');
5. 责任链模式
function order500(orderType,isPay,count){
    if(orderType == 1 && isPay == true)    {
        console.log("亲爱的用户，您中奖了100元红包了");
    }else {
        //我不知道下一个节点是谁,反正把请求往后面传递
        return "nextSuccessor";
    }
};
function order200(orderType,isPay,count) {
    if(orderType == 2 && isPay == true) {
        console.log("亲爱的用户，您中奖了20元红包了");
    }else {
        //我不知道下一个节点是谁,反正把请求往后面传递
        return "nextSuccessor";
    }
};
function orderNormal(orderType,isPay,count){
    // 普通用户来处理中奖信息
    if(count > 0) {
        console.log("亲爱的用户，您已抽到10元优惠卷");
    }else {
        console.log("亲爱的用户，请再接再厉哦");
    }
}
// 下面需要编写职责链模式的封装构造函数方法
var Chain = function(fn){
    this.fn = fn;
    this.nextSuccessor = null;
}
Chain.prototype.setNextSuccessor = function(successor){
    return this.successor = successor
}
// 把请求往下传递
Chain.prototype.passRequest = function(){
    var ret = this.fn.apply(this,arguments);
    if(ret === 'nextSuccessor'){
        // 调用后面的节点
        return this.successor && this.successor.passRequest.apply(this.successor, arguments);
    }
    return ret;
}


//现在我们把3个函数分别包装成职责链节点：
var chainOrder500 = new Chain(order500);
var chainOrder200 = new Chain(order200);
var chainOrderNormal = new Chain(orderNormal);

// 然后指定节点在职责链中的顺序
chainOrder500.setNextSuccessor(chainOrder200);
chainOrder200.setNextSuccessor(chainOrderNormal);

//最后把请求传递给第一个节点：
chainOrder500.passRequest(1,true,500);  // 亲爱的用户，您中奖了100元红包了
chainOrder500.passRequest(2,true,500);  // 亲爱的用户，您中奖了20元红包了
chainOrder500.passRequest(3,true,500);  // 亲爱的用户，您已抽到10元优惠卷 
chainOrder500.passRequest(1,false,0);   // 亲爱的用户，请再接再厉哦
6. 策略模式
// 策略类
var obj = {
        "A": function(salary) { return salary * 4; },
        "B" : function(salary) { return salary * 3; },
        "C" : function(salary) { return salary * 2; } 
};
//环境类
var calculateBouns =function(level,salary) {
    return obj[level](salary);
};
// 调用
console.log(calculateBouns('A',10000)); // 40000
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,937评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,503评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,712评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,668评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,677评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,601评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,975评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,637评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,881评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,387评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,971评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2赞 342

推荐阅读更多精彩内容

  • 排序算法汇总
    简单来说，时间复杂度指的是语句执行次数，空间复杂度指的是算法所占的存储空间 时间复杂度计算时间复杂度的方法： 用常...
    Teci阅读 1,080评论 0赞 1
  • 常规排序算法总结
    概述 因为健忘，加上对各种排序算法理解不深刻，过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总...
    清风之心阅读 685评论 0赞 1
  • （转）八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    蚁前阅读 5,164评论 0赞 52
  • 10个流行的排序算法
    稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可...
    意识流丶阅读 3,148评论 2赞 9
  • 美团前端程序员第二轮面试的10个问题，你会几个？
    近日，w3cschool app开发者头条上分享了美团前端程序员第二轮面经，引来了不少程序员粉丝们的围观。 在分享...
    编程狮W3Cschool阅读 3,629评论 0赞 3