前端常用的查找和排序算法等必会知识点

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;
}
复制代码

冒泡排序

• 先找出最大的，再找出最小的
• 性能最差
• 排序次数： arr.length的等差数列求和次 -> n**n/2 -n/2 次

function bubble_sort(arr) {
    //值交换函数
    function swap(arr, x, j) {
        var temp = arr[x];
        arr[x] = arr[j];
        arr[j] = temp;
    }
    
    //先找出最大的，再找出最小的
    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);
复制代码

深度克隆

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;
}
复制代码

合并排序

//将数组分成两个数组， 
// 索引 [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);
}

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