数据结构与算法-进阶知识

// 排序和搜索是什么？
1. 排序：把某个乱序的数组变成升序或者降序的数组
2. 搜索：找出数组中某个元素的下标
3. js 中的排序：数组的 sort 方法
4. js 中的搜索：数组的 indexOf 方法
5. 排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序
6. 搜索算法：顺序搜索、二分搜索
----------------------------------------------------------------------------------------------
// 冒泡排序
1. 比较所有相邻元素，如果第一个比第二个大，则交换它们
2. 一轮下来，可以保证最后一个数是最大的
3. 执行 n - 1 轮，就可以完成排序
4. 冒泡排序的时间复杂度是 O(n^2) // 两个嵌套循环
Array.prototype.bubbleSort = () => {
  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
      }
    }
  }
}
const arr = [1, 2, 3, 4, 5]
arr.bubbleSort()
----------------------------------------------------------------------------------------------
// 选择排序
1. 找出数组中的最小值，选中它并将其放置在第一位
2. 接着找到第二小的值，选中它并将其放置在第二位
3. 以此类推，执行 n - 1 轮
4. 选择排序的时间复杂度是 O(n^2) // 两个嵌套循环
Array.prototype.selectionSort = () => {
  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 = i
      }
    }
    if (indexMin !== i) {
      const temp = this[i]
      this[i] = this[indexMin]
      this[indexMin] = temp
    }
  }
}
const arr = [1, 2, 3, 4, 5]
arr.selectionSort()
----------------------------------------------------------------------------------------------
// 插入排序
1. 从第二个数开始往前比
2. 比它大就往后排
3. 以此类推进行到最后一个数
4. 插入排序的时间复杂度是 O(n^2) // 两个嵌套循环
Array.prototype.insertionSort = () => {
  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
      }
      i--
    }
    this[j] = temp
  }
}
const arr = [1, 2, 3, 4, 5]
arr.insertionSort()
----------------------------------------------------------------------------------------------
// 归并排序
1. 分：把数组劈成两半，再递归的对子数组进行分的操作，直到分成一个个单独的数
2. 合：把两个数组合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组
3. 怎么合并两个有序数组？
    1. 新建一个空数组 res，用于存放最终排序后的数组
    2. 比较两个有序数组的头部，较小者出队并推入 res 中
    3. 如果两个数组还要值，就重复第二步
4. 归并排序的时间复杂度是 O(n * logN) // 分的时间复杂度是 O(logN) 合的时间复杂度是 O(n)
Array.prototype.mergeSort = () => {
  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] ? oderLeft.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
  })
}
const arr = [1, 2, 3, 4, 5]
arr.mergeSort()
----------------------------------------------------------------------------------------------
// 快速排序
1. 分区：从数组中任意选择一个基准，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面
2. 递归：递归的对基准前后的子数组进行分区
3. 快速排序的时间复杂度是 O(n * logN) // 递归的时间复杂度是 O(logN) 分区的时间复杂度是 O(n)
Array.prototype.quickSort = () => {
  const rec = arr => {
    if (arr.length === 1) {
      return arr
    }
    const left = []
    const right = []
    const mid = arr[0]
    for (let i = 1; i < arr.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
  })
}
const arr = [1, 2, 3, 4, 5]
arr.quickSort()
----------------------------------------------------------------------------------------------
// 顺序搜索
1. 遍历数组
2. 找到跟目标值相等的元素，就返回它的下标
3. 遍历结束后，如果没有搜索到目标值，就返回 -1
4. 快速排序的时间复杂度是 O(n * logN) // 递归的时间复杂度是 O(logN) 分区的时间复杂度是 O(n)
Array.prototype.sequentialSearch = () => {
  for (let i = 0; i < this.length; i++) {
    if (this[i] === item) {
      return i
    }
  }
  return -1
}
const arr = [1, 2, 3, 4, 5]
arr.sequentialSearch(3)
----------------------------------------------------------------------------------------------
// 二分搜索
1. 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
2. 如果目标值大于或小于中间元素，则在大于或小于中间元素的那一半数组中搜索
3. 二分排序的时间复杂度是 O(logN) // 每一次比较都使搜索范围缩小一半
Array.prototype.binarySearch = () => {
  let low = 0
  let 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
}
const arr = [1, 2, 3, 4, 5]
arr.binarySearch(3)
----------------------------------------------------------------------------------------------
// 分而治之是什么？
1. 分而治之是算法设计中的一种方法
2. 它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题
3. 使用场景：// 分、解、合
    1. 归并排序：
      分：把数组从中间一分为二
      解：递归的对子数组进行归并排序
      合：合并有序子数组
    2. 快速排序
      分：选基准，按基准把数组分成两个子数组
      解：递归的对两个子数组进行快速排序
      合：对两个子数组进行合并
----------------------------------------------------------------------------------------------
// 动态规划是什么？
1. 动态规划是算法设计中的一种方法
2. 它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题
3. 使用场景：斐波那数列
----------------------------------------------------------------------------------------------
// 分而治之和动态规划的区别
1. 分解出来的子问题是否是独立的
2. 如果是相互独立的就是分而治之
3. 如果是相互重叠的就是动态规划
----------------------------------------------------------------------------------------------
// 贪心算法是什么？
1. 贪心算法是算法设计中的一种方法
2. 期盼通过每个阶段的局部最优选择，从而达到全局的最优
3. 结果并不一定是最优
----------------------------------------------------------------------------------------------
// 回溯算法是什么？
1. 回溯算法是算法设计中的一种方法
2. 回溯算法是一种渐进式寻找并构建问题解决方式的策略
3. 回溯算法会先从一个可能的动作开始解决问题，如果不行就回溯并选择另一个动作，直到将问题解决