进阶算法之“搜索算法”

一、理论

1. 排序和搜索简介

• 排序：把某个乱序的数组变成升序或降序数组
• 搜索：找出数组中某个元素的下标

1.1 js中的排序和搜索

• js中的排序：sort()
• js中的搜索：indexOf()

1.2 排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序

1.3 搜索算法

• 顺序搜索
• 二分搜索

2. js实现排序

2.1 冒泡排序

2.2.1 思路

• 比较相邻元素，如果第一个比第二个大，则交换他们
• 一轮下来，保证最后一个数是最大的
• 执行n-1轮即完成排序

2.2.2 动画演示

冒泡排序动画演示

2.2.3 coding part

Array.prototype.bubbleSort = function () {
  for(let i = 0; i < this.length - 1; i++) {
    for(let j = 0; j < this.length - 1 - i; j++) {
      if(this[j] > this[j + 1]) {
        const temp = this[j]
        this[j] = this[j + 1]
        this[j + 1] = temp
      }
    }
  }
}

2.2.4 时间复杂度

• 时间复杂度：O(n^2)

2.2 选择排序

2.2.1 思路

• 找到数组的最小值，选中并将其放在第一位
• 找到数组的第二小值，选中并将其放在第二位
• 以此类推，执行n-1轮

2.2.2 动画演示

选择排序动画演示

2.2.3 coding part

Array.prototype.selectionSort = function () {
  for(let i = 0; i < this.length-1; i++) {
    let indexMin = i
    for(let j = i; j < this.length; j++) {
      if(this[j] < this[indexMin]) {
        indexMin = j
      }
    }
    if(indexMin !== i) {
      const temp = this[i]
      this[i] = this[indexMin]
      this[indexMin] = temp
    }
  }
}

2.2.4 时间复杂度

• 时间复杂度：O(n^2)

2.3 插入排序

2.3.1 思路

• 从第二个数开始往前比
• 比他大就往后排
• 以此类推进行到最后一个数

2.3.2 动画演示

插入排序动画演示

2.3.3 coding part

Array.prototype.insertionSort = function () {
  for(let i = 1; i < this.length; i++) {
    const temp = this[i]
    let j = i
    while(j > 0) {
      if(this[j-1] > temp) {
        this[j] = this[j-1]
      } else {
        break
      }
      j--
    }
    this[j] = temp
  }
}

2.3.4 时间复杂度

• 时间复杂度：O(n^2)

2.4 归并排序

2.4.1 思路

• 分：把数组劈成两半，再递归得将子数组进行“分”操作，直到分成一个个单独的数
• 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并成一个完整数组

合并两个有序数组

• 新建一个空数组res，用于存放最终排序后的数组
• 比较两个有序数组的头部，较小者出队并推入res中

2.4.2 动画演示

归并排序动画演示

2.4.3 coding part

Array.prototype.mergeSort = function () {
  const rec = arr => {
    if(arr.length == 1) return arr
    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid, arr.length)
    const orderLeft = rec(left)
    const orderRight = rec(right)
    const res = []
    while(orderLeft.length || orderRight.length) {
      if(orderLeft.length && orderRight.length) {
        res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
      } else if(orderLeft.length) {
        res.push(orderLeft.shift())
      } else if(orderRight.length) {
        res.push(orderRight.shift())
      }
    }
    return res
  }
  const res = rec(this)
  res.forEach((n, i) => this[i] = n)
}

2.4.4 时间复杂度

• 分的时间复杂度：O(logn)
• 合的时间复杂度：O(n)
• 时间复杂度：O(nlogn)

2.5 快速排序

2.5.1 思路

• 分区：从数组中任意选择一个基准，所有比基准小的元素放在基准前，比基准小的元素放在基准后
• 递归：递归地对基准前后的子数组进行分区

2.5.2 动画演示

快速排序动画演示

2.5.3 coding part

Array.prototype.quickSort = function () {
  const rec = (arr) => {
    if(arr.length == 1) return arr
    const left = []
    const right = []
    const mid = arr[0];
    for(let i = 1; i < this.length; i++) {
      if(arr[i] < mid) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    return [...rec(left), mid, ...rec(right)]
  }
  const res = rec(this)
  res.forEach((n, i) => this[i] = n)
}

2.5.4 时间复杂度

• 递归的时间复杂度：O(logn)
• 分区的时间复杂度：O(n)
• 时间复杂度：O(nlogn)

3. js实现搜索

3.1 顺序搜索

3.1.1 思路

• 遍历数组
• 找到跟目标值相等的元素，返回其下标
• 遍历结束后，若没有找到相等元素则返回-1

3.1.2 coding part

Array.prototype.sequentialSearch = function(item) {
  for(let i = 0; i < this.length; i++) {
    if(this[i] === item) {
      return i
    }
  }
  return -1
}

3.1.3 时间复杂度

• 时间复杂度：O(n)

3.2 二分搜索

前提：数组有序

3.2.1 思路

• 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
• 如果目标值大于或小于中间元素，则在大于或小于中间元素的那一半数组中搜索

3.2.2 coding part

Array.prototype.binarySearch = function(item) {
  let low = 0, high = this.length - 1
  while(low <= high) {
    const mid = Math.floor((low + high) / 2)
    const element = this[mid]
    if(element < item) {
      low = mid + 1
    } else if(element > item) {
      high = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

3.2.3 时间复杂度

• 时间复杂度：O(logn)

二、刷题

1. 合并两个有序链表（21）

1.1 题目描述

• 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

1.2 解题思路

• 与归并排序中合并两个有序数组很相似
• 将数组替换成链表

1.3 解题步骤

• 新建一个新链表，作为返回结果
• 用指针遍历两个有序数组，并比较两个链表当前节点，较小者先接入新链表并将指针后移一步
• 链表遍历结束，返回新链表

function mergeTwoLists(l1, l2) {
  const res = new ListNode(0);
  let p = res, p1 = l1, p2 = l2;
  while(p1 && p2) {
    if(p1.val < p2.val) {
      p.next = p1;
      p1 = p1.next;
    } else {
      p.next = p2;
      p2 = p2.next;
    }
    p = p.next;
  }
  if(p1) {
    p.next = p1;
  }
  if(p2) {
    p.next = p2
  }
  return res.next
}

1.4 时间复杂度&空间复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

2. 猜数字大小（374）

2.1 题目描述

• 猜数字游戏的规则如下：
  • 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
  • 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
  • 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
    • -1：我的数字比较小 pick < num
    • 1：我的数字比较大 pick > num
    • 0：恭喜！你猜对了！pick == num

2.2 解题思路

输入：n = 10, pick = 6
输出：6

• 二分搜索
• 调用guess函数来判断中间元素是否是目标值

2.3 解题步骤

• 二分搜索

function guessNumber(n) {
  let low = 1, high = n;
  while(low <= high) {
    const mid = Math.floor((low + high) / 2);
    const res = guess(mid)
    if(res === 0) {
      return mid
    } else if(res === 1) {
      low = mid + 1
    } else if(res === -1) {
      high = mid - 1
    }
  }
}

2.4 时间复杂度&空间复杂度

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

三、总结 -- 技术要点