专栏首页M不作声数据结构与算法

数据结构与算法

常见的数据结构

  • 线性表 链表是一个线性结构,同时也是一个天然的递归结构,链表增加了节点的指针域,空间开销比较大。 循环单链表是链表的最后一个节点指向第一个节点,构成一个链环。 双向链表是节点中包含两个指针部分,一个指向前驱元,一个指向后继元。
  • 栈和队列 栈是一个线性结构,只能在某一端添加或删除数据,遵循先进后出的原则。对栈的基本操作有进栈(push)(pop)出栈,相当于插入和删除最后一个元素。可以用数组实现。 队列是一种特殊的线性表,只允许在表的前端(front)进行删除操作,在表的后端(rear)进行插入操作。
  • 树与二叉树
    • 树,是由n个有限节点组成一个具有层次关系的集合,是一种非常重要的数据结构。每个节点有零个或多个子节点,没有父节点的节点称为根节点;每个非根节点有且只有一个父节点;没有子节点的节点称为叶子结点;除了根节点外,每个子节点都可以分为多个不相交的子树。
    • 二叉树,是每个节点最多拥有两个子节点,分别为左节点和右节点
    • 二叉查找树,也叫二叉排序树,二叉搜索树。与二叉树的区别在于每个节点的值都比他的左子树大,比右子树小
  • 图 图,是一种比树更为复杂的数据结构。树的节点之间是一对多的关系,且存在父子的层级划分;图的顶点之间是多对多的关系,并且所有的节点都是平等的,没有谁是父谁是子。

树的遍历

树的遍历分为深度优先搜索和广度优先搜索。深度优先搜索有先序遍历、中序遍历、和后序遍历三种方式。广度优先搜索是层次遍历

先序遍历算法:先访问根节点,然后访问左节点,最后访问右节点。

preTraversal() {
  this._pre(this.root)
}
_pre(node) {
  if(node) {
    console.log(node.value)
    this._pre(node.left)
    this._pre(node.right)
  }
}

中序遍历算法:先访问左节点,然后访问根节点,最后访问右节点。

midTraversal() {
  this._mid(this.root)
}

_mid(node) {
  if(node) {
    this._mid(node.left)
    console.(node.value)
    this._mid(node.right)
  }
}

后序遍历算法:先访问左节点,然后访问右节点,最后访问根节点。

backIraversal() {
  this._back(this.root)
}
_bcak(node) {
  if(node) {
    this._back(node.left)
    this._back(node.right)
    console.log(node.value)
  }
}

层次遍历,使用队列结构完成。

breadthTraversal() {
  if(!this.root) return null
  let q = new Queue()
  q.enQueue(this.root)
  while (!q.isEmpty()) {
    let n = q.deQueue()
    if(n.left) q.enQueue(n.left)
    if(n.right) q.enQueue(n.right)
  }
}

树节点的插入和删除

  • 节点插入 将该节点的值与树上节点的值做比较,如果小于,继续遍历左子树;如果大于,继续遍历右子树。如果左右子树为空,那么直接插入。如果大于左子树,则判断右子树;如果小于右子树,则判断左子树。
  • 节点删除,节点删除分为三种情况
    • 需要删除的节点没有子树
    • 需要删除的节点只有一条子树
    • 需要删除的节点有左右两条树

    最复杂的是第三种情况,解决办法为:找到需要删除节点p的直接前缀p(或直接后缀)s,用s来替换节点p,然后再删除此节点s。

delect(v) {
  this.root = this._delect(this.root, v)
}
_delect(node, v){
  if(!node) return null
  // 判断在左子树还是在右子树
  if(node.value < v) {
    node.right = this._delect(node.right.v)
  } eles if(node.value > v) {
    node.left = this._delect(node.left.v)
  } else {
    if (!node.left) return node.right
    if (!node.right) return node.left
    // _getMin()获取右树上最小的节点 _delectMin()删除最小节点
    // 
    let min = this._getMin(node.right)
    min.right = this._delectMin(node.right)
    min.left = node.left
    node = min
  }
  // 维护size
  node.size = this._getSize(node.left) + this._getSize(node.right) + 1
  return node
}

插入排序

