POST

常见的算法

2022/03/16 算法 共 5453 字，约 16 分钟

排序算法

冒泡排序

maopao

基本原理：从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较最后一个元素，此时最后一个元素就是该数组中最大的树。下一轮重复以上操作，但最后一个元素已经是最大数了，不需要进行比较，只需要比较到 length - 1 的位置。

function swap(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}
function bubble(array) {
  if (!array || array.length <= 2) return
  for(let i = array.length - 1; i > 0; i--) {
    // 从 0 到 length - 1 遍历
    for(let j = 0; j < i; j++) {
      if (array[j] > array[j + 1]) {
        swap(array, j, j + 1)
      }
    }
  }
  return array
}

时间复杂度为 O(n * n)

选择排序

xuanze

基本原理：遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的元素交换。第一次遍历完成后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上面的操作。

function swap(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}
function selection(array) {
  if (!array || array.length <= 2) return
  for(let i = 0; i < array.length; i++) {
    let minIndex = i
    for(let j = i + 1; j < array.length; j++) {
      minIndex = array[i] < array[minIndex] ? j : minIndex
    }
    swap(array, i, minIndex)
  }
  return array
}

时间复杂度为 O(n * n)

插入排序

charu

基本原理：第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

function swap(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}
function insertion(array) {
  if (!array || array.length <= 2) return
  for(let i = 1; i < array.length; i++) {
    for(let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
      swap(array, j, j + 1)
    }
  }
  return array
}

时间复杂度为 O(n * n)

归并排序

guibing

基本原理：递归的将数组两两分开直到最多包含两个元素，然后将数组排序合并，最终合并为排序好的数组

function sort(array) {
  if (!array || array.length <= 2) return
  mergeSort(array, 0, array.length - 1)
  return array
}
function mergeSort(array, left, right) {
  // 左右索引相同说明已经只有一个数
  if (left === right) return
  // 等同于 left + (rigth - left) / 2，使用位运算是因为位运算比四则运算快
  let mid = parseInt(left + ((right - left) >> 1))
  mergeSort(array, left, mid)
  mergeSort(array, mid + 1, right)

  let help = []
  let i = 0, p1 = left, p2 = mid + 1
  while(p1 <= mid && p2 <= right) {
    help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++]
  }
  while(p1 <= mid) {
    help[i++] = array[p1++]
  }
  while(p2 <= right) {
    help[i++] = array[p2++]
  }
  for(let i = 0; i < help.length; i++) {
    array[left + i] = help[i]
  }
  return array
}

时间复杂度为 O(N * logN)

快速排序

kuaisu

基本原理：随机选取一个数组中的值作为基准值，从左至右取值与基准值对比大小。比基准值小的放数组左边，大的放右边，对比完成后将基准值和第一个比基准值大的值交换位置，然后将数组以基准值的位置分为两部分，继续递归以上操作。

function sort(array) {
  if (!array || array.length <= 2) return
  quickSort(array, 0, array.length - 1)
  return array
}
function quickSort(array, left, right) {
  if (left < right) {
    swap(array, left, right)
    // 随机取值，然后和末尾交换，这样做比固定取一个位置的复杂度略低
    let indexs = part(array, parseInt(Math.random() * (right - left + 1) + left, right))
    quickSort(array, left, indexs[0])
    quickSort(array, indexs[1] + 1, right)
  }
}
function part(array, left, right) {
  let less = left - 1
  let more = right
  while(left < more) {
    if (array[left] < array[right]) {
      // 当前值比基准值小，less 和 left 都加一
      ++less
      ++left
    } else if (array[left] > array[right]) {
      // 当前值比基准值大，将当前值和右边的值交换，并且不改变 left，因为当前换过来的值还没有判断过大小
      swap(array, --more, left)
    } else {
      // 和基准值相同，只移动下标
      left++
    }
  }
  // 将基准值和比基准值大的第一个值交换位置，这样数组就变成 [比基准值小, 基准值, 比基准值大]
  swap(array, right, more)
  return [less, more]
}
function swap(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}

二叉树

二叉树的先序、中序、后序遍历

根据访问根节点的时机进行记忆

  • 先序遍历表示先访问根节点，然后访问左节点，最后访问右节点
  • 中序遍历表示先访问左节点，然后访问根节点，最后访问右节点
  • 后续遍历表示先访问左节点，然后访问右节点，最后访问根节点

递归方法实现

function TreeNode(val) {
  this.val = val
  this.left = this.right = null
}
var traversal = function(root) {
  if (root) {
    // 先序
    traversal(root.left)
    // 中序
    traversal(root.right)
    // 后序
  }
}

