常见的数据结构有哪些？有哪些基本操作？常见的排序算法是如何实现的？各自的优点和缺点是什么？本文简单分享算法基础、常用数据结构、排序算法。给学生上一门数据结构和算法的基础课。1前言1为什么要研究算法和数据结构？解决具体问题。深度优化程序性能的基础。学习一个思想：如何将真实问题转化为计算机语言表示。2业务开发要掌握到什么程度？了解常见的数据结构和算法，沟通无障碍。学以致用：知道遇到问题要用什么数据结构和算法来优化。2数据结构基础1什么是数据结构？数据结构是数据的组织、管理和存储格式，其目的是高效地访问和修改数据。数据结构是算法的基石。如果把算法比作美丽而灵活的舞者，那么数据结构就是舞者脚下宽阔坚实的舞台。2物理结构和逻辑结构的区别？物理结构就像人的血肉之躯，看得见、摸得着、摸得着，比如数组、链表。逻辑结构就像人的思想和精神，是看不见摸不着的，如队列、栈、树、图等。3线性存储结构和非线性存储结构有什么区别？线性：元素之间是一对一的关系，比如栈和队列。非线性：每个元素可能连接到0个或多个元素，例如树和图。三算法基础1什么是算法？数学：算法是用于解决某些类型问题的公式和思想。计算机：旨在解决特定算术和逻辑问题的一系列编程指令。2如何衡量算法的好坏？时间复杂度：运行时间的长短。空间复杂度：占用内存的大小。3如何计算时间复杂度？大O表示法（渐近时间复杂度）：将程序的相对执行时间函数T(n)简化为一个数量级，可以是n、n^2、logN等。推导时间复杂度的几个原则：如果运行时间是常量级的，用常量1表示。仅保留时间函数中的最高阶项。如果存在最高阶项，则忽略最高阶项之前的系数。时间复杂度比较：O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)。不同时间复杂度算法运行时间比较：4如何计算空间复杂度？常数空间O(1)：存储空间的大小是固定的，与输入规模没有直接关系。线性空间O(n)：分配的空间是一个线性集合，集合大小与输入大小n成正比。二维空间O(n^2)：分配的空间是一个二维数组集合，集合的长宽与输入大小n成正比。递归空间O(logn)：递归是一种特殊的场景。虽然递归代码中没有显式声明变量或集合，但计算机在执行程序时，会专门分配一块内存空间来存放“方法调用栈”。执行递归操作所需的内存空间与递归的深度成正比。5如何定义算法稳定性？稳定性：如果a原本在b的前面，并且a=b，排序后a还是在b的前面。不稳定：如果a原本在b的前面，并且a=b，排序后a可能出现在b的后面。6常见的算法有哪些？首先必须明确：具体算法解决具体问题。字符串：Bruteforcematch、BM、KMP、Trie等搜索：二分搜索、遍历搜索等排序：冒泡排序、快速排序、计数排序、堆排序等搜索：TFIDF、PageRank等聚类分析:expectationmaximization,k-meanings,k-digits等深度学习：深度信念网络，深度卷积神经网络，生成对抗等异常检测：k-最近邻，局部异常因子等......其中、字符串、搜索、排序算法是最基本的算法。常见的四种数据结构1数组1）什么是数组？数据是由有限数量的相同类型的变量组成的有序集合。数组中的每个变量称为一个元素。2）数组的基本操作？读取O(1)，更新O(1)，插入O(n)，删除O(n)，扩容O(n)。2链表1）什么是链表？链表是一种物理上不连续、不连续的数据结构，由多个节点组成。单向链表的每个节点包含两部分，一部分是存储数据的变量data，另一部分是指向下一个节点的指针next。2）链表的基本操作？读取O(n)，更新O(1)，插入O(1)，删除O(1)。3）链表VS数组array：适用于读取多，插入删除少的场景。链表：适用于插入删除较多，读取较少的场景。3堆栈1）什么是堆栈？栈是一种线性逻辑数据结构，栈中的元素只能是后进先出的。存放最早元素的位置称为栈底，存放最后元素的位置称为栈顶。打个比方，堆栈是一端封闭的开口空心管，而队列是两端开口的空心管。2）如何实现栈？数组实现：链表实现：3）栈的基本操作，入栈O(1)，出栈O(1)。4）栈的应用？回溯历史，比如方法调用栈。页面面包屑。4队列1）什么是队列？它是线性逻辑数据结构，队列的元素只能后进后出。队列的出口端称为队头，队列的入口端称为队尾。2）如何实现队列？数组实现：链表实现：3）队列的基本操作？入队O(1)，出队O(1)。4）队列应用消息队列多线程等待队列网络爬虫URL队列爬5哈希表1）什么是哈希表？一种逻辑数据结构，提供键和值关系之间的映射。2）哈希表的基本操作？写：O(1)，读：O(1)，扩容O(n)。3）什么是散列函数？哈希表本质上是一个数组，但是数组只能根据下标访问，像a[0]a[1]a[2]a[3]，而哈希表的key主要是string类型。通过hash函数，我们可以将字符串或者其他类型的key转换成数组的下标索引。如果给出一个长度为8的数组，则：当key=001121,index=HashCode("001121")%Array.length=7当key=this,index=HashCode("this")%Array.length=64)什么是散列冲突？不同的key通过hash函数得到的下标可能相同。比如key002936对应的数组下标是2，002947对应的数组下标也是2，这种情况就是哈希冲突。5）如何解决哈希冲突？开放寻址方式：ExampleThreadlocal。链表法：例子Hashmap。6棵树1)什么是树？树是n(n≥0)个节点的有限集。当n=0时，称为空树。在任何非空树中，都具有以下特征：存在且只有一个称为根的特定节点。当n>1时，剩余节点可分为m(m>0)个互不相交的有限集，每个集本身就是一棵树，称为根的子树。2）树遍历？(1)深度优先前序：根节点、左子树、右子树。Inorder：左子树，根节点，右子树。后序：左子树、右子树、根节点。实现方式：递归或堆栈。(2)广度优先序列：逐层遍历。实现方式：队列。7二叉树1）什么是二叉树？二叉树是树的一种特殊形式。二叉树，顾名思义，这棵树的每个节点最多有2个子节点。注意最多有2个，或者只有1个，或者没有子节点。2）什么是满二叉树？二叉树的所有非叶子节点都有左孩子和右孩子，并且所有叶子节点都在同一层上，则该树是一棵满二叉树。3）什么是完全二叉树？对于具有n个节点的二叉树，按层次顺序编号，所有节点都从1到n编号。如果这棵树的所有节点都与同深度的满二叉树中编号为1到n的节点位置相同，那么这棵二叉树就是一棵完全二叉树。8二叉搜索树1）什么是二叉搜索树？二叉搜索树在二叉树的基础上增加了如下条件：如果左子树不为空，则左子树上所有节点的值都小于根节点的值。如果右子树不为空，则右子树上所有节点的值都大于根节点的值。左右子树也是二叉搜索树。2）二叉搜索树的作用是什么？搜索==》二分查找。排序==》中序遍历。3）二叉树的实现？链表。数组：对于稀疏二叉树，数组表示非常浪费空间。9二叉堆1）什么是二叉堆？二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆两种。最大堆的任一父节点的值都大于或等于其左右子节点的值。最小堆的任一父节点的值都小于或等于其左右子节点的值。2）二叉堆的基本操作？(1)插入：最后插入，节点向上浮动。(2)删除：删除头节点，将尾节点放在头中，然后下沉。（3）搭建二叉堆：二叉树==》二叉堆，所有非叶子节点依次下沉。3）二叉堆如何实现？数组：五种常见排序算法1十大经典排序算法2冒泡排序1)算法描述冒泡排序是一种简单的排序算法，它迭代遍历待排序数组，一次比较两个元素，如果顺序错误则交换它们。重复访问序列的工作，直到没有需要交换，也就是说序列已经排好了序，这个算法的名字来源于较小的元素会通过交换慢慢“浮”到序列的顶端。2）实现步骤比较相邻元素。如果第一个比第二个大，就交换它们。对每一对相邻的元素做同样的事情，从开始的第一对到最后的最后一对，所以最后的元素应该是最大的数。对所有重复以上步骤除了最后一个元素。重复步骤1~3直到排序完成。3）优点和缺点优点：易于实施和理解。缺点：时间复杂度为O(n^2)，元素排序效率比较低。4）适用范围数据基本有序，数据量较小的场景。5）场景优化（1）排序后继续冒泡的问题。这一轮排序，如果没有交换元素，则isSorted为true，直接跳出大循环，避免后续无意义的重复。(2)部分已经有序，但下一轮仍要遍历记录有序数据和无序数据的边界，有序部分下一轮不需要遍历。(3)只有一个元素是错误的，但需要经过多轮排序Cocktailsorting：元素的比较和交换是双向的，就像摇鸡尾酒一样。3归并排序1)算法描述归并排序是一种基于归并操作的有效排序算法。该算法是分治法的一个非常典型的应用。递归地将当前序列一分为二（split），在保持元素顺序不变的情况下，对上一步得到的子序列进行整合（merge），最终形成有序序列。2）实现步骤图源：https://www.cnblogs.com/chengxiao/p/6194356.html将长度为n的输入序列分成两个长度为n/2的子序列。分别对两个子序列使用归并排序。将两个已排序的子序列合并为最终的已排序序列。3）优缺点优点：性能好且稳定，时间复杂度为O(nlogn)。排序稳定，适用场景更多。缺点：非原地排序，空间复杂度高。4）适用于数据量大，预计需要稳定排序的场景。4快速??排序1)算法描述快速排序采用分而治之的策略，将一个序列划分为更小和更大的子序列，然后对两个子序列进行递归排序，实现整个序列的最终排序。2)实现步骤从序列中挑出一个元素，称为“pivot”。重新排序序列，所有小于参考值的元素都放在参考值的前面，所有大于参考值的元素都放在参考值的后面（相同的数字可以去任何一边）。此分区退出后，基准测试位于序列的中间。这称为分区操作。对【小于参考值的元素子数组】和【大于参考值的元素子数组】进行递归排序。3）优缺点优点：性能较好，时间复杂度最佳O(nlogn)，大部分场景性能接近最优。就地排序，时间复杂度优于归并排序。缺点：在某些场景下，最差的排序性能是O(n^2)。排序不稳定。4）适用于数据量大，不需要稳定排序的场景。5）场景优化（1）为每个参考元素选择最大或最小的元素随机选择参考元素而不是第一个元素。以三数为中法，随机抽取三数，以中数为参考元素。(2)序列包含大量大于、小于或等于参考值的重复数据。(3)快速排序的性能优化双轴快速排序：2个参考号，例子：Arrays.sort()。5堆排序1）算法描述堆排序（Heapsort）是指利用堆的数据结构设计的一种排序算法。堆叠是一种近似完全二叉树的结构，同时满足堆叠的性质：即子节点的键值或索引总是小于（或大于）其父节点。2）实现步骤将初始的待排序关键词序列（R1，R2....Rn）构建成一个最大堆，即初始无序区。将顶层元素R[1]与末尾元素R[n]交换，得到一个新的无序区域(R1,R2,...Rn-1)和一个新的有序区域(Rn)，并满足R[1,2...n-1]<=R[n]。由于交换后的新堆顶R[1]可能违反堆的性质，需要将当前无序区（R1,R2,...Rn-1）调整为新堆，然后合并R[1]再次与无序区域的最后一个元素交换，得到一个新的无序区域（R1，R2....Rn-2）和一个新的有序区域（Rn-1，Rn）。重复这个过程，直到有序区的元素个数为n-1，整个排序过程就完成了。3）优缺点优点：性能较好，时间复杂度为O(nlogn)。时间复杂度比较稳定。辅助空间复杂度为O(1)。缺点：在数据变化的情况下，堆的维护成本比较高。4）适用范围为数据量大，数据以流式方式输入的场景。5）为什么在实际情况下快速排序比堆排序快？堆排序的过程表明，最大堆建立后，堆顶的元素会和最后一个元素交换，然后最后一个元素会从堆顶下沉到合适的位置，因为堆顶的元素bottom一定比较小，下沉过程中会进行大量几乎无效的比较。因此，虽然堆排序的复杂度和快速排序一样，都是O(NlogN)，但是堆排序复杂度的常数系数更大。6计数排序1)算法描述计数排序不是一种基于比较的排序算法，其核心是将输入的数据值转换成一个key，存储在附加的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入数据必须是一定范围内的整数。2）实现步骤找到待排序数组中最大的元素。构造一个长度为最大元素值+1的数组C。遍历无序随机数序列，每个整数按其值入座，对应数组下标的值加1。遍历数组C，输出下标数组元素的值，多次输出元素的值。3）优缺点优点：性能比较完美的排序，时间复杂度为O(n+k)，k为序列的最大值。稳定排序。缺点：适用范围比较窄。4）适用范围序列的元素都是整数，适用于k不是很大，序列比较集中的情况。5）场景优化（1）数字不是从0开始，会存在浪费空间的问题。序列的最小值作为偏移量，序列的最大值-最小值+1作为统计数组的长度。7桶排序1)算法描述桶排序是计数排序的升级版。它利用了函数的映射关系，而高效的关键就在于这个映射函数的确定。实现原理：假设输入数据服从均匀分布，将数据分成有限个桶，对每个桶分别进行排序（可以使用其他排序算法，也可以递归继续使用桶排序进行排序）。2）实现步骤创建桶，区间跨度=（最大值-最小值）/（桶数-1）。遍历序列并检查数字。在每个桶中排序，可以选择快速排序等。遍历所有桶，输出所有元素。3）优缺点优点：最优时间复杂度为O(n)，比较排序算法耗尽。缺点：适用范围比较窄。时间复杂度不稳定。4）适用范围数据服从均匀分布的场景。8性能比较随机生成一个0到K之间的序列，共有N个数，使用各种算法进行排序，记录排序所需要的时间。参考内容及图片来源[1]《漫画算法：小灰的算法之旅》[2]《算法(第4版)》[3]《算法图解》[4]《剑指Offer》[5]十大经典排序算法（动图演示）https://www.cnblogs.com/onepixel/p/7674659.html[6]维基百科https://zh.wikipedia.org/wiki/Wikipedia:%E9%A6%96%E9%A1%B5