构建有序序列,扫描已排序序列,将数据插入到有序序列中合适的位置。

function checkArray(array) {
  return Array.isArray(array)
}

function swaps(array, left, right) {
  let rightValue = array[right]
  array[right] = array[left]
  array[left] = rightValue
}

function insertion(array) {
  if (!checkArray(array)) 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;
}

选择排序

在序列中找出最小的元素,放到排序序列的起始位置,然后再从剩下的序列中再找出最小的元素,重复这个过程。

function select(array) {
  if (!checkArray(array)) return
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    for(let j = i + 1; j < array.length; j++) {
      minIndex = array[j] < array[minIndex] ? j : minIndex;
    }
    swap(array, i, minIndex);
  }
  return array;
}

冒泡排序

比较两个元素,将较大的元素放在后边,当一次循环完成后,最大的元素被放在最后的位置,循环这个过程,知道排序完成。

代码实现:

funciton bubble(array) {
  checkArray(array);
  for (let i = array.legth - 1; i > 0; i--){
    for (let j = 0; j < i; j++) {
      if (array[j] > array[j + 1]) swap(array, j, j+1)
    }
  }
}

快速排序

在序列中选取一个值,将比该值小的元素放在左边,比该值大的放在右边,在分别对左右两侧的元素做相同的操作,直到排序完成。

function sort(array) {
  if (!checkArray(array)) return
  quickSort(array, 0, array.length - 1);
  return array;
}

function quickSort(array, left, right) {
  if (left < right) {
    swap(array, , 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 sort(array) {
  if (!checkArray(array)) return
  mergeSort(array, 0, array.length - 1);
  return array;
}

function mergeSort(array, left, right) {
  // 左右索引相同说明已经只有一个数
  if (left === right) return;
  // 等同于 `left + (right - left) / 2`
  // 相比 `(left + right) / 2` 来说更加安全,不会溢出
  // 使用位运算是因为位运算比四则运算快
  let mid = parseInt(left + ((right - left) >> 1));
  mergeSort(array, left, mid);
  mergeSort(array, mid + 1, right);

  let help = [];
  let i = 0;
  let p1 = left;
  let 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 自平衡二叉树实现及时间复杂度分析

    我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:

    不作声
  • JS手动实现一个链表

    链表是一个「线性」结构,充分利用了计算机的内存空间,实现了灵活的内存状态管理。在物理存储结构上,链表是不连续、无顺序的存储结构,在逻辑上,通过使用节点的引用实现...

    不作声
  • 再也不用怕面试问二叉树了

    二叉树是一种非常重要的数据结构。在算法题中经常会使用到,在面试中的占比也是非常大的。

    不作声
  • <>并归排序&&小和问题&&逆序对问题

    master公式(也称主方法)是用来利用分治策略来解决问题经常使用的时间复杂度的分析方法,(补充:分治策略的递归解法还有两个常用的方法叫做代入法和递归树法,以后...

    大学里的混子
  • LeetCode 94 | 构造出所有二叉搜索树

    今天是LeetCode专题第61篇文章,我们一起来看的是LeetCode95题,Unique Binary Search Trees II(不同的二叉搜索树II...

    TechFlow-承志
  • 每日两题 T37

    一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

    合一大师
  • 【leetcode刷题】T80-最长特殊序列 II

    给定字符串列表,你需要从它们中找出最长的特殊序列。最长特殊序列定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。

    木又AI帮
  • 关于Kubernetes证书的那点事

    众所周知。Kubernetes 需要 PKI 证书才能进行基于 TLS 的身份验证。如果你是使用kubeadm安装的 Kubernetes, 则会自动生成集群所...

    聂伟星
  • 如何做好电商大促的容量规划

    在进行整体电商架构设计过程中,关注系统的稳定性是很重要的工作,也是对架构师能力的一种考察,特别是在电商系统准备搞一次大促时,合理的对系统进行容量规划就显得尤为重...

    春哥大魔王
  • 在OpenOffice.org和微软Office之间共享文档

    原文:Sharing files between OpenOffice.org and Microsoft Office。翻译可能也比较随意。 本文版权请向原文...

    张善友

扫码关注云+社区

领取腾讯云代金券