排序_桶排序
简述 桶排序需要创建若干个桶来协助排序。 所谓桶，每个桶bucket代表一个区间范围，里面可以承载一个或多个元素。 复杂度 名称 最好 平均 最差 空间 稳定性 桶排序 n+k n nlog(n) n 是 实现 算法导论 桶排序思想，假设对数组A[p...r]排序，首先将这些元素...
匹配_朴素字符串匹配算法
字符串匹配 字符串匹配的形式化定义如下：假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。 字符数组P和T通常称...
BFS和DFS
BFS 概述 广度优先搜索（Breadth-First Search，简称 BFS）是一种遍历或搜索图或树数据结构的算法 它从根节点开始，沿着树的宽度遍历节点（即先访问同一层级的所有节点，再访问下一层级的节点） 在图中，BFS 从起始节点开始，探索所有邻居，然后依次遍历每个邻居的...
数据结构_最小优先级队列
概述 优先级队列是一种用来维护由一组元素构成集合S的数据结构，其中每个元素都有一个相关的值，称之为关键字。一个最小优先级队列支持以下操作： insert(S,x):将元素x插入到集合S中 min(S)：返回S中具有最小关键字的元素 extract_min(S):去掉并返回S中具有...
排序_归并排序
简述 归并排序思想，假设对数组A[p...r]排序： 分解 将数组A[p...r]平均划分为2子数组A[p...q-1]个A[q...r]，一直划分直到每个子数组只有1个元素 归并 对 A[p...q-1]和A[q...r]这两个已排序好的数组进行合并 复杂度 时间复杂度 O(n...
排序_快速排序
简述 快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。 快速排序是从冒泡排序演变而来的。 快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。 为什么快速排序比较快？ 因为它使用了分治法...
排序_冒泡排序
简述 冒泡排序通过反复遍历要排序的列表，比较每对相邻项，并以升序或降序的方式交换它们。重复操作列表，知道不需要交换为止。 复杂度 名称 最好 平均 最差 空间 稳定性 冒泡排序 n n2 n2 1 是 理解 冒泡排序，有n个数字，就要进行n次大循环 每次大循环，会找到所有数里面的...
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述 堆排序算法步骤： 把无序数组构建成二叉堆。需要从小到大排序，就...
匹配_有限自动机字符串匹配算法
定义 假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。 字符数组P和T通常称为字符串。 原理 有限自动机 定义...
搜索当前标签