排序_桶排序
简述 桶排序需要创建若干个桶来协助排序。 所谓桶，每个桶bucket代表一个区间范围，里面可以承载一个或多个元素。 复杂度 名称 最好 平均 最差 空间 稳定性 桶排序 n+k n nlog(n) n 是 实现 算法导论 桶排序思想，假设对数组A[p...r]排序，首先将这些元素...
算法特点、哈希表
基于算法思想 比较排序 冒泡排序（Bubble Sort）： 反复交换相邻的逆序元素 快速排序（Quick Sort）： 通过分区交换来排序，递归地对分区进行排序 堆排序（Heap Sort）： 利用堆结构进行排序，构建最大堆，然后依次将最大元素移到数组末尾 归并排序（Merge...
匹配_朴素字符串匹配算法
字符串匹配 字符串匹配的形式化定义如下：假设文本是一个长度为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 从起始节点开始，探索所有邻居，然后依次遍历每个邻居的...
匹配_有限自动机字符串匹配算法
定义 假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,...z}。 字符数组P和T通常称为字符串。 原理 有限自动机 定义...
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述 堆排序算法步骤： 把无序数组构建成二叉堆。需要从小到大排序，就...
狄克斯特拉算法
概述 狄克斯特拉算法（Dijkstra's Algorithm）是一种用于计算单源最短路径的算法，适用于非负权重的有向图和无向图 对于狄克斯特拉算法而言，图必须有权重才行 如果图是无权图（即所有边的权重都相同，可以视为权重为 1） 可以使用广度优先搜索（BFS）来找到最...
数据结构_最小优先级队列
概述 优先级队列是一种用来维护由一组元素构成集合S的数据结构，其中每个元素都有一个相关的值，称之为关键字。一个最小优先级队列支持以下操作： insert(S,x):将元素x插入到集合S中 min(S)：返回S中具有最小关键字的元素 extract_min(S):去掉并返回S中具有...
排序_快速排序
简述 快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。 快速排序是从冒泡排序演变而来的。 快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。 为什么快速排序比较快？ 因为它使用了分治法...
搜索当前标签