数据结构、算法相关收藏

[lizhongzhen11]

1. VisuAlgo
2. 算法导论视频
3. 可以买本《数据结构与算法 JavaScript描述》，适合入门
4. 有一定实力的可以去刷牛客网和leetcode
5. JavaScript 算法与数据结构
6. LeetCodeAnimation
   动画版

自己写的相关记录

1. 读《数据结构与算法 JavaScript描述》——实现一个栈结构
2. 读《数据结构与算法 JavaScript描述》——实现一个队列结构
3. 读《数据结构与算法 JavaScript描述》——实现一个链表结构

排序

• 视频 | 手撕九大经典排序算法，看我就够了！

冒泡与选择排序 2020-08-06

以前我只会冒泡和快排，今天知道了 选择，一时没绕过来，都不知道它和冒泡有什么区别，研究了一段时间才发现：

选择排序，也用到了嵌套 for 循环，不过它会在每次遍历时先保存当前循环的第一个数 arr[i]，假设它为当前循环中最小的 min，然后用后面的数与 min 比较，如果比 min 还小，则改变 min 的值为这个更小的数，一直到内循环结束，再通过 arr[i] = min 即可将当前内循环最小的数移动到当前循环开始的索引位置。

let arr = [9,8,5,9,6,7,19,2,1]
for (let i = 0; i < arr.length - 1; i ++) {
  let min = arr[i]
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[j] < min) {
      let temp = arr[j]
      arr[j] = min
      min = temp
    }
  }
  arr[i] = min
}

插入排序 2020-08-07

今天又学到了个 插入排序，还是嵌套循环，看书上定义一时没明白什么意思，有点迷糊，看看代码手动去敲一遍就容易理解了。实话说这三个排序还是 冒泡 最易懂，可能因为接触的早吧。

for (let i = 1; i < arr.length; i++) {
  let temp = arr[i]
  let j = i
  while(j > 0 && arr[j - 1] > temp) {
    arr[j] = arr[j - 1]
    j--
  }
  arr[j] = temp
}

注意：最后是 arr[j] = temp，用的是内循环的 j 而不是外循环的 i！

注意：插入排序 外循环是从索引 1 开始的

希尔排序 2020-08-7

这个排序搞了我半天！真不容易懂啊。属于 插入排序 的变种升级，普通 插入排序 都是一个接一个顺序遍历的，希尔排序 感觉是先选好开始遍历的 起始位置（间隔序列里面的元素），然后从起始位置遍历到数组末尾。
重点是内部第三层循环，为何是 j >= gaps[g] 还有 j - gaps[g]？说白了为何与第一层循环确定的间隔比而不是与第二层循环确定的索引比？

其实第一层循环确定的是 间隔 即遍历 起始位置，内部嵌套的两层循环都应该与这个 起始位置 比较。如果第三层循环直接与第二层自增的索引比较，那将毫无意义，最多当 j === i 时才会满足，无法确定连续元素的大小关系。而与第一层的 起始位置 对比，第三层循环通过 j = j - gaps[g] 可以确定 起始位置 后面的连续元素。

let gaps = [5, 3, 1] // 间隔序列
let arr = [9,8,5,9,6,7,19,2,1]

// 遍历间隔序列
for (let g = 0; g < gaps.length; g++) {
  // 根据 间隔 确定遍历起始位置，一直到数组最后一个
  for (let i = gaps[g]; i < arr.length; i++) {
    let temp = arr[i]
    let j
    for (j = i; j >= gaps[g] && arr[j - gaps[g]] > temp; j = j - gaps[g]) {
      arr[j] = arr[j - gaps[g]]
    }
    arr[j] = temp
  }
}

归并排序 2020-08-08

《数据结构与算法JavaScript描述》中提到 归并排序 分为 自顶向下（需要递归）（大多数情况） 和 自底向上 两种，书中用的是 自底向上，书中的看不进去，在 十大经典排序算法动画与解析，看我就够了！（配代码完全版） 找到了 自顶向下 版本代码，看了动画想自己去实现，无从下笔，只能看他代码实现了，看着看着自然就恍然大悟了，这里给出js版：

let arr = [9,8,5,9,6,7,19,2,1]

const slice = (arr) => {
  if (arr.length < 2) {
    return arr
  }
  let middle = Math.floor(arr.length / 2)
  let left = arr.slice(0, middle) // 注意：这里不能 middle + 1，否则栈溢出
  let right = arr.slice(middle)
  return merge(slice(left), slice(right))
}

const merge = (left, right) => {
  let result = []
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left[0])
      left = left.slice(1)
    } else {
      result.push(right[0])
      right = right.slice(1)
    }
  }

  while (left.length > 0) {
    result.push(left[0])
    left = left.slice(1)
  }
  while (right.length > 0) {
    result.push(right[0])
    right = right.slice(1)   
  }

  return result
}

我在一开始编写时，slice 里面代码是这样的：

left = arr.slice(0, middle + 1)

但是测试时直接报 栈溢出。一开始很是费解，直到我看到这里，想到如果 arr 一开始是 [3, 2] 这种只有两个元素的数组，那么传进去程序将会一直陷入对 left 的无限求值，并且 left 值始终维持在 [3, 2] 不会改变！
而 left = arr.slice(0, middle) 则会避免这种情况，无论 middle 是奇数还是偶数，都能保证递归到最底层时只有一个元素！

这是细节问题，我自己想优化下写法结果打脸了，这样也好，能加深理解。