阅读 794

前端常用的查找和排序等必会手写知识

有序数组插入数字

function insertNumber(arr, x) {
    
    //查找到第一个大于x的数字
    let b = newArr.find(e => e > x);
    
    
    if (b === undefined) { 
        // 如果b不存在,证明x是最大的数字,push到数组尾部
        newArr.push(x);
        
    } else {
    
        //获取b的index,把新的数字插入到b的位置
        let bIndex = newArr.indexOf(b)
        newArr.splice(bIndex, 0, x)
    }
    
    return arr;

}

复制代码

两个有序数组合并成一个新的有序数组

  • 和插入一样, 第一个解构,对第二个数组进行遍历循环插入到第一个数组
function insert_some_numbers(arr1, arr2) {
    //创建新数组,并结构第一个数组
    var newArr = [...arr1];
    
    for (var i = 0; i < arr2.length; i++) {
        //获取第二个数组中的每一位
        x = arr2[i];
        
        //在新解构的数组中查找第一个比他大的数组
        let b = newArr.find(e => e > x);
        
        //获取到这个数字的索引并插入到他的前面
        let bindex = newArr.indexOf(b)
        newArr.splice(bindex === -1 ? newArr.length : bindex, 0, x)
    }
    return newArr;
}
let arr1 = [1, 2, 3, 4, 5, 6, 8, 9];
console.log(insert_some_numbers(arr1, [1, 2, 3]));
复制代码

二分查找

  • 最大查找次数 Math.ceil(Math.log2(arr.length))
function binarySearch(arr, x) {
    var left = 0; //左边界
    var right = arr.length - 1; //右边界
    var guess;  // 游标, 中间索引去小数点

    while (left <= right) { // 左侧边界小于右侧边界才执行
    
        guess = ((left + right) / 2) | 0;  //游标索引, 中间索引去小数点
        
        if (arr[guess] === x) return guess // 当游标索引就是查找的X的话,返回游标索引
        
        else if (arr[guess] > x) right = guess - 1 // 游标索引位 大于 x , 右边界移动到guess之前。
        
        else left = guess + 1 // 游标索引位 小于 x , 右边界移动到guess之后。
    }
    
    return -1; //未查找到
}


var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(
    binarySearch(arr, 5) 
)
复制代码

有序数组插入新数字

  • 模拟一个空位置循环比较,
  • 从数组尾部向前比较,前面的那一位比x大,比x大的那个数字索引+1,
  • 再跟前面的一位作比较,如果比X小, p+1位索引就被变量x 占了
function insert_number_3(arr, x) {
    //p是下一个待比较元素的索引
    //p-1是空位
    //p不能小于0, 当P小于0代表, x是最小的
    let p = arr.length - 1;
    while (p >= 0 && arr[p] > x) {
        arr[p + 1] = arr[p];
        p--;
    }
    arr[p + 1] = x;
}
let arr1 = [1, 2, 3, 4, 5, 6, 8, 9];
insert_number_3(arr1, 6)
console.log(arr1)
复制代码

插入排序

  • 性能最差
  • n^2/2 - n/2 次比较
  • 从数组的第1索引位置,逐次向前比较
  • 比较次数 1 + 2 + 3 + ··· + arr.length 次
function insertion_sort(arr) {
    //第一位不用去作比较,只有一位的数组可以看作为有序数组
    for (var i = 1; i < arr.length; i++) {
        insert(arr, i, arr[i]);
    }
}

function insert(arr, i, x) {
    let p = i - 1; // p 作为被首先比较的元素
    // arr[i] 也就是 x  是待插入的元素
    while (p >= 0 && arr[p] > x) {
        // 当待插入的元素
        arr[p + 1] = arr[p];
        p--;
    }
    arr[p + 1] = x;
}
复制代码

选择排序

