前端面试

快速排序

参考：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)
  const 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) {
  const 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) {
    const 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) {
    const 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) {
    const 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
}