内部排序

插入排序

直接插入排序：

描述：对A[n]进行排序，从头开始往后遍历。当前下标为k，记L = A[k]，首先从A[0]~A[k-1]从后往前依次比较元素大小，查找插入位置j；其次，插入位置后的元素依次后移一个位置；最后A[j] = L

1. 哨兵：哨兵值存放着当前插入元素值，由于插入元素不可能大于其本身，于是当插入元素比较到哨兵时便可知道自身值为最小。同时哨兵还能防止发生越界。
2. 时间复杂度：最好O(n)、最坏O(n^2)；空间复杂度：O(1)。算法稳定，适用于顺序、链式存储

折半插入排序：

描述：建立在直接插入的基础上，不同点在于无哨兵且查找元素插入位置时采用折半查找，因为插入元素前面的序列都是有序的。 比较次数为O(nlogn)，与待排序表的初始序列无关，取决于表中元素个数n。 时间复杂度为O(n^2)，算法稳定。

希尔排序：

描述：将待排序表分隔成若干个形如L[i,i+d,i+2d,…,i+kd]的子表，在每个子表中采用直接排序排序；下一趟缩小d后再一次分割，再排序；重复此操作直至有序。该算法又称缩小增量排序 空间复杂度O(1)，算法不稳定且仅适用于线性表。

交换排序

冒泡排序：

描述：从前往后两两比较相邻元素，若大于(或小于)则交换它们，下一趟重复如上操作；每趟至少可以确定一个值的最终位置。 时间复杂度O(n^2)，空间复杂度O(1)

快速排序：

描述：基于分治思想，从待排序表L[1,…,n]中任选一个元素作为pivot(通常取首元素)，通过一趟排序将待排序表划分为两个独立的部分。 过程解析：设置两个指针low、high分别指针排序表的表头和表尾，并从表中表头元素作为pivot。

1. 首先high指针往前遍历找到一个小于pivot的元素k，然后将k的值交换到low所指向的位置。
2. 接着low向后移动，找到一个值大于pivot的元素j，然后将j的值交换到high所指向的位置。
3. 重复上述步骤直至low==high，此时low所指向的位置便为pivot的最终位置，记为一趟排序。
4. 待经过1、2、3后排序表被划分为多个独立的表，分别对这些表再次进行上述步骤即可。。 优化思想：任选一个元素作为pivot，此时交换操作需要等到上述步骤3中才能进行 时间复杂度：最好O(nlog2n)，最坏O(n^2)；空间复杂度：最好O(log2n)，最坏O(n)，平均O(log2n) 算法不稳定，平均性能最优

选择排序

简单选择：每趟选择一个为排序序列中最大或最小的元素与序列头/尾的元素交换。每趟能确定一个元素的最终位置。 时间复杂度：O(n^2)，空间复杂度O(1)

堆排序

排序过程：从最后一个元素开始向上进行如下操作：检查当前结点是否满足根>=左右(大根堆)，若不满足则将当前结点与更大的一个孩子交换。 插入操作：将当前元素插入到堆尾，依次向上进行排序调整。 删除操作：将堆顶元素删除后选取堆的最后一个元素交换到堆顶，此时堆的性质被破坏，需要从堆顶往下依次进行调整。 关键字比较次数：不超过4n 时间复杂度：建堆O(n)，每次调整时间为O(h)，最好、最坏、平均情况下，时间复杂度为O(nlog2n)。 空间复杂度：O(1)

归并排序

描述：将两个或两个以上的有序表合成一个新的有序表。需要先把要合并的有序表复制到辅助数组中再从各个有序段中取出一个记录进行关键字比较，较小者放入原表。 n路归并：将n个的有序表合并成一个新的有序表 整个排序需要logkM(向上取整，k路归并，M个元素)趟排序，每趟排序需要将m个元素分成各含m/n个子表。 时间复杂度：O(nlog2n)；空间复杂度：O(n)

