排序_快速排序
简述 快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。 快速排序是从冒泡排序演变而来的。 快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。 为什么快速排序比较快？ 因为它使用了分治法...
查找_二分查找
简述 也叫折半查找，性能优异。 但是所查找的数列必须是有序序列。 复杂度 时间复杂度 log2(N) 实现 非递归实现 递归实现 插值查找 二分查找每次都会计算出一个mid，然后拿这个mid的值去做比较 $$ mid = \frac{(low+high)}{2} $$ $$ mi...
动态规划_最长公共子序列
简述 最长公共子序列算法思想，令 X=< x1,x2,...xm > Y=<y1,y2,...yn> 为两个序列， Z=<z1,z2,...zk>为X和Y的某一个最长公共子序列： 如果 xm=yn，则zk=xm=yn,且Z(k-1)是X(m-1...
排序_冒泡排序
简述 冒泡排序通过反复遍历要排序的列表，比较每对相邻项，并以升序或降序的方式交换它们。重复操作列表，知道不需要交换为止。 复杂度 名称 最好 平均 最差 空间 稳定性 冒泡排序 n n2 n2 1 是 理解 冒泡排序，有n个数字，就要进行n次大循环 每次大循环，会找到所有数里面的...
搜索与图论模板
树与图的存储 树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。 树与图的遍历 拓扑排序 时间复杂度O(n+m),n表示点数，m表示边数 朴素dijkstra算法 时间复杂度O(n*n+...
狄克斯特拉算法
概述 狄克斯特拉算法（Dijkstra's Algorithm）是一种用于计算单源最短路径的算法，适用于非负权重的有向图和无向图 对于狄克斯特拉算法而言，图必须有权重才行 如果图是无权图（即所有边的权重都相同，可以视为权重为 1） 可以使用广度优先搜索（BFS）来找到最...
排序_归并排序
简述 归并排序思想，假设对数组A[p...r]排序： 分解 将数组A[p...r]平均划分为2子数组A[p...q-1]个A[q...r]，一直划分直到每个子数组只有1个元素 归并 对 A[p...q-1]和A[q...r]这两个已排序好的数组进行合并 复杂度 时间复杂度 O(n...
一些变量值交换的方法
第三个变量 实现 优点 简单易懂，逻辑清晰 缺点 需要额外的空间来存储临时变量 异或运算 实现 优点 不需要额外的空间 运算只使用基本的逻辑运算，适用于底层硬件编程 缺点 对大多数程序员来说，这种方法不如使用第三个变量的方式直观，容易引起误解 如果 a 和 b 是同一个变量，这种...
匹配_KMP模式匹配算法：二
预处理操作 参数 iterP_begin:模式序列P的起始迭代器 iterP_end:模式序列P的终止迭代器 解析 初始化 pai[1] = 0,k = 0 遍历(q从：2->m) 从2开始，因为Pk必须是Pm的真子集。 条件：k > 0 && p[k...
排序_基数排序
简述 基数排序思想，假设对数组A[p...r]排序，其中数组中所有元素都为正整数，并且不超过RADIXWITH位（有模板的RADIXWITH参数指定）： 首先对A中所有元素按照个位数大小进行排序（原地的） 再对A中所有元素按照个十数大小进行排序（原地的） 一直到最后按照A中所有元...
搜索当前标签