SelectionSort(A[0..n-1]): // 选择排序排序数组 // 输入：可排序数组A[0..n-1] // 输出：升序排序数组A[0..n-1] for i = 0 to n-1 do min = i for j = i to n-1 do if A[j] < A[min] min = j swap A[i] and A[min]
BubbleSort(A[0..n-1]): // 冒泡排序排序数组 // 输入：可排序数组A[0..n-1] // 输出：升序排序数组A[0..n-1] for i = 0 to n-2 do for j = 0 to n-2-i do if A[j+i] < A[j] swap A[j] and A[j+1]
InsertionSort(A[0..n-1]) // 用插入排序对给定数组排序 // 输入：n个可排序元素构成数组 // 输出：非降序排序数组 for i = 1 to n-1 do v = A[i] j = i - 1 while j >= 0and A[j] > v do A[j+1] = A[j] j = j - 1 A[j+1] = v // 上一步比较元素已经赋值给其后，所以应该覆盖其值
ShellSort(A[0..n-1]) // 用插入排序对给定数组排序 // 输入：n个可排序元素构成数组 // 输出：非降序排序数组 h = 1 while h < n/3 h = h*3 + 1 // 获取初始h值，之后每轮h变为1/3 while h >= 1: for i = h to n-1: v = A[i] j = i - h while j >= 0and A[j] > v do A[j] = A[j-h] j = j - h A[j+h] = v h = h/3
特点
Shell排序全衡量子数组规模、有序性，更加高效
h递增序列
子数组部分有序程度取决于h递增序列的选择
不同的h递增序列对算法效率有常数倍的变动，但是在实际
应用中效果不明显
Shell排序是唯一无法准确描述其对于乱序数组性能特征的排序
方法
减常量法
归并排序
Mergesort
将需要排序的数组A[0..n-1]均分的
对两个子数组递归排序，然后把排序后的子数组合并为有序
数组
1 2 3 4 5 6 7 8 9 10
Mergesort(A[0..n-1]): // 递归调用MergeSort对数组排序 // 输入：可排序数组A[0..n-1] // 输出：非降序排列数组A[0..n-1] if n > 1: copy A[0..floor(n/2)-1] to B[0..floor(n/2)-1] copy A[floor(n/2)..n-1] to C[0..ceiling(n/2)-1] Mergesort(B[0..floor(n/2)-1]) Mergesort(C[0..ceiling(n/2)-11]) Merge(B, C, A)
Merge
初始两只指针指向待合并数组首个元素
比较两个元素大小，将较小元素添加到新数组中，被复制元素
的数组指针右移
重复直到某一数组处理完毕，将未处理完数组复制到新数组尾部
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Merge(B[0..p-1], C[0..q-1], A[0..p+q-1]): // 将两个有序数组合并为新的有序数组 // 输入：有序数组B[0..p-1]、C[0..q-1] // 输出：存放有B、C中元素的有序数组A[0..p+q-1] while i < p and j < q: if B[i] <= C[j] A[k] = B[i] i = i + 1 else: A[k] = C[j] j = j + 1 k = k + 1 if i == p: copy C[j..q-1] to A[k..p+q-1] else: copy B[i..p-1] to A[k..p+q-1]
ComparisonCountingSort(A[0..n-1]) // 用比较计数法排序 // 输入：可排序数组A[0..n-1] // 输出：将A中可排序数组按照升序排列数组 for i = 0 to n-1 do count[i] = 0 for i = 0 to n-2 do for j = i+1 to n-1 do if A[i] < A[j] count[j] += 1 else count[i] += 1 for i = 0 to n-1 do S[count[i]] = A[i]
特点
算法效率
算法比较次数为$n(n-1)/2$
占用了线性数量的额外空间
算法使得键值的可能移动次数最小化，能够直接将键值放在在
有序数组最终位置
输入增强
分布计数排序
待排序元素来自于某个已知小集合$[l..u]$
算法
扫描列表，计算、存储列表中元素出现频率于数组$F[l..u]$中
再次扫描列表，根据值填入相应位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
DistributionCountingSort(A[0..n-1], l, u): // 分布计数法排序，对元素来自有限范围整数的数组排序 // 输入：数组[0..n-1]，数组中整数位于l、u间 // 输出：A中元素构成非降序数组S[0..n-1] for j = 0 to u-l do D[j] = 0 for i = 0 to n=1 do D[A[i]-l] += 1 for j = 1 to u-l do D[j] += D[j-1] // 存储各元素最后出现索引+1 for i = n-1 downto 0 do j = A[i] - l S[D[j]-1] = A[i] D[j] -= 1 // 更新应该存储的位置，类似于压栈 return S
特点
算法效率
如果元素值范围固定，效率为线性（不是基于比较的排序，
$nlogn$没有限制）
用空间换时间，其实可以看作是hash
利用了输入列表独特自然属性
变治法（输入增强）
应用
判断线性表元素是否唯一
寻找线性表众数
快速查找
线性表顺序统计量
寻找列表中第k小的元素
也即：求出给定列表中k个最小元素问题
采用partitioning的思路，需要将给定列表根据某个值先行划分
Lumuto划分算法
QuickSelect算法
算法
对划分完后出数组，s为分割位置
若：s == k-1，则中轴p就是第k小元素
若：s < k-1，则应该是数组右边划分第k-s小元素
若：s > k-1，则应该是数组左边划分第k小元素
这样就得到规模更小的问题实例
1 2 3 4 5 6 7 8 9 10 11
QuickSelect(A[l..r], k) // 用基于划分递归算法解决选择问题 // 输入：可排序数组A[0..n-1]的子数组A[l..r]、整数k // 输出：A[l..r]中第k小元素 s = Partition(A[l..r]) if s = l+k-1 return A[s] elif s > l+k-1 QuickSelect(A[l..s-1], k) else QuickSelect(A[s+1..r], l+k-1-s)
LomutoPartition(A[l..r]) // 采用Lomuto算法，用首个元素作中轴划分数组 // 输入：可排序数组A[0..n-1]的子数组A[l..r] // 输出：A[l..r]的划分、中轴位置 p = A[l] s = l for i = l+1 to r if A[i] < p s = s+1 swap(A[s], A[i]) swap(A[l], A[s]) return s
count = 0 // 全局变量：访问次序（次数） DFS(G) // 对给定图的深度优先查找遍历 // 输入：图G=<V, E> // 输出：图G顶点按照DFS遍历第一次访问到的先后次序， // 未访问到标记未0 for each vertex v in V do if v is marked with 0 dfs(v) dfs(v) // 递归访问所有和v相连接的未访问顶点，赋予count值 count = count+1 mark v with count for each vertex w in V adjecnt to v do if w is marked with 0 dfs(w)
count = 0 // 全局变量：访问次序（次数） BFS(G) // 给定图广度优先查找变量 // 输入：图G=<V, E> // 输出：图G的顶点按照被BFS遍历第一次访问到次序， // 未访问顶点标记未0 for each vertax v in V do if v is marked with 0 bfs(v) bfs(v) // 访问所有和v相连接的顶点，赋count值 count = count+1 whilte queue is not empty do for each vertex w in V adjcent to the front vertex do if w is marked with 0 count = count+1 mark w with count add w to the queue remove the front vertex from the queue
S = initStack() DFN[MAX_VERTAX], Low[MAX_VERTEX] index = 0 QList = InitList(Queue())
tarjan(u, E): // 比较DFS搜索次序、回边到达次序判断强连通分量 // 输入：结点u，边集合E // 输出：强连通分量队列列表 DFN[u] = Low[u] = ++ index S.push(u) for each (u, v) in E: if (v is not visited): tarjan(v) Low[u] = min(Low[u], Low[v]) // 使用v找到的前驱更新u能找到前驱，递归更新 elseif (v in S): // 判断边是否为回边 Low[u] = min(Low[u], DFN[v]) // Low[u] = min(Low[u], Low[v]) // 应该也行 if(DFN[u] == Low[u]): Q = QList.next() repeat v = S.pop() Q.push(v) until (u == v)
Warshall(A[1..n, 1..n]) // 计算传递闭包的Warshall算法 // 输入：A[1..n, 1..n]包含n个顶点的有向图的邻接矩阵 // 输出：A的传递闭包 R^0 = A for i = 1 to n do for i = 1 to n do for j = 1 to n do if R^(k-1)[i, j] == 1or (R^(k-1)[i, k] == 0and R^(k-1)[k, j] == 0) R^k[i, j] = 1 return R^n
Dijkstra(G, s) // 单起点最短路径Dijkstra算法 // 输入：G=<V, E>非负权重加权连通图，顶点s起始点 // 输出：对V中每个顶点，从s到v的最短路径长度d_v Initialize(Q) // 将顶点优先队列初始化为空 for v in V d_v = \infty p_v = NULL Insert(Q, s, d_s) // 初始化有限队列中顶点优先级 d_s = 0 Decrease(Q, s, d_s) // 更新s优先级为d_s V_T = NULL
for i = 0 to |V|-1do u* = DeleteMin(Q) // 删除优先级最小元素 V_T = V_T \union {u*} for v in V-V_T 中与u*邻接顶点 do if d_u* + w(u*, u) < d_u d_u = d_u* + w(u*, u) p_u = u* Decrease(Q, u, d_u)
Floyd(W[1..n, 1..n]) // 计算完全最短路径的Floyd算法 // 输入：W不包含负距离的距离矩阵 // 输出：包含最短距离的距离矩阵 D^0 = W for k = 1 to n do for i = 1 to n do for j = 1 to n do D[i, j] = min(D[i, j], D[i, k] + D[k, j]) return D
MaximumBipartiteMatching(G) // 用类似广度优先算法遍历求二分图的一个最大匹配 // 输入：二分图G=<V, U, E> // 输出：输入图中一个最大基数匹配 初始边集合M包含某些合法的匹配（例如空集合） 初始队列Q包含V的所有自由顶点（任意序） whilenotEmpty(Q)do w = Front(Q) Dequeue(Q) if w \in V for 邻接w的每个顶点u do // 二分图性质保证u一定在U中 if u是自由顶点 // 增益 M = M \union (w, u) // 首边进匹配 v = w while v已经被标记 do // 从增益路径回溯生成匹配 u = 以v标记的点 M -= (v, u) // 偶数边出匹配 v = 以u标记的点 M += (v, u) // 奇数边进匹配 删除所以顶点标记 用V中所有自由顶点重新初始化Q break // 增益后，重新搜索 else // u已经匹配 if (w, u) not \in M and u未标记 用w标记u Enqueue(Q, u) else // w \in U，此时w必然已经匹配 用w标记w的对偶v // 将已有匹配添加进增益路径中 Enqueue(Q, v) return M // 当前匹配已经是最大匹配
TopologicalSort(G): // 从有向图中不断删除入度为0的点、入栈，判断有向图G是否 // 为DAG，并给出拓扑排序栈 // 输入：有向图G // 输出：拓扑排序栈T InitStack(S) indgree = [v.indegree for v in G] for v in G: if v.indgree == 0 S.push(v) // 存储0入度结点栈 count = 0 // 删除结点计数 while(!S.empty()) v = S.pop() T.push(v) count++ for(u connected to v) if --indgree.u == 0 S.push(u) if count < |G.V| // 结点未删除完毕，但无0入度结点 // G中有回路，报错 return ERROR return T
TopologicalOrder(G): // 从有向图中不断删除入度为0的点、入栈，判断有向图G是否 // 为DAG，并给出拓扑排序栈 // 输入：有向图G // 输出：拓扑排序栈T、顶点事件最早发生事件ve InitStack(S) indgree = [v.indegree for v in G] ve[0..|G.V|] = 0 for v in G: if v.indgree == 0 S.push(v) // 存储0入度结点栈 count = 0 // 删除结点计数 while(!S.empty()) v = S.pop() T.push(v) count++ for(u connected by v) ve[u] = max{ve[u], ve[v] + len(v, u)} // 若有更长路径，更新 if --indgree[u] == 0 S.push(u) if count < |G.V| // 结点未删除完毕，但无0入度结点 // G中有回路，报错 return ERROR return T, ve
CriticalPath(G, T, ve): // 逆序求顶点事件最晚发生时间，求出关键活动 // 输入：有向无环图G，G拓扑排序 // 输出：关键活动队列Q vl[0..|G.V|] = ve Q = InitQueue() while(!T.empty()) v = T.pop() for (u connect to v) vl[u] = min{vl[u], vl[v] - len(u, v)} for(v in G.V) for (u connected by v) ee = ve[v] el = vl[u] - len(v) if(el == ee) Q.push(G.edge(v, u)) return Q