非递归实现

非递归使用栈的结构，通过栈的先进后出模拟递归实现

  • 先序遍历：
    function pre(root) {
  if (root) {
    let stack = []
    stack.push(root)
    // 判断栈是否为空
    while(stack.length > 0) {
      // 弹出栈顶元素
      root = stack.pop()
      console.log(root)
      // 先序遍历是先左后右，栈是先进后出，所以先 push 右边，再 push 左边
      if (root.right) {
        stack.push(root.right)
      }
      if (root.left) {
        stack.push(root.left)
      }
    }
  }
}
  • 中序遍历：
    function mid(root) {
  if (root) {
    let stack = []
    // 中序遍历是先左再根后右，首先应该把最左边节点遍历到底依次 push 进栈
    // 当左边没有节点时，就打印栈顶元素，然后寻找右节点
    // 对于最左边的叶节点来说，可以把它看成是 null 节点的父节点
    // 左边打印不出东西就把父节点拿出来打印，然后再看右节点
    while(stack.length > 0 || root) {
      if (root) {
        stack.push(root)
        root = root.left
      } else {
        root = stack.pop()
        console.log(root)
        root = root.right
      }
    }
  }
}
  • 后续遍历：
    function pos(root) {
  if (root) {
    let stack1 = []
    let stack2 = []
    // 后续遍历是先左再由后跟，所以对于一个栈来说
    // 应该先 push 根节点，然后 push 右节点，最后 push 左节点
    stack1.push(root)
    while(stack1.length > 0) {
      root = stack1.pop()
      stack2.push(root)
      if (root.left) {
        stack1.push(root.left)
      }
      if (root.right) {
        stack1.push(root.right)
      }
    }
    while(stack2.length > 0) {
      console.log(stack2.pop())
    }
  }
}

深度优先遍历

深度优先遍历包括：

  • 先序遍历，先访问根节点，然后访问左节点，最后访问右节点
  • 中序遍历，先访问左节点，然后访问根节点，最后访问右节点
  • 后序遍历，先访问左节点，然后访问右节点，最后访问根节点

先序遍历可以用来显示目录结构等；中序遍历可以实现表达式树，在编译底层很有用；后序遍历可以用来实现计算机目录内的文件及其信息等。

先序遍历

  • 递归
    function dfs(root) {
  if (root) {
    console.log(root)
    dfs(root.left)
    dfs(root.right)
  }
}
  • 非递归
    function dfs(root) {
  if (root) {
    const stack = [root]
    while(stack.length) {
      root = stack.pop() // 取出栈顶元素
      console.log(root)
      // 因为先序遍历是先左后右，栈是先进后出结构
      // 所以先 push 右边再 push 左边
      if (root.right) stack.push(root.right)
      if (root.left) stack.push(root.left)
    }
  }
}

中序遍历

  • 递归
    function dfs(root) {
  if (root) {
    dfs(root.left)
    console.log(root)
    dfs(root.right)
  }
}
  • 非递归
    function dfs(root) {
  if (root) {
    const stack = []
    // 中序遍历是先左再根最后右
    // 所以⾸先应该先把最左边节点遍历到底依次 push 进栈
    // 当左边没有节点时，就打印栈顶元素，然后寻找右节点
    // 对于最左边的叶节点来说，可以把它看成是两个 null 节点的⽗节点
    // 左边打印不出东⻄就把⽗节点拿出来打印，然后再看右节点
    while(stack.length || root) {
      if (root) {
        stack.push(root)
        root = root.left
      } else {
        root = stack.pop()
        console.log(root)
        root = root.right
      }
    }
  }
}

后序遍历

  • 递归
    function dfs(root) {
  if (root) {
    dfs(root.left)
    dfs(root.right)
    console.log(root)
  }
}
  • 非递归
    function dfs(root) {
  if (root) {
    const stack1 = []
    const stack2 = []
    stack1.push(root)
    while(stack1.length) {
      root = stack1.pop()
      stack2.push(root)
      if (root.left) stack1.push(root.left)
      if (root.right) stack1.push(root.right)
    }
    while(stack2.length) {
      console.log(stack2.pop())
    }
  }
}

广度优先遍历

广度遍历是从二叉树的根结点开始，自上而下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问

  • 递归
  • 非递归
    function bfs(root) {
  const queue = [node]
  while(queue.length) {
    root = queue.shift()
    console.log(root.value)
    if (root.left) queue.push(root.left)
    if (root.right) queue.push(root.right)
  }
}
算法