// 找到第一个最小的,放在第一位
// 再找到第二个最小的, 放在第二位
function select(array) {

    var len = array.length;
    
    //第零位到倒数第二位
    for (var i = 0; i < len - 1; i++) { 
        
        //先认定数组中的第i位是最小的, 再逐次跟后面的作比较
        var minnum = array[i];
        
        //第一位到最后一位
        for (var j = i + 1; j < len; j++) { 
            
            // 如果后面的更小的话, 做值的交换
            if (array[j] < minnum) {
                //值交换
                [array[j], minnum] = [minnum, array[j]]
            }
        }
        //比较过后, 给第i位赋值
        array[i] = minnum;
    }
}

var arr = [4, 5, 8, 9, 4, 2, 15, 6]
select(arr)
console.log(arr)
复制代码

冒泡排序

  • 先找出最大的,再找出最小的
  • 性能最差
  • 排序次数: arr.length的等差数列求和次 -> n**n/2 -n/2 次
function bubble_sort(arr) {
    //值交换函数
    function swap(arr, x, j) {
        [arr[x],arr[j]] = [arr[j], arr[i]]
    }
    
    //先找出最大的,再找出最小的
    for (let i = arr.length - 1; i >= 1; i--) {
        //从1开始,每一次都和前一位作比较。
        for (let j = 1; j <= i; j++) {
            arr[j] < arr[j - 1] && swap(arr, j-1, j)
        }
    }
}

const arr2 = [91, 60, 96, 9, 30, 20, 31, 77, 81, 24];
bubble_sort(arr2)
console.log(arr2);
复制代码

合并排序

//将数组分成两个数组, 
// 索引 [a,b) 和 [b,c)

//合并函数部分,
function merge(arr, a, b, c) {
    // 此时arr1 和 arr2 是 两个有序数组
    let arr1 = arr.slice(a, b);
    let arr2 = arr.slice(b, c);

    //在两个数组后面布置哨兵
    arr1.push(Infinity);
    arr2.push(Infinity);
    //设置两个数组的比较位置的索引的游标索引
    // 如果这个数字被赋值,则索引+1
    var i = 0, j = 0;
    //循环给arr赋值
    for (let k = a; k < c; k++) {
        //k : 下一个写入位置
        //i : arr1中的回写位置
        //j :  arr2中的回写位置
        arr[k] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
    }
}

function mergeSort(arr, a, c) {
    //判断数组长度是否为1
    if (c - a < 2) { return };
    const b = Math.ceil((a + c) / 2);
    //左侧部分递归
    mergeSort(arr, a, b);
    //右侧部分递归
    mergeSort(arr, b, c);
    //执行拼接
    merge(arr, a, b, c);
}

// 把数组拆成一个,一个的数组, 在执行拼接
复制代码

双路快速

function quickSort(arr) {
    //递归出口,数组长度为0
    if (arr.length == 0) return [];
    // 建立比较数字, 左侧数组, 右侧数组
    var left = [];
    var right = [];
    var pivot = arr[0];
    //从数组第一位开始比较
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    // 递归 连接数组, 这个函数是纯函数,结果不会改变原数组。
    return quickSort(left).concat(pivot, quickSort(right))
}
let arr = [4, 51, 59, 13, 1, 31, 3, 1, 8];
let result = quickSort(arr);
console.log(result)
复制代码

三路快排

function qSort3(arr) {
    if (arr.length == 0) {
        return [];
    }
    //定义三个数组
    var left = [];
    //三路快排的核心是多了一个中间数组, 中间数组放相等的值,避免了不必要的比较
    var center = []; 
    var right = [];

    //设置一个比较值
    var pivot = arr[0];

    //循环比较部分
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else if (arr[i] == pivot) {
            center.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    //循环递归 大于比较值的部分和小于比较值的部分
    return [...qSort3(left), ...center, ...qSort3(right)];
}
var newArr = qSort3([9, 4, 10, 8, 12, 2, 6, 7, 3, 1, 1, 0, 9, 1, 0])
console.log(newArr)
复制代码

深度克隆

function deepClone2(origin, target) {
    var target = target || ((origin instanceof Array) ? [] : {});

    for (var prop in origin) {
        if (origin.hasOwnProperty(prop)) {
            if (typeof origin[prop] == 'object') {
                if (Object.prototype.toString.call(origin[prop]) === '[object Array]') {
                    target[prop] = [];
                } else {
                    target[prop] = {};
                }
                deepClone2(origin[prop], target[prop]);
            } else {
                target[prop] = origin[prop]
            }
        }
    }
    return target;
}
复制代码

数组扁平化

function platArray(arr) {
    var newArr = [];
    function pushToArray(arr) {
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] instanceof Array) {
                pushToArray(arr[i])
            } else {
                newArr.push(arr[i])
            }
        }
    }
    pushToArray(arr)
    return newArr;
}
console.log(platArray([[1, 2], [[[[3]]]], [{ name: "lyz", info: { age: "24" } }], [4, [5, [6]]]]));
// [1, 2, 3, { name: 'lyz', info: { age: '24' } }, 4, 5, 6]
复制代码

