前端算法小白日刷三题13

今天主要学归并排序、快速排序和二分查找

归并排序

//归并排序
function mergeSort(arr) {
    if (arr.length < 2) return arr;
    let mid = Math.floor(arr.length / 2)
        // let left = arr.slice(0, mid)
        // let right = arr.slice(mid)

    function merge(left, right) {
        let result = []
        console.log(left, right)
        while (left.length && right.length) {
            result.push(left[0] < right[0] ? left.shift() : right.shift())
        }
        return result.concat(left, right)
    }
    return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

console.log(mergeSort([3, 1, 4, 1, 5, 9, 2, 6]));

快速排序 

//快速排序
function quickSort(arr) {
    if (arr.length <= 1) return arr
    let mid = Math.floor(arr.length / 2)
    let pivot = arr.splice(mid, 1)[0]
    let left = []
    let right = []
    for (let i = 0; i < arr.length; i++) {
        arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i])
    }
    return quickSort(left).concat(pivot, quickSort(right))
}

console.log(quickSort([3, 4, 2, 1, 5]));

二分查找

//二分查找

function binarySearch(arr, target) {
    let start = 0
    let end = arr.length - 1
    while (start <= end) {
        let mid = Math.floor((start + end) / 2)
        if (arr[mid] == target) {
            return mid
        }
        if (arr[mid] > target) {
            end = mid
        }
        if (arr[mid] < target) {
            start = mid + 1
        }
    }
    return -1
}

console.log(binarySearch([1, 2, 3, 4, 5], 3));

今天的内容就到这里啦，明天继续