基础排序算法
【注】参考自教材「算法导论」。
1. 插入排序
1.1 简介
插入排序是稳定的、原址的排序算法，其时间复杂度为 O(n2)O(n^2)O(n2) 。
1.2 伪代码
1234567891011InsertionSort(A) { for j = 2 to A.length key = A[j] // 将 A[j] 插入到有序数组 A[1..j-1] 中 i = j - 1 // 将大于 A[j] 的元素后移 while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i+1] = key}
2. 选择排序
2.1 简介
选择排序是不稳定的、原址的排序算法，其时间复杂度为 O(n2)O(n^2)O(n2) 。选择排序不稳定的原因在于其在将找到的最小元素交换到有序序列尾部时改变了原来尾部元素与其他元素的相对位置。
2.2 伪代码
12345678910SelectSort(A ...
排序算法概述
1. 概念
1.1 原址
如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外，则成排序算法是原址的。
1.2 稳定
在输入数组中，存在多个具有相同的关键字的元素，若经过排序，这些元素的相对次序保持不变，则称这种排序算法是稳定的，否则称为不稳定的。
2. 算法
2.1 比较排序
排序方法
平均时间复杂度
最坏时间复杂度
最好时间复杂度
空间复杂度
稳定性
插入排序
O(n2)O(n^2)O(n2)
O(n2)O(n^2)O(n2)
O(n)O(n)O(n)
O(1)O(1)O(1)
稳定
选择排序
O(n2)O(n^2)O(n2)
O(n2)O(n^2)O(n2)
O(n2)O(n^2)O(n2)
O(1)O(1)O(1)
不稳定
冒泡排序
O(n2)O(n^2)O(n2)
O(n2)O(n^2)O(n2)
O(n)O(n)O(n)
O(1)O(1)O(1)
稳定
希尔排序
O(n1.3)O(n^{1.3})O(n1.3)
O(n2)O(n^2)O(n2)
O(n)O(n)O(n)
O(1)O(1)O(1)
不稳定
快速排序
O(nlog2n)O( ...
PAT「1005 Programming Pattern (35分)」
1. 题目
题目链接：PAT「1005 Programming Pattern (35分)」 。
Description
Programmers often have a preference among program constructs. For example, some may prefer if(0==a), while others may prefer if(!a). Analyzing such patterns can help to narrow down a programmer’s identity, which is useful for detecting plagiarism.
Now given some text sampled from someone’s program, can you find the person’s most commonly used pattern of a specific length?
Input Specification:
Each input file contains one test case. For ...
术语
GP：Generic Programming
OO：Object Oriented
STL：Standard Template Library
基数排序
【注】参考自教材「算法导论」。
1. 简介
基数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制。基数排序对排序关键字的最低数位到最高数位中的每一数位采用其他排序算法进行排序。基数排序时间复杂度可以达到 O(d(n+k))O(d(n+k))O(d(n+k))（这中情况下对每一数位采用的排序算法为计数排序）。其中，kkk 为待排序序列的排序关键字每一数位的最大范围，ddd 是排序关键字的数位数目。
计数排序要求每一数位排序所使用的排序算法都是稳定的，否则将影响计数排序的正确性。基数排序是稳定的，其原址性取决于对每一数位所使用的排序算法的原址性。
2. 思想
类比于多关键字元素序列的排序思想，先比较第一关键字，再比较第二关键字、…… ，这样的排序思想属于自顶向下的思想，即先根据第一关键字排序后将序列分割为小的子序列，然后再根据第二关键字排序……，以此类推。这样做有一个不利之处在于对每个关键字排序需要限定区间，根据第一关键字排序的区间为整个区间，根据第二关键字排序的区间限定为第一关键字相同的区间，以此类推。
然而本质上不同子序列区间对第 iii 个关键字排 ...
堆排序与优先队列
【注】参考自教材「算法导论」。
1. 堆
1.1 定义
（二叉）堆物理上是一个数组，逻辑上是一棵完全二叉树，树上的每一个结点对应数组中的一个元素。
设表示堆的数组 AAA，其包含两个属性：
A.lengthA.lengthA.length 给出数组元素的个数。
A.heapsizeA.heapsizeA.heapsize 给出有多少个堆元素存储在该数组中。
1.2 性质
从根结点编号为 1 开始，同一深度的结点自左往右、不同深度的结点自上往下，对堆上的结点编号（即逐层从左往右进行编号），结点编号对应数组 AAA 中元素的下标。
nnn 个元素的堆的高度为 ⌊lgn⌋\lfloor \lg n \rfloor⌊lgn⌋ 。
证明
因为堆是一棵完全二叉树，设堆高为 hhh，则
2h≤n≤2h+1−1⇒lg(n+1)−1≤h≤lgn⇒lgn−1<lg(n+1)−1≤h≤lgn\begin{array}{c}
2^h \leq n \leq 2^{h+1} - 1 \Rightarrow \lg (n+1) - 1 \leq h \leq \lg n \\
...
计数排序
【注】参考自教材「算法导论」。
1. 简介
计数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制，可以达到 O(n+k)O(n+k)O(n+k) 。其中，kkk 为待排序序列的排序关键字的最大范围。
计数排序是稳定的、非原址的。
2. 思想
计数排序假设 nnn 个输入元素中的每一个的排序关键字都是在 0 到 kkk 区间（左闭右开）内的一个整数。对每一个输入元素 xxx ，确定小于 xxx 的元素个数，然后利用元素个数直接将序列按顺序排好放到输出序列中。
3. 实现
3.1 伪代码
12345678910111213141516171819CountingSort(A, Key, k) { // 定义新数组 B & C define B[0..A.length] define C[0..k] // 初始化数组 C for i = 0 to k C[i] = 0 // 统计每个关键字的元素数量 for j = 1 to A.length C[Key[j]] = C[K ...
树基础知识
【注】参考自教材「算法导论」。
1. 自由树
1.1 定义
自由树是一个连通的、无环的无向图，简称树。
【注】一个可能不连通的、无环的无向图称为森林。
1.2 概念
结点的度：自由树中节点的度和无向图中的一样，即相邻结点的个数。
1.3 性质
令 G=(V,E)G = (V,E)G=(V,E) 是一个无向图，则下面的描述是等价的：
GGG 是自由树。
GGG 中任何两结点由唯一简单路径相连。
GGG 是连通的，但是从图中移除任意一条边得到的图均不连通。
GGG 是连通的，且 ∣E∣=∣V∣−1|E| = |V| - 1∣E∣=∣V∣−1 。
GGG 是无环的，且 ∣E∣=∣V∣−1|E| = |V| - 1∣E∣=∣V∣−1 。
GGG 是无环的，但是如果向 EEE 中添加任何一条边，均会造成图包含一个环。
2. 有根树 & 有/无序树
2.1 定义
有根树 是一个自由树，其结点中存在根结点（简称根）。
有序树 是一棵有根树，其中每个结点的孩子是有序的（即树中某结点的孩子之间的左右位置关系是有影响的）。
2.2 概念
祖先 & 后代：考虑以 ...
PAT「1004 To Buy or Not to Buy - Hard Version (35分)」
1. 题目
题目链接：PAT「1004 To Buy or Not to Buy - Hard Version (35分)」 。
Description
Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence in some cases Eva might have to buy several strings to get all the beads she needs. With a hundred strings in the shop, Eva needs your help to tell her whether or not she can get all the ...
STL用法详解
1. 简介
STL 提供了大约 100100100 个实现算法的模版函数，基本都包含在 <algorithm> 库之中，还有一部分包含在 <numeric> 和 <functional> 中。完备的函数列表参见「参考手册」。
2. 常用函数
find(InputIterator first, InputIterator last, const T& val)：顺序查找 [first, last) 中第一个等于 val 值对应的 Iterator。如果没找到 val 值，则返回 Iterator last。
reverse(BidirectionalIterator first, BidirectionalIterator last)：翻转 [first, last) 中的元素。
unique(ForwardIterator first, ForwardIterator last)：去除容器中相邻的重复元素，返回值为指向去重后容器结尾的迭代器，原容器大小不变。unique 函数直接采用覆盖方法去重，故去重后容器的结尾后的元素并不是剩 ...
凸包算法
凸包类型的题算法主要有三种：JarvisMarch 算法、Graham 算法和 Andrew 算法，这三种算法时间性能上递增。
1. JarvisMarch 算法
1.1 思想
纵坐标最小然后横坐标最小的点一定是凸包上的点， 我们将其记为 p0{p_0}p0，从 p0{p_0}p0 开始，按逆时针的方向，逐个找凸包上的点，每前进一步找到一个点，所以叫作步进法。
选取下一个点的方法：
假设已找到 p0{p_0}p0、p1{p_1}p1，则利用跟 p0p1{p_0p_1}p0p1 向量夹角最小的点作为 p2{p_2}p2。（p1{p_1}p1 则利用 p0p1{p_0p_1}p0p1向量和水平线的夹角）
1.2 代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 ...
LCS、LIS、LICS算法
概念
首先，要理解子串和子序列的含义：
子串：来源于原序列连续的一段。
子序列：来源于原序列中元素相对顺序不变的一段，不要求元素连续。
1. LCS\mathrm{LCS}LCS（最长公共子序列）
1.1 转移方程
给定两个序列 AAA、BBB，设 C[i,j]C[i, j]C[i,j] 为 LCS(Ai,Bj)\mathrm{LCS}(A_i, B_j)LCS(Ai,Bj) 的长度，其中 AiA_iAi、BjB_jBj 分别表示 AAA 从首元素到第 iii 个元素的一段、BBB 从首元素到第 jjj 个元素的一段, aia_iai、bib_ibi 分别表示 AAA 中第 iii 个元素、BBB 中第 jjj 个元素，序列 AAA 和 BBB 的长度分别为 nnn 和 mmm。则 LCS\mathrm{LCS}LCS 的状态转移方程为：
C[i,j]=0(i=0∨j=0)C[i, j] = 0 \quad (i = 0 \vee j = 0 )C[i,j]=0(i=0∨j=0)
C[i,j]=C[i−1,j−1]+1(i,j>0∧ai=bj)C[i, j] = ...