字符串反转

var str = 'abcde';

function strReverse(str) {
    // new String 出来的类数组是不能修改某一位的,
    // writeable是false;
    var strObj = [...new String(str)];
    var times = strObj.length / 2 | 0;
    for (var i = 0; i < times; i++) {
        var y = strObj.length - 1 - i;
        [strObj[i], strObj[y]] = [strObj[y], strObj[i]];

    }
    return strObj.join('');
}

console.log(strReverse(str));
复制代码

观察 者模式

 //es6
 
        class Event {
            constructor() {
                this.cache = {};
            }

            on(type, handle) {
                if (!this.cache[type]) {
                    this.cache[type] = [handle];
                } else {
                    this.cache[type].push(handle)
                }
            }

            // 执行某一个type下面的全部函数
            emmit() {
                // argiments 第一位是type类型, 其余几位是函数用的参数
                //获取type
                var type = arguments[0];
                // 获取参数, 
                var arg = [].slice.call(arguments, 1);
                // 依次执行数组里面的函数
                for (var i = 0; i < this.cache[type].length; i++) {
                    this.cache[type][i].apply(this, arg)
                }
            }

            //清空某一个type数组
            empty(type) {
                this.cache[type] = [];
            }

            // 清空指定的type数组里面的指定的hanle
            remove(type, handle) {
                var infos = this.cache[type];
                if (!infos) return false;
                if (!handle) {
                    infos && (infos.length = 0);
                } else {
                    for (var i = 0, len = infos.length; i < len; i++) {
                        if (infos[i] === handle) {
                            infos.splice(i, 1);
                        }
                    }
                }
            }
        }
复制代码

简易版的Promise (还不支持Promise内部的异步触发)

//executor 函数是同步执行的函数 ,包含有两个参数 resolve reject
// promise对象有三种状态 pending, fulfilled 和 rejected

function myPromise(executor) {
    //在 es5中函数中执行函数的this指向问题
    var _this = this;

    // 设置初始状态和resolve和reject函数初始参数
    _this.status = "pending";
    _this.resolveValue = null;
    _this.rejectValue = null;

    function resolve(value) {
        if (_this.status === 'pending') {
            _this.status = "fulfilled";
            _this.resolveValue = value;
        }
    }
    
    function reject(reason) {
        if (_this.status === 'pending') {
            _this.status = "rejected";
            _this.rejectValue = reason;
        }
    }
    
    //使用try catch来处理Promise中抛出异常的情况
    try {
        executor(resolve, reject)
    } catch (e) {
        //如果抛出异常 , 执行reject就可以了
        reject(e)
    }

}

//Promise原型链上的方法then的实现

myPromise.prototype.then = function (onFulfilled, onRejected) {
    var _this = this;
    
    if (_this.status === "fulfilled") {
        onFulfilled(_this.resolveValue)
    }
    if (_this.status === "rejected") {
        onRejected(_this.rejectValue)
    }
}
复制代码

支持异步的简易版Promise (不支持链式操作)

//executor 函数是同步执行的函数 ,包含有两个参数 resolve reject
// promise对象有三种状态
// pending, fulfilled 和 rejected

