# dataStructuresAndAlgorithms **Repository Path**: zyhua/dataStructuresAndAlgorithms ## Basic Information - **Project Name**: dataStructuresAndAlgorithms - **Description**: javascript数据结构与算法笔记 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-07-18 - **Last Updated**: 2021-10-07 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # dataStructuresAndAlgorithms #### 介绍 javascript数据结构与算法笔记 #### 哈希表 哈希表通常是基于数组进行实现的，但是相对于数组，它有很多优势 * 提供快速的插入-删除-查找操作 * 无论多少数据，插入和删除值需要接近常量的时间：即O(1)的时间级。实际上，只需要几个机器指令即可完成 * 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素 * 哈希表相对于树来说编码要容易很多 哈希表相对于数组的不足 * 哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素 * 通常情况下，哈希表中的key是不允许重复的，不能放置相同的key，用于保存不同的元素 哈希表的结构就是数组，但是神奇的地方在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取到HashCode #### 二叉搜索树 [二叉搜索树相关资料](https://www.jianshu.com/p/ad811c95aad3) 二叉搜索树是一颗二叉树, 可以为空；如果不为空，满足以下性质 * 非空左子树的所有键值小于其根结点的键值 * 非空右子树的所有键值大于其根结点的键值 * 左、右子树本身也都是二叉搜索树 二叉搜索树的特点 * 二叉搜索树的特点就是相对较小的值总是保存在左结点上, 相对较大的值总是保存在右结点上 * 查找效率非常高, 这也是二叉搜索树中, 搜索的来源 先序遍历 1. 访问根结点 2. 先序遍历其左子树 3. 先序遍历其右子树 中序遍历 1. 中序遍历其左子树 2. 访问根结点 3. 中序遍历其右子树 后序遍历 1. 后序遍历其左子树 2. 后序遍历其右子树 3. 访问根结点 #### 红黑树 红黑树除了符合二叉搜索树的基本规则外，还添加了以下特性 1. 节点是红色或黑色 2. 根节点是黑色 3. 每个叶子节点都是黑色的空节点（NIL节点） 4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点） 5. 从任一节点到每个叶子的所有路径都包含相同数目的黑色节点(如 从根节点出发到每个叶子节点) ##### 红黑树的相对平衡 前的约束，确保了红黑树的关键特性： * 从根到叶子的最长可能路径，不会超过最短可能路径的两倍长 * 结果就是这个数基本是平衡的 * 虽然没有做到绝对的平衡，但是可以保证在最坏的情况下，依然是高效的 为什么可以做到最长路径不超过最短路径的两倍 * 性质4决定了路径不能有两个相连的红色节点 * 最短的可能路径都是黑色节点 * 最长的可能路径是红色和黑色交替 * 性质5所有路径都有相同数目的黑色节点 * 这就表明了没有路径能多于任何其他路径的两倍 ##### 红黑树的变色 插入一个新节点时，有可能树不再平衡，可以通过三种方式的变换，让树保持平衡 * 换色、左旋转、右旋转 变色 * 为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色 首先，需要知道插入的新的节点通常都是红色节点 * 在插入节点为红色的时候，有可能插入一次是不违反红黑树任何规则的 * 而插入黑色节点，必然会导致有一条路径上多了黑色节点，这是很难调整的 * 红色节点可能导致出现红红相连的情况，但是这种情况可以通过颜色调换和旋转来调整 左旋转 逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子 ![](./images/1.jpg) 右旋转 顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子 ![](./images/2.jpg) #### 图论 什么是图 * 图结构是一种与树结构有些相似的数据结构 * 图论是数学的一个分支，并且在数学的概念上，树是图的一种 * 它以图为研究对象，研究顶点和边组成的图形的数学理论和方法 * 主要研究的目的是事物之间的关系，顶点代表，边代表两个事物间的关系 特点 * 一组顶点：通常用V（vertex）表示顶点的集合 * 一组边：通常用E（Edge）表示边的集合 * 边是顶点和顶点之间的连线 * 边可以是有向的，也可以是无向的 * 比如 A --- B，通常表示无向；A ---> B，通常表示有向 ### 排序算法 #### 常见大O表示形式 | 符号 | 名称 | | ---- | ---- | | O(1) | 常数的 | | O(log(n)) | 对数的 | | O(n) | 线性的 | | O(nlog(n)) | 线性和对数乘积 | | O(n²) | 平方 | | O(2ⁿ) | 指数 | 推导大O表示法的方式 * 用常量1取代运行时间中所有的加法常量，如：76 --> O(1) * 在修改后的运行次数函数中，只保留最高阶项，如：2N² + 3n + 1 --> O(2N²) * 如果最高存在且不为1，则去除与这个项相乘的常数，如：2N² --> O(N²) #### 排序算法 常见排序算法：冒泡排序、选择排序、插入排序、归并排序、计数排序、基数排序、希尔排序、堆排序、桶排序 简单排序：冒泡排序、选择排序、插入排序 高级排序：希尔排序、快速排序 ##### 冒泡排序 * 对未排序的各个元素从头到尾一次比较相邻的两个元素大小 * 如果左边的元素大，则两个元素交换位置 * 向右移动一个位置，比较后面两个元素 * 当走到最右端时，最大的元素一定被放在了最右边 * 按照这个思路，从最左端重新开始，这次走到倒数第二个位置的元素即可 * 依次类推，就可以将数据排序完成 * 时间复杂度为O(N²) ##### 选择排序 选择排序改进了冒泡排序 * 将交换的次数有O(N²)减少到O(N) * 但是比较的次数依然是O(N²) 选择排序的思路 * 选定第一个索引位置，然后和后面元素依次比较 * 如果后面的元素，小于第一个索引位置的元素，则交换位置 * 经过一轮的比较后，可以确定第一个位置是最小的 * 然后使用同样的方法把剩下的元素逐个比较即可 * 可以看出选择排序，第一轮会选出最小值，第二轮会选出第二小的值，直到最后 [10, 23, 7, 76, 13, 4] var index = 0，10跟23比较10小index保持不变，依次往后比较，7小 index=2，在往后比较，4小 index=5，让4和10交换位置 [4, 23, 7, 76, 13, 10] ##### 插入排序 插入排序是学习高级排序的基础，比如希尔排序、快速排序，所以非常重要 局部有序： * 插入排序思想的核心是局部有序，什么是局部有序 * 在一个队列中，选择其中一个作为标记的对员 * 这个被标记的队员左边的所有队员已经是局部有序的 * 这意味着，有一部分人是按顺序排列好的，有一部分还没有顺序 插入排序思路 * 从第一个元素开始，该元素可以认为已经被排序 * 取出下一个元素，在已经排序的元素序列中从后向前扫描 * 如果该元素（已排序）大于新元素，将该元素移动到下一位置 * 重复上一个步骤，直到找到已排序的元素小于或者等于新元素的位置 * 将新元素插入到该位置后，重复上面的步骤 ##### 快速排序 快速排序最重要的思想是分而治之 比如，从需要排序的数字中选出任意的数字，将所有小于这个数字的数字放在左边，大于这个数字的数字放在右边 然后在左边选出任意的数字，将所有小于这个数字的数字放在左边，大于这个数字的数字放在右边；右边同样；递归处理 快速排序的思路 *