前端面试

快速排序

参考：https://www.cnblogs.com/du001011/p/10798540.html

快速排序最经常的思路就是利用递归，当然也可以借助数组不用递归来实现快速排序

/**
 * 非递归实现快速排序
 * @param {*} data 
 * @param {*} low 
 * @param {*} high 
 */
function quickSort(data, low, high) {
    console.log(data, low, high)
    const pivot = partition(data, low, high);
    let result = [];

    if (pivot + 1 < high) {
        result.push(pivot + 1, high);
    } else if (pivot > low + 1) {
        result.push(low, pivot - 1);
    }



    // 数组不为空
    while (result.length > 0) {
        console.log(1, result)
        const temp_high = result.pop();
        const temp_low = result.pop();
        if (temp_low >= temp_high) {
            break;
        }
        const temp_pivot = partition(data, temp_low, temp_high);

        if (temp_pivot + 1 < high) {
            result.push(temp_pivot + 1, temp_high)
        } else if (temp_pivot - 1 > low) {
            result.push(temp_low, temp_pivot - 1);
        }

    }

    return data;

}


// 严版获取快排pivot
function partition(data, low, high) {

    let pivot = data[low];

    while (low < high) {
        // 高位
        while (low < high && pivot <= data[high]) --high;
        data[low] = data[high]
        // 低位
        while (low < high && pivot >= data[low]) ++low;
        data[high] = data[low]
    }
    data[low] = pivot

    return low
}

console.log(quickSort([1, 8, 9, 2], 0, 3))

二分查找

参考：https://labuladong.gitee.io/algo/算法思维系列/二分查找详解.html

文章解释的非常清楚，二分查找分为三种情况：

• 判断是否存在某元素【目标查询】
• 查询某元素首次出现的索引位置【左侧查询】
• 查询某元素最后一次出现的位置【右侧查询】

综合代码整理如下，直接记忆：

function rightBinarySearch(data, target) {
    if (!data.length) {
        return -1
    }
    let left = 0;
    let right = data.length - 1;

    while (left <= right) {

        let mid = left + Math.floor((right - left) / 2);

        if (target === data[mid]) {
            // 别返回，锁定右侧边界
            left = mid + 1
        } else if (target < data[mid]) {
            // 左侧
            right = mid - 1
        } else if (target > data[mid]) {
            // 右侧；
            left = mid + 1;
        }
    }

    // left = right+1; 判断出界
    if (right < 0 || data[right] !== target) {
        return -1
    }
    return right
}


// [left，right]
function leftBinarySearch(data, target) {
    if (!data.length) {
        return -1
    }
    let left = 0;
    let right = data.length - 1;

    while (left <= right) {

        let mid = left + Math.floor((right - left) / 2);

        if (target === data[mid]) {
            // 左侧收缩
            right = mid - 1;
        } else if (target < data[mid]) {
            // 左侧
            right = mid - 1
        } else if (target > data[mid]) {
            // 右侧；
            left = mid + 1;
        }
    }


    // left = right+1; 左侧判断出界
    if (left > data.length || data[left] !== target) {
        return -1
    }


    return left
}

上面的这两种无非就是向左还是向右查询的问题，特别注意在跳出循环后需要判断是否出界

最后，也是最常用的二分查询，直接用来查询某个元素

function binarySearch(data,target){
    if (!data.length) {
        return -1
    }
    let left = 0;
    let right = data.length - 1;

    while (left <= right) {

        let mid = left + Math.floor((right - left) / 2);

        if (target === data[mid]) {
   return mid;    
        } else if (target < data[mid]) {
            // 左侧
            right = mid - 1
        } else if (target > data[mid]) {
            // 右侧；
            left = mid + 1;
        }
    }
    
    // 没有则返回-1
    return -1
}