基数排序

最高位优先或最低位优先 思想：借助多关键字的排序思想来对单逻辑关键字进行排序，关键字必须能够比较大小 时间复杂度O(d(n+r)) 空间复杂度O(r)，算法稳定

—总结

1. 对任意n个关键字排序的比较次数至少为log2(n!)次

逻辑结构与存储结构

逻辑结构

线性结构：一般线性表、栈、队列、串、数组 非线性：集合、树、图

存储结构

顺序存储、链式存储、索引存储、散列存储 判断方法：能够采取多种存储方式的结构为逻辑结构，只能采取一种存储方式的为存储结构。 例如：

1. 线索二叉树： 二叉树是逻辑结构，但线索二叉树是加上线索后的【链表结构】，因此是存储结构。
2. 静态链表：是用【一片连续的空间（数组，顺序）】来存储实现的，故静态链表是存储结构。
3. 有向图：可以用【邻接表】或【邻接矩阵】两种实现，故有向图是逻辑结构。
4. 二叉树：可以用【数组】或【指针（链式）】实现，故二叉树是逻辑结构。
5. 散列表：用的是【散列（哈希）】存储，即根据元素的关键字直接计算出该元素的存储地址，故是存储结构。6. 循环队列：用【数组】求余实现，故是存储结构。
6. 顺序表：用【数组】实现，故是存储结构。

栈和树的微妙联系

出栈次序：n 个不同的元素进栈，出栈元素的不同排列个数为 1/(n+1)*2n!/n!(2n-n)! 前序遍历：相当于以前序序列为入栈次序 中序遍历：相当于以后序序列为出栈次序 因为前序遍历和中序遍历可以唯一确定一棵树，因此当给出前序序列要求确定序列对应的不同二叉树的棵数时可以将问题转化为"给定一个入栈(前序)序列，求出栈(中序)序列有多少种"

图的简单知识速览

假设图中有 n 个结点

1. 无向图的|E|取值范围为(0, n(n-1)/2) |E|取最大值时称为完全图；有向图|E|取值范围为(0, n(n-1)) |E|取最大值时称为有向完全图。
2. G=(V,E) G1=(V1, E1)，若 V1 为 V 子集且 E1 为 E 子集，那么 G1 为 G 的子图，若 V1=V，则 G 为生成子图(包含所有顶点)
3. 连通图的生成树是包含图中全部顶点的一个极小连通子图。非连通图中，连通分量的生成树构成了非连通图的生成森林。（极大：连通子图包含尽可能多的边，极小：连通子图包含尽可能少的边）
4. 无向图顶点 v 的度为依附于 v 的边的条数，全部顶点度数之和 = 边数之和的两倍；有向图则分为入度(以 v 为终点)、出度(以 v 为起点)，入度之和 = 出度之和 = 边数两倍
5. 图 G 满足|E| < |V|log|V|时为稀疏图，反之为稠密图
6. 顶点不重复出现的路径成为简单路径；除了第一个顶点和最后一个顶点相同以外，路径上其余顶点不重复出现的路径成为简单回路。当|E| > n-1 时一定有环。
7. 顶点 u 到 v 之间不存在路径，记该距离为 ∞
8. 有向树：根结点入度为 0，其余结点入度为 1

快速判断哈夫曼编码技巧

拥有同一双亲的叶结点编码长度相同，末位不同。

希尔排序增量快速判断

观察初始数据与第一趟排序中位置发生变化的某个数，测算变化间隔 k，检验 k/2，2*k 位置是否符合增序/降序

C 语言初始化

int a[n]; memset(a, “1”, n*sizeof(int));

有向无环图描述表达式

做图步骤：

1. 标出各个运算符的生效次序，按运算可并列性各层依次加入操作数结点
2. 按顺序加入运算符，当需要用到另一个运算结果时产生分层(后来者在顶层)

快速判断队列出队/入队序列

出队：入队序列由外向内递减