基数排序

【注】参考自教材「算法导论」。 1. 简介 基数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制。基数排序对排序关键字的最低数位到最高数位中的每一数位采用其他排序算法进行排序。基数排序时间复杂度可以达到 O(d(n+k))O(d(n+k))O(d(n+k))（这中情况下对每一数位采用的排序算法为计数排序）。其中，kkk 为待排序序列的排序关键字每一数位的最大范围，ddd

Technique ACM 算法 排序
Technique ACM 算法 排序

堆排序与优先队列

【注】参考自教材「算法导论」。 1. 堆 1.1 定义 （二叉）堆物理上是一个数组，逻辑上是一棵完全二叉树，树上的每一个结点对应数组中的一个元素。 设表示堆的数组 AAA，其包含两个属性： A.lengthA.lengthA.length 给出数组元素的个数。 A.heapsizeA.heapsizeA.heapsize 给出有多少个堆元素存储在该数组中。 1.2 性质 从根结点编号为 1

Technique ACM 算法 排序
Technique ACM 算法 排序 数据结构

计数排序

【注】参考自教材「算法导论」。 1. 简介 计数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制，可以达到 O(n+k)O(n+k)O(n+k) 。其中，kkk 为待排序序列的排序关键字的最大范围。 计数排序是稳定的、非原址的。 2. 思想 计数排序假设 nnn 个输入元素中的每一个的排序关键字都是在 0 到 kkk 区间（左闭右开）内的一个整数。对每一个输入元素 xx

Technique ACM 算法 排序
Technique ACM 算法 排序

树基础知识

【注】参考自教材「算法导论」。 1. 自由树 1.1 定义 自由树是一个连通的、无环的无向图，简称树。 【注】一个可能不连通的、无环的无向图称为森林。 1.2 概念 结点的度：自由树中节点的度和无向图中的一样，即相邻结点的个数。 1.3 性质 令 G=(V,E)G = (V,E)G=(V,E) 是一个无向图，则下面的描述是等价的： GGG 是自由树。 GGG 中任何两结点由唯一简单路径

Technique ACM 算法 图论 树
Technique ACM 算法 数据结构 图论 树

凸包算法

凸包类型的题算法主要有三种：JarvisMarch 算法、Graham 算法和 Andrew 算法，这三种算法时间性能上递增。 1. JarvisMarch 算法 1.1 思想 纵坐标最小然后横坐标最小的点一定是凸包上的点， 我们将其记为 p0{p_0}p0​，从 p0{p_0}p0​ 开始，按逆时针的方向，逐个找凸包上的点，每前进一步找到一个点，所以叫作步进法。 选取下一个点的方法： 假设已找

Technique ACM 算法
Technique ACM 算法