function myPromise(executor) {
    //在 es5中函数中执行函数的this指向问题
    var _this = this;

    // 设置初始状态和resolve和reject函数初始参数
    _this.status = "pending";
    _this.resolveValue = null;
    _this.rejectValue = null;

    //执行数组, 里面存入函数
    _this.ResolveCallbackList = [];
    _this.RejectCallbackList = [];

    function resolve(value) {
        if (_this.status === 'pending') {
            _this.status = "fulfilled";
            _this.resolveValue = value;
            //执行的时候已经可以是异步了, 如果是异步的时候, 
            //数组里面有函数,不然没有函数
            _this.ResolveCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    function reject(reason) {
        if (_this.status === 'pending') {
            _this.status = "rejected";
            _this.rejectValue = reason;
            //执行的时候已经可以是异步了, 如果是异步的时候, 
            //数组里面有函数,不然没有函数
            _this.RejectCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    //使用try catch来处理Promise中抛出异常的情况
    try {
        executor(resolve, reject)
    } catch (e) {
        //如果抛出异常 , 执行reject就可以了
        reject(e)
    }

}

//Promise原型链上的方法then的实现

myPromise.prototype.then = function (onFulfilled, onRejected) {
    var _this = this;
    if (_this.status === "fulfilled") {
        onFulfilled(_this.resolveValue)
    }
    if (_this.status === "rejected") {
        onRejected(_this.rejectValue)
    }
    
    //增加pending状态的判断, 如果是pending, 存入到相应的执行事件的数组当中。
    if (_this.status === "pending") {
        onFulfilled && _this.ResolveCallbackList.push(function () {
            onFulfilled(_this.resolveValue);
        });
        onRejected && _this.RejectCallbackList.push(function () {
            onRejected(_this.rejectValue);
        })
    }
}
复制代码

简易版Promise支持链式调用(then目前还是同步的)

function myPromise(executor) {
    //在 es5中函数中执行函数的this指向问题
    var _this = this;

    // 设置初始状态和resolve和reject函数初始参数
    _this.status = "pending";
    _this.resolveValue = null;
    _this.rejectValue = null;

    //执行数组, 里面存入函数
    _this.ResolveCallbackList = [];
    _this.RejectCallbackList = [];

    function resolve(value) {
        if (_this.status === 'pending') {
            _this.status = "fulfilled";
            _this.resolveValue = value;
            _this.ResolveCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    function reject(reason) {
        if (_this.status === 'pending') {
            _this.status = "rejected";
            _this.rejectValue = reason;
            _this.RejectCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    //使用try catch来处理Promise中抛出异常的情况
    try {
        executor(resolve, reject)
    } catch (e) {
        //如果抛出异常 , 执行reject就可以了
        reject(e)
    }

}

//Promise原型链上的方法then的实现
//链式调用的核心:
//.then 执行后会返回一个 >>>新的Promise对象<<< 注意是新的

myPromise.prototype.then = function (onFulfilled, onRejected) {
    var _this = this;

    var nextPromise = new myPromise(function (resolve, reject) {
        if (_this.status === "fulfilled") {
            var nextResolveValue = onFulfilled(_this.resolveValue);
            //获取then里面的第一个函数的返回值,给下一个then的promise传参
            //当 前一个Promise的同步触发, 直接就执行下一个promise的resolve函数
            resolve(nextResolveValue);
        }
        if (_this.status === "rejected") {
            var nextRejectValue = onRejected(_this.rejectValue);
            //  这个也必须要是resolve的函数, 
            resolve(nextRejectValue);
        }

        if (_this.status === "pending") {
            onFulfilled && _this.ResolveCallbackList.push(function () {
                var nextResolveValue = onFulfilled(_this.resolveValue);
                //前一个Promise的异步触发, 直接就执行下一个promise的resolve函数
                resolve(nextResolveValue);
            });
            onRejected && _this.RejectCallbackList.push(function () {
                var nextRejectValue = onRejected(_this.rejectValue);
                //  这个也必须要是resolve的函数
                resolve(nextRejectValue);
            })
        }
    });
    return nextPromise;
}
复制代码

Promise实现空then()传递, .then()异步执行 .then()的抛错处理

function myPromise(executor) {
    //在 es5中函数中执行函数的this指向问题
    var _this = this;

    // 设置初始状态和resolve和reject函数初始参数
    _this.status = "pending";
    _this.resolveValue = null;
    _this.rejectValue = null;

    //执行数组, 里面存入函数
    _this.ResolveCallbackList = [];
    _this.RejectCallbackList = [];

    function resolve(value) {
        if (_this.status === 'pending') {
            _this.status = "fulfilled";
            _this.resolveValue = value;
            _this.ResolveCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    function reject(reason) {
        if (_this.status === 'pending') {
            _this.status = "rejected";
            _this.rejectValue = reason;
            _this.RejectCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    //使用try catch来处理Promise中抛出异常的情况
    try {
        executor(resolve, reject)
    } catch (e) {
        //如果抛出异常 , 执行reject就可以了
        reject(e)
    }

}

//Promise原型链上的方法then的实现
//链式调用的核心:
//.then 执行后会返回一个 >>>新的Promise对象<<< 注意是**新的**
//
//空then原理 .then() 也就是 .then((val)=>val, err=>err)

myPromise.prototype.then = function (onFulfilled, onRejected) {
    var _this = this;

    //实现空then的数据的传递
    if (!onFulfilled) {
        onFulfilled = function (val) {
            return val;
        }
    }
    if (!onRejected) {
        onRejected = function (reason) {
            throw reason
        }
    }

    var nextPromise = new myPromise(function (resolve, reject) {
        if (_this.status === "fulfilled") {
            //使用then实现异步执行, 和抛出错误的处理
            setTimeout(function () {
                try {
                    var nextResolveValue = onFulfilled(_this.resolveValue);
                    //获取then里面的第一个函数的返回值,给下一个then的promise传参
                    //当 前一个Promise的同步触发, 直接就执行下一个promise的resolve函数
                    resolve(nextResolveValue);
                } catch (e) {
                    reject(e)
                }

            })
        }

        if (_this.status === "rejected") {
            setTimeout(function () {
                try {
                    var nextRejectValue = onRejected(_this.rejectValue);
                    //  这个也必须要是resolve的函数, 
                    resolve(nextRejectValue);
                } catch (e) {
                    reject(e)
                }
            })
        }

        if (_this.status === "pending") {
            onFulfilled && _this.ResolveCallbackList.push(function () {
                setTimeout(function () {
                    try {
                        var nextResolveValue = onFulfilled(_this.resolveValue);
                        //前一个Promise的异步触发, 直接就执行下一个promise的resolve函数
                        resolve(nextResolveValue);
                    } catch (e) {
                        reject(e)
                    }
                })
            });
            onRejected && _this.RejectCallbackList.push(function () {
                setTimeout(function () {
                    try {
                        var nextRejectValue = onRejected(_this.rejectValue);
                        //  这个也必须要是resolve的函数
                        resolve(nextRejectValue);
                    } catch (e) {
                        reject(e)
                    }
                })
            })
        }
    });
    return nextPromise;
}

复制代码

完整的Promise函数实现原理

function MyPromise(executor) {
    //在 es5中函数中执行函数的this指向问题
    var _this = this;

    // 设置初始状态和resolve和reject函数初始参数
    _this.status = "pending";
    _this.resolveValue = null;
    _this.rejectValue = null;

    //执行数组, 里面存入函数
    _this.ResolveCallbackList = [];
    _this.RejectCallbackList = [];

    function resolve(value) {
        if (_this.status === 'pending') {
            _this.status = "fulfilled";
            _this.resolveValue = value;
            _this.ResolveCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    function reject(reason) {
        if (_this.status === 'pending') {
            _this.status = "rejected";
            _this.rejectValue = reason;
            _this.RejectCallbackList.forEach(function (ele) {
                ele();
            })
        }
    }
    //使用try catch来处理Promise中抛出异常的情况
    try {
        executor(resolve, reject)
    } catch (e) {
        //如果抛出异常 , 执行reject就可以了
        reject(e)
    }

}

//Promise原型链上的方法then的实现
//链式调用的核心:
//.then 执行后会返回一个 >>>新的Promise对象<<< 注意是**新的**
//
//空then原理 .then() 也就是 .then((val)=>val, err=>err)

//这个函数用来解决then里面的函数返回一个新的new promise的
function ResolutionReturnValue(returnValue, resolve, reject) {
    if (returnValue instanceof MyPromise) {
        //如果是promise对象, 用then处理返给下一个then,
        returnValue.then(function (val) {
            resolve(val);
        }, function (reason) {
            reject(reason);
        })
    } else {
        // returnValue 是一个普通的值
        resolve(returnValue);

    }
}



MyPromise.prototype.then = function (onFulfilled, onRejected) {
    var _this = this;

    //实现空then的数据的传递
    if (!onFulfilled) {
        onFulfilled = function (val) {
            return val;
        }
    }
    if (!onRejected) {
        onRejected = function (reason) {
            throw reason
        }
    }

    var nextPromise = new MyPromise(function (resolve, reject) {
        if (_this.status === "fulfilled") {
            //使用then实现异步执行, 和抛出错误的处理
            setTimeout(function () {
                try {
                    //nextResolveValue 他有可能是一个对象new Promise(), 后续再书中进行判断
                    var nextResolveValue = onFulfilled(_this.resolveValue);
                    //因为是异步的代码, nextPromise是可以被传到函数执行中的, 因为setTimeout发身在给nextPromise的赋值之后
                    ResolutionReturnValue(nextResolveValue, resolve, reject);
                } catch (e) {
                    reject(e)
                }

            })
        }

        if (_this.status === "rejected") {
            setTimeout(function () {
                try {
                    var nextRejectValue = onRejected(_this.rejectValue);
                    //  这个也必须要是resolve的函数, 
                    ResolutionReturnValue(nextRejectValue, resolve, reject);
                } catch (e) {
                    reject(e)
                }
            })
        }

        if (_this.status === "pending") {
            onFulfilled && _this.ResolveCallbackList.push(function () {
                setTimeout(function () {
                    try {
                        var nextResolveValue = onFulfilled(_this.resolveValue);
                        //前一个Promise的异步触发, 直接就执行下一个promise的resolve函数
                        ResolutionReturnValue(nextResolveValue, resolve, reject);
                    } catch (e) {
                        reject(e)
                    }
                })
            });
            onRejected && _this.RejectCallbackList.push(function () {
                setTimeout(function () {
                    try {
                        var nextRejectValue = onRejected(_this.rejectValue);
                        //  这个也必须要是resolve的函数
                        ResolutionReturnValue(nextRejectValue, resolve, reject);
                    } catch (e) {
                        reject(e)
                    }
                })
            })
        }
    });

    return nextPromise;
}

//模块导出 前后端都可以用
try {
    module.exports = MyPromise
} catch (e) { }
复制代码

Promise.all

MyPromise.all = function(promises) {
    return new Promise(function (resolve, reject) {
        //类型判断
        if (!isArray(promises)) {
            return reject(new TypeError('arguments must be an array'));
        }
        //目前已经resolve的数量
        var resolvedCounter = 0;
        //获取参数数组长度
        var promisesNum = promises.length;
        // 全部成功是的返回值是一个数组,数组里面是每一个成功的promise的resolve的参数
        var resolvedValues = new Array(promiseNum);
        //对数组进行遍历,因为是异步,所以要防止产生闭包。
        for (var i = 0; i < promiseNum; i++) {
            (function (i) {
                Promise.resolve(promises[i]).then(function (value) {
                    resolvedCounter++
                    resolvedValues[i] = value
                    // 只有resolve的数量和promise的数量一致的时候才会触发最外层的resolve执行
                    if (resolvedCounter == promisesNum) {
                        return resolve(resolvedValues)
                    }
                }, function (reason) {
                    return reject(reason)
                })
            })(i)
        }
    })
}


复制代码

本菜鸟忘了的时候复习用的。

关注下面的标签,发现更多相似文章
评论