基础排序算法 【注】参考自教材「算法导论」。 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] 中 2020-08-22 Technique ACM 算法 排序 Technique ACM 算法 排序
基础排序算法 【注】参考自教材「算法导论」。 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] 中 2020-08-22 Technique ACM 算法 排序 Technique ACM 算法 排序
排序算法概述 1. 概念 1.1 原址 如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外，则成排序算法是原址的。 1.2 稳定 在输入数组中，存在多个具有相同的关键字的元素，若经过排序，这些元素的相对次序保持不变，则称这种排序算法是稳定的，否则称为不稳定的。 2. 算法 2.1 比较排序 排序方法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 插入排序 O(n2)O 2020-08-21 Technique ACM 算法 排序 Technique ACM 算法 排序
排序算法概述 1. 概念 1.1 原址 如果输入数组中仅有常数个元素需要在排序过程中存储在数组之外，则成排序算法是原址的。 1.2 稳定 在输入数组中，存在多个具有相同的关键字的元素，若经过排序，这些元素的相对次序保持不变，则称这种排序算法是稳定的，否则称为不稳定的。 2. 算法 2.1 比较排序 排序方法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性 插入排序 O(n2)O 2020-08-21 Technique ACM 算法 排序 Technique ACM 算法 排序
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). Analyz 2020-08-20 Technique ACM 题解 Technique ACM 题解
术语 GP：Generic Programming OO：Object Oriented STL：Standard Template Library 2020-08-19 Technique C++ Technique C++
基数排序 【注】参考自教材「算法导论」。 1. 简介 基数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制。基数排序对排序关键字的最低数位到最高数位中的每一数位采用其他排序算法进行排序。基数排序时间复杂度可以达到 O(d(n+k))O(d(n+k))O(d(n+k))（这中情况下对每一数位采用的排序算法为计数排序）。其中，kkk 为待排序序列的排序关键字每一数位的最大范围，ddd 2020-08-18 Technique ACM 算法 排序 Technique ACM 算法 排序
堆排序与优先队列 【注】参考自教材「算法导论」。 1. 堆 1.1 定义 （二叉）堆物理上是一个数组，逻辑上是一棵完全二叉树，树上的每一个结点对应数组中的一个元素。 设表示堆的数组 AAA，其包含两个属性： A.lengthA.lengthA.length 给出数组元素的个数。 A.heapsizeA.heapsizeA.heapsize 给出有多少个堆元素存储在该数组中。 1.2 性质 从根结点编号为 1 2020-08-18 Technique ACM 算法 排序 Technique ACM 算法 排序 数据结构
计数排序 【注】参考自教材「算法导论」。 1. 简介 计数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制，可以达到 O(n+k)O(n+k)O(n+k) 。其中，kkk 为待排序序列的排序关键字的最大范围。 计数排序是稳定的、非原址的。 2. 思想 计数排序假设 nnn 个输入元素中的每一个的排序关键字都是在 0 到 kkk 区间（左闭右开）内的一个整数。对每一个输入元素 xx 2020-08-18 Technique ACM 算法 排序 Technique ACM 算法 排序
树基础知识 【注】参考自教材「算法导论」。 1. 自由树 1.1 定义 自由树是一个连通的、无环的无向图，简称树。 【注】一个可能不连通的、无环的无向图称为森林。 1.2 概念 结点的度：自由树中节点的度和无向图中的一样，即相邻结点的个数。 1.3 性质 令 G=(V,E)G = (V,E)G=(V,E) 是一个无向图，则下面的描述是等价的： GGG 是自由树。 GGG 中任何两结点由唯一简单路径 2020-08-18 Technique ACM 算法 图论 树 Technique ACM 算法 数据结构 图论 树