算法与数据结构

栈

​ 问题类型：

​ 修改栈

​ 递归与栈

​ 树

​ 利用栈实现队列

​ 解法类型：

​ 单调栈

​ 双指针

​ 双栈

​ 观察并推导出数学公式

​ 语言自带工具类

​

队列

​ 滑动窗口

常见问题

队列的实现方式及其应用

双端队列

​ 注意：Deque同时具有双端队列的性质

堆

​ 优先队列和堆

优化算法的方法

​ 二分法？？

树

二叉树

​ L、D、R分别表示遍历左子树、访问根结点和遍历右子树

• 先序（根）遍历：DLR
• 中序（根）遍历：LDR
• 后序（根）遍历：LRD

仅有前序和后序遍历，不能确定一个二叉树，必须有中序遍历的结果

二叉树的性质

• 性质1：在二叉树中第 i 层的结点数最多为 2^{i-1}2i−1 （i ≥ 1）
• 性质2：高度为k的二叉树其结点总数最多为 2^{k}－12k－1 （k ≥ 1）
• 性质3：对任意的非空二叉树 T ，如果叶结点的个数为n0 ，而其度为 2 的结点数为n2 ，则： n0=n2+1

满二叉树

深度为k，且有 2^k-1 个节点称之为 满二叉树；

• 性质4：第i层上的节点数为 2^{i-1} ；

完全二叉树

深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

• 性质5：对于具有n个结点的完全二叉树的高度为 log_{2}^{n}+1

二叉树的构造

//n 表示当前结点字符
Node* tree(vector<char> data, int n) {

    Node* node;

    if (n >= data.size())
        return NULL;
    if (data[n] == '#')
        return NULL;

    node = new Node;
    node->data = data[n];

    node->left = tree(data, n + 1);
    node->right = tree(data, n + 2);
    return node;
}

堆

堆通常是一个可以被看做一棵树的数组对象。堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
• 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

通常堆是通过一维数组来实现的。在数组起始位置为1的情形中：

• 父节点i的左子节点在位置 2×i ;
• 父节点i的右子节点在位置 2×i+1 ;
• 子节点i的父节点在位置 i÷2 ;

霍夫曼树

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为 WPL=W1\times L1+W2\times L2+W3\times L3+…+Wn\times LnWPL=W1×L1+W2×L2+W3×L3+…+Wn×Ln ，N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明霍夫曼树的WPL是最小的。

霍夫曼树构造

1. 根据给定的n个权值(W1,W2...Wn)，使对应节点构成n个二叉树的森林T=(T1,T2...Tn)，其中每个二叉树Ti(1 <= i <= n)中都有一个带权值为Wi的根节点，其左、右子树均为空。
2. 在森林T中选取两个节点权值最小的子树，分别作为左、右子树构造一个新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点权值之和。
3. 在森林T中，用新得到的二叉树替代选取的两个二叉树。
4. 重复2和3，直到T只包含一个树为止。这个数就是霍夫曼树。

定理：对于具有n个叶子节点的霍夫曼树，共有2n-1个节点。这是由于霍夫曼树只有度为0和度为2的结点，根据二叉树的性质 n0 = n2 + 1，因此度为2的结点个数为n-1个，总共有2n-1个节点。

霍夫曼编码

对于一个霍夫曼树，所有左链接取’0’、右链接取’1’。从树根至树叶依序记录所有字母的编码。

带权路径

• 结点的权：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
• 结点的带权路径：从根结点到该结点之间的路径长度与该结点的权的乘积。
• 树的带权路径：所有叶子结点的带权路径长度之和，记为WPL。

平衡二叉树

​ 一般的二叉查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

​ AVL树是最先发明的 自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。

• 它的左子树和右子树都是平衡二叉树。
• 左子树和右子树的深度之差的绝对值不超过1。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

• 右旋：左结点转到根节点位置。
• 左旋：右节点转到根节点位置。

高度为k的AVL树，节点数N最多2^k -1，即满二叉树；

红黑树

​ 红黑树是一种自平衡二叉查找树，每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

• 节点是红色或黑色。
• 根是黑色。
• 所有叶子都是黑色（叶子是NIL节点）。
• 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

​

​ 红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

​ 这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限 允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用”nil叶子”或”空（null）叶子”，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量（O(log n)）的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为O(log n)次。

B树

B树是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，复杂度均为 O(n)O(n) 。总的来说，B树是一个泛化的二叉查找树，一个节点可以拥有两个以上的子节点。但其与自平衡二叉查找树不同，B树更适合大数据块的存储系统，例如：磁盘。

在B树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被 合并 或者 分离。因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点 没有被完全填充，可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。例如，在一个2-3 B树（通常简称2-3树），每一个内部节点只能有 2 或 3 个子节点。

根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：

• 每一个节点最多有 m 个子节点
• 每一个非叶子节点（除根节点）最少有 m\div 2m÷2 个子节点
• 如果根节点不是叶子节点，那么它至少有两个子节点
• 有 k 个子节点的非叶子节点拥有 k − 1 个键
• 所有的叶子节点都在同一层

每一个内部节点的键将节点的子树分开。例如，如果一个内部节点有 3 个子节点（子树），那么它就必须有两个键： a1 和 a2 。左边子树的所有值都必须小于 a1 ，中间子树的所有值都必须在 a1 和a2 之间，右边子树的所有值都必须大于 a2 。

B树内的节点可分为三类：

• 内部节点：内部节点是除叶子节点和根节点之外的所有节点。它们通常被表示为一组有序的元素和指向子节点的指针。
• 根节点：根节点拥有的子节点数量的上限和内部节点相同，但是没有下限。
• 叶子节点：叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。

B树的查找

在B树中的查找给定关键字的方法 类似于二叉排序树上的查找，不同的是在每个节点上确定向下查找的路径不一定是二路的，而是n+1路的。因为节点内的关键字序列key[1..n]有序，故既可以使用顺序查找，也可以使用二分查找。在一棵B树上查找关键字为k的方法为：将k与根节点中的key[i]进行比较：

1. 若k=key[i]，则查找成功；
2. 若k<key[1]，则沿指针ptr[0]所指的子树继续查找；
3. 若key[i]<k<key[i+1]，则沿着指针ptr[i]所指的子树继续查找；
4. 若k>key[n]，则沿着指针ptr[n]所指的子树继续查找。

B树的插入

将关键字k插入到B树的过程分两步完成：

1. 利用B树的查找算法查找出该关键字的插入节点(注意B树的插入节点一定属于最低非叶子节点层)。
2. 判断该节点是否还有空位，即判断该节点是否满足n < m-1，若满足：直接把关键字k插入到该节点合适位置上；若不满足：分裂节点，取一新节点，把原节点上的关键字和k按升序排列后，从中间位置(m/2)处把关键字(不包括中间位置的关键字)分成两部分，左部分所含关键字放在旧节点中，右部分关键字放在新节点中，中间位置的关键字连同新节点的存储位置插入到双亲节点。如果双亲节点的关键字个数也超出max则再分裂。

B树的删除

首先查找B树中需删除的元素，如果该元素在B树中存在，则将该元素在其结点中进行删除；如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素到父节点中，然后是移动之后的情况；如果没有，直接删除后，然后是移动之后的情况。

删除元素，移动相应元素之后，如果某结点中元素数目（即关键字数）小于Min(m/2)-1，则需要看其某相邻兄弟结点是否丰满，如果丰满，则向父节点借一个元素来满足条件；如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于Min(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点，

B+树

B+ 树是 B 树的变体，也是一种多路搜索树。m阶的 B+ 树和 B 树的主要差异如下：

• 在B+树中，具有n个关键字的节点含有n个子树，即每个关键字对应一个子树，而在B树中，具有n个关键字的节点含有(n+1)个子树。
• 在B+树中，每个节点(除根节点外)中的关键字个数n的取值范围是[m/2] <= n <= m，根节点n的取值范围2 <=n <=m；而在B树中，除根节点外，其他所有非叶子节点的关键字个数：[m/2]-1 <= n <= m-1，根节点关键字个数为1 <= n <= m-1
• B+树中所有叶子节点包含了全部关键字，即其他非叶子节点中的关键字包含在叶子节点中，而在B树中，关键字是不重复的。
• B+树中所有非叶子节点仅起到索引的作用，即节点中每个索引项值含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。而在B树中，每个关键字对应一个记录的存储地址。
• 在 B+ 树所有叶子节点链接成一个不定长的线性表。

B+树的查找

在B+树中可以采用两种查找方式：

• 直接从最小关键字开始顺序查找。
• 从B+树的根节点开始随机查找。这种查找方式与B树的查找方式类似，只是在分支节点上的关键字与查找值相等时，查找并不会结束，要继续查到叶子节点为止，此时若查找成功，则按所给指针取出对应元素。

在B+树中，不管查找是否成功，每次查找都是经历一条树从根节点到叶子节点的路径。

B+树的插入

1. 首先，查找要插入其中的节点的位置。接着把值插入这个节点中。
2. 如果没有节点处于违规状态则处理结束。
3. 如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则创建一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不小于最大数的一半。

B+树的删除

1. 首先，查找要删除的值。接着从包含它的节点中删除这个值。
2. 如果没有节点处于违规状态则处理结束。
3. 如果节点处于违规状态则有两种可能情况：
   • 它的兄弟节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。
   • 它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。

B+树的优势所在

为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引？

1. B+树的中间节点能存储更多指针
2. B+树的查询效率更加稳定：关键字查询的路径长度相同
3. 减少回溯：由于B+树中叶子节点存在指针，所以在范围查找时不需要回溯到父节点，直接类型链表遍历即可，减少IO

Trie树

Trie树，又称前缀树，字典树， 是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie树查询和插入时间复杂度都是 O(n)，是一种以空间换时间的方法。当节点树较多的时候，Trie 树占用的内存会很大。

Trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

Hash

哈希表（Hash Table，也叫散列表），是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。哈希表的实现主要需要解决两个问题，哈希函数和冲突解决。

哈希函数

哈希函数也叫散列函数，它对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构，同时散列结果应当具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值变化使得输出值发生巨大的变化）。

冲突解决

• 开放地址法：

  以发生冲突的哈希地址为输入，通过某种哈希冲突函数得到一个新的空闲的哈希地址的方法有以下几种方式：

• 线性探查法：从发生冲突的地址开始，依次探查下一个地址，直到找到一个空闲单元。

• 平方探查法：设冲突地址为d0，则探查序列为：d0+1^2,d0-1^2,d0+2^2…

• 拉链法：把所有的同义词用单链表链接起来。在这种方法下，哈希表每个单元中存放的不再是元素本身，而是相应同义词单链表的头指针。HashMap就是使用这种方法解决冲突的。

最小生成树算法

• 连通图：在无向图G中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若图G中任意两个顶点都连通，则称G为连通图。
• 生成树：一个连通图的生成树是该连通图的一个极小连通子图，它含有全部顶点，但只有构成一个数的(n-1)条边。
• 最小生成树：对于一个带权连通无向图G中的不同生成树，各树的边上的 权值之和最小。构造最小生成树的准则有三条：
  • 必须只使用该图中的边来构造最小生成树。
  • 必须使用且仅使用(n-1)条边来连接图中的n个顶点。
  • 不能使用产生回路的边。

Prim算法

假设G=(V,E)是一个具有n个顶点的带权连通无向图，T(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点v出发的最小生成树T的步骤为：

• 初始化U={v}，以v到其他顶点的所有边为候选边(U中所有点到其他顶点的边)。
• 重复以下步骤(n-1)次，使得其他(n-1)个顶点被加入到U中。
  • 从候选边中挑选权值最小的边加入TE，设该边在V-U(这里是集合减)中的顶点是k，将k加入U中。
  • 考察当前V-U中的所有顶点j，修改候选边，若边(k,j)的权值小于原来和顶点j关联的候选边，则用(k,j)取代后者作为候选边。

Kruskal算法

假设G=(V,E)是一个具有n个顶点的带权连通无向图，T(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点v出发的最小生成树T的步骤为：

• 置U的初始值等于V(即包含G中的全部顶点)，TE的初始值为空
• 将图G中的边按权值从小到大的顺序依次选取，若选取的边未使生成树T形成回路，则加入TE，否则放弃，知道TE中包含(n-1)条边为止。

最短路径算法

Dijkstra —— 贪心算法

从一个顶点到其余顶点的最短路径

设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第1组为已求出最短路径的顶点（用S表示，初始时S只有一个源点，以后每求得一条最短路径v,...k，就将k加到集合S中，直到全部顶点都加入S）。第2组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序把第2组的顶点加入S中。

步骤：

1. 初始时，S只包含源点，即`S={v}`，顶点v到自己的距离为0。U包含除v外的其他顶点，v到U中顶点i的距离为边上的权。
2. 从U中选取一个顶点u，顶点v到u的距离最小，然后把顶点u加入S中。
3. 以顶点u为新考虑的中间点，修改v到U中各个点的距离。
4. 重复以上步骤知道S包含所有顶点。

Floyd —— 动态规划

Floyd 算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题。该算法的时间复杂度为 O(N^{3})O(N3) ，空间复杂度为 O(N^{2})O(N2)

设 D_{i,j,k}D**i,j,k 为从 ii 到 jj 的只以 (1..k)(1..k) 集合中的节点为中间节点的最短路径的长度。

$$ D_{i,j,k}=\begin{cases} D_{i,j,k-1} & 最短路径不经过 k
D_{i,k,k-1}+D_{k,j,k-1} & 最短路径经过 k \end{cases} $$

因此， D_{i,j,k}=min(D_{i,k,k-1}+D_{k,j,k-1},D_{i,j,k-1})D**i,j,k=min(D**i,k,k−1+D**k,j,k−1,D**i,j,k−1) 。伪代码描述如下：

// let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 for each vertex v
    dist[v][v] ← 0
 for each edge (u,v)
    dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
 for k from 1 to |V|
    for i from 1 to |V|
       for j from 1 to |V|
          if dist[i][j] > dist[i][k] + dist[k][j]
             dist[i][j] ← dist[i][k] + dist[k][j]
         end if

KMP算法

KMP算法解决的问题是字符匹配，这个算法把字符匹配的时间复杂度缩小到O(m+n),而空间复杂度也只有O(m),n是target的长度，m是pattern的长度。

• 部分匹配表（Next数组）：表的作用是 让算法无需多次匹配S中的任何字符。能够实现线性时间搜索的关键是 在不错过任何潜在匹配的情况下，我们”预搜索”这个模式串本身并将其译成一个包含所有可能失配的位置对应可以绕过最多无效字符的列表。
• Next数组（前缀和前缀的比较）：t为模式串，j为下标
  • Next[0] = -1
  • Next[j] = MAX{ k | 0 < k < j | " t0 t1 ... tk " = "t ( j-k ) t ( j-k+1 ) ... t( j-1 )" }

|i| 0| 1| 2| 3| 4| 5 |6| |–| | t[i]| A| B| C| D| A| B| D| |next[i]| -1| 0 |0 |0 |0 |1 |2|

• NextVal数组：是一种优化后的Next数组，是为了解决类似aaaab这种模式串的匹配，减少重复的比较。 如果t[next[j]]=t[j]：nextval[j]=nextval[next[j]]，否则nextval[j]=next[j]。

|i| 0| 1| 2| 3| 4| 5 |6| |–| | t | a| b| c| a| b| a |a| |next[j] | -1| 0 |0 |0 |1 |2 |1| |nextval[j] | -1| 0 |0 |-1 |0 |2 |1|

在上面的表格中，t[next[4]]=t[4]=b，所以nextval[4]=nextval[next[4]]=0

查找算法

ASL

由于查找算法的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数（平均查找长度）作为衡量一个查找算法效率的标准。ASL= ∑(n,i=1) Pi*Ci，其中n为元素个数，Pi是查找第i个元素的概率，一般为Pi=1/n，Ci是找到第i个元素所需比较的次数。

顺序查找

原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。时间复杂度o(n)。

折半查找

折半查找要求线性表是有序表。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)。

• 可以借助二叉判定树求得折半查找的平均查找长度：log2(n+1)-1。
• 折半查找在失败时所需比较的关键字个数不超过判定树的深度，n个元素的判定树的深度和n个元素的完全二叉树的深度相同log2(n)+1。

public int binarySearchStandard(int[] num, int target){
    int start = 0;
    int end = num.length - 1;
    while(start <= end){ //注意1
        int mid = start + ((end - start) >> 1);
        if(num[mid] == target)
            return mid;
        else if(num[mid] > target){
            end = mid - 1; //注意2
        }
        else{
            start = mid + 1; //注意3
        }
    }
    return -1;
}

• 如果是start < end，那么当target等于num[num.length-1]时，会找不到该值。
• 因为num[mid] > target, 所以如果有num[index] == target, index一定小于mid，能不能写成end = mid呢？举例来说：num = {1, 2, 5, 7, 9}; 如果写成end = mid，当循环到start = 0, end = 0时（即num[start] = 1, num[end] = 1时），mid将永远等于0，此时end也将永远等于0，陷入死循环。也就是说寻找target = -2时，程序将死循环。
• 因为num[mid] < target, 所以如果有num[index] == target, index一定大于mid，能不能写成start = mid呢？举例来说：num = {1, 2, 5, 7, 9}; 如果写成start = mid，当循环到start = 3, end = 4时（即num[start] = 7, num[end] = 9时），mid将永远等于3，此时start也将永远等于3，陷入死循环。也就是说寻找target = 9时，程序将死循环。

分块查找

分块查找又称索引顺序查找，它是一种性能介于顺序查找和折半查找之间的查找方法。分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

排序算法

常见排序算法

稳定排序：

• 冒泡排序 — O(n²)
• 插入排序 — O(n²)
• 桶排序 — O(n); 需要 O(k) 额外空间
• 归并排序 — O(nlogn); 需要 O(n) 额外空间
• 二叉排序树排序 — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
• 基数排序 — O(n·k); 需要 O(n) 额外空间

不稳定排序

• 选择排序 — O(n²)
• 希尔排序 — O(nlogn)
• 堆排序 — O(nlogn)
• 快速排序 — O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

交换排序

冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序总的平均时间复杂度为O(n^2)。冒泡排序是一种稳定排序算法。

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

void bubble_sort(int a[], int n)
{
    int i, j, temp;
    for (j = 0; j < n - 1; j++)
        for (i = 0; i < n - 1 - j; i++)
        {
            if(a[i] > a[i + 1])
            {
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
}

快速排序 快速排序-百度百科

快速排序是一种 不稳定 的排序算法，平均时间复杂度为 O(nlogn)。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 步骤为：

• 从数列中挑出一个元素，称为”基准”（pivot），
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快排的时间花费主要在划分上，所以

• 最坏情况：时间复杂度为O(n^2)。因为最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。
• 最好情况：每次划分选取的基准都是当前无序区的中值。如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了。

public void sort(int[] arr, int low, int high) {
    int l = low;
    int h = high;
    int povit = arr[low];
    while (l < h) {
        while (l < h && arr[h] >= povit)
            h--;
        if (l < h) {
            arr[l] = arr[h];
            l++;
        }
        while (l < h && arr[l] <= povit)
            l++;
        if (l < h) {
            arr[h] = arr[l];
            h--;
        }
    }

    arr[l] = povit;

    System.out.print("l=" + (l + 1) + ";h=" + (h + 1) + ";povit=" + povit + "\n");
    System.out.println(Arrays.toString(arr));
    if (l - 1 > low) sort(arr, low, l - 1);
    if (h + 1 < high) sort(arr, h + 1, high);
}

快排的优化

1. 当待排序序列的长度分割到一定大小后，使用插入排序。
2. 快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。
3. 从左、中、右三个数中取中间值。

插入排序

直接插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

void insert_sort(int* a, int len) {
    for (int i = 1; i < len; ++i) {
        int j = i - 1;
        int temp = a[i];
        while (j >= 0 && temp < a[j]) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
}

希尔排序

也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

void shell_sort(int* a, int len) {
    int step = len / 2;
    int temp;

    while (step > 0) {
        for (int i = step; i < len; ++i) {
            temp = a[i];
            int j = i - step;
            while (j >= 0 && temp < a[j]) {
                a[j + step] = a[j];
                j -= step;
            }
            a[j + step] = temp;
        }
        step /= 2;
    }
}

选择排序

直接选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。实际适用的场合非常罕见。

void selection_sort(int arr[], int len) {
    int i, j, min, temp;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len; j++)
            if (arr[min] > arr[j])
                min = j;
           temp = arr[min];
        arr[min] = arr[i];
        arr[i] = temp;
    }
}

堆排序

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。

1. 将数组分为有序区和无序区，在无序区中建立最大堆
2. 将堆顶的数据与无序区末尾的数据交换
3. 从后往前，直到所有数据排序完成

public void heapSort(int[] nums) {
    for (int i = nums.length - 1; i >= 0; i--) {
        maxHeap(nums, 0, i);

        swap(nums, 0, i);
    }
}

public void maxHeap(int[] heap, int start, int end) {
    if (start == end) {
        return;
    }

    int parent = start;
    int childLeft = start * 2 + 1;
    int childRight = childLeft + 1;

    if (childLeft <= end) {
        maxHeap(heap, childLeft, end);

        if (heap[childLeft] > heap[parent]) {
            swap(heap, parent, childLeft);
        }
    }

    if (childRight <= end) {
        maxHeap(heap, childRight, end);

        if (heap[childRight] > heap[parent]) {
            swap(heap, parent, childRight);
        }
    }
}

private void swap(int[] nums, int a, int b) {
    int t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
}

归并排序

归并排序采用分治的思想：

• Divide：将n个元素平均划分为各含n/2个元素的子序列；
• Conquer：递归的解决俩个规模为n/2的子问题；
• Combine：合并俩个已排序的子序列。

性能：时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。

public void mergeSort(int[] array, int start, int end, int[] temp) {
    if (start >= end) {
        return;
    }

    int mid = (start + end) / 2;

    mergeSort(array, start, mid, temp);
    mergeSort(array, mid + 1, end, temp);

    int f = start, s = mid + 1;
    int t = 0;
    while (f <= mid && s <= end) {
        if (array[f] < array[s]) {
            temp[t++] = array[f++];
        } else {
            temp[t++] = array[s++];
        }
    }

    while (f <= mid) {
        temp[t++] = array[f++];
    }

    while (s <= end) {
        temp[t++] = array[s++];
    }

    for (int i = 0, j = start; i < t; i++) {
        array[j++] = temp[i];
    }
}

桶排序

桶排序工作的原理是将 数组分到有限数量的桶 里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)O(n) 。由于桶排序不是比较排序，他不受到 O(n\log n)O(nlogn) 下限的影响。

桶排序以下列程序进行：

• 设置一个定量的数组当作空桶子。
• 寻访序列，并且把项目一个一个放到对应的桶子去。
• 对每个不是空的桶子进行排序。
• 从不是空的桶子里把项目再放回原来的序列中。

private int indexFor(int a, int min, int step) {
    return (a - min) / step;
}

public void bucketSort(int[] arr) {
    int max = arr[0], min = arr[0];
    for (int a : arr) {
        if (max < a)
            max = a;
        if (min > a)
            min = a;
    }
    // 该值可根据实际情况选择
    int bucketNum = max / 10 - min / 10 + 1;
    List buckList = new ArrayList<List<Integer>>();
    // create bucket
    for (int i = 1; i <= bucketNum; i++) {
        buckList.add(new ArrayList<Integer>());
    }
    // push into the bucket
    for (int i = 0; i < arr.length; i++) {
        int index = indexFor(arr[i], min, 10);
        ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
    }
    ArrayList<Integer> bucket = null;
    int index = 0;
    for (int i = 0; i < bucketNum; i++) {
        bucket = (ArrayList<Integer>) buckList.get(i);
        insertSort(bucket);
        for (int k : bucket) {
            arr[index++] = k;
        }
    }
}

// 把桶內元素插入排序
private void insertSort(List<Integer> bucket) {
    for (int i = 1; i < bucket.size(); i++) {
        int temp = bucket.get(i);
        int j = i - 1;
        for (; j >= 0 && bucket.get(j) > temp; j--) {
            bucket.set(j + 1, bucket.get(j));
        }
        bucket.set(j + 1, temp);
    }
}

基数排序

对于有d个关键字时，可以分别按关键字进行排序。有俩种方法：

• MSD：先从高位开始进行排序，在每个关键字上，可采用基数排序
• LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

即通过每个数的每位数字的大小来比较

//找出最大数字的位数
int maxNum(int arr[], int len) {
    int _max = 0;

    for (int i = 0; i < len; ++i) {
        int d = 0;
        int a = arr[i];

        while (a) {
            a /= 10;
            d++;
        }

        if (_max < d) {
            _max = d;
        }
    }
    return _max;
}


void radixSort(int *arr, int len) {
    int d = maxNum(arr, len);
    int *temp = new int[len];
    int count[10];
    int radix = 1;

    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < 10; ++j) {
            count[j] = 0;
        }

        for (int k = 0; k < len; ++k) {
            count[(arr[k] / radix) % 10]++;
        }

        for (int l = 1; l < 10; ++l) {
            count[l] += count[l - 1];
        }

        for (int m = 0; m < len; ++m) {
            int index = (arr[m] / radix) % 10;
            temp[count[index] - 1] = arr[m];
            count[index]--;
        }

        for (int n = 0; n < len; ++n) {
            arr[n] = temp[n];
        }
        radix *= 10;

    }

    delete (temp);
}

拓扑排序

在有向图中找拓扑序列的过程，就是拓扑排序。拓扑序列常常用于判定图是否有环。

• 从有向图中选择一个入度为0的结点，输出它。
• 将这个结点以及该结点出发的所有边从图中删除。
• 重复前两步，直到没有入度为0的点。

如果所有点都被输出，即存在一个拓扑序列，则图没有环。

跳跃表

跳跃列表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是 O(log n) ，优于普通队列的 O(n)。

快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。跳过的元素的方法可以是 随机性选择 或 确定性选择，其中前者更为常见。

在查找目标元素时，从顶层列表、头元素起步。算法沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。

跳跃列表不像平衡树等数据结构那样提供对最坏情况的性能保证：由于用来建造跳跃列表采用随机选取元素进入更高层的方法，在小概率情况下会生成一个不平衡的跳跃列表（最坏情况例如最底层仅有一个元素进入了更高层，此时跳跃列表的查找与普通列表一致）。但是在实际中它通常工作良好，随机化平衡方案也比平衡二叉查找树等数据结构中使用的确定性平衡方案容易实现。跳跃列表在并行计算中也很有用：插入可以在跳跃列表不同的部分并行地进行，而不用对数据结构进行全局的重新平衡。

跳跃表插入一个元素：

实现

因为跳跃列表中的元素可以在多个列表中，所以每个元素可以有多于一个指针。跳跃列表的插入和删除的实现与普通的链表操作类似，但高层元素必须在进行多个链表中进行插入或删除。

package io.github.hadyang.leetcode.algo;

import lombok.Getter;
import lombok.Setter;

import java.util.Arrays;
import java.util.Random;

/**
 * @author haoyang.shi
 */
public class SkipList<K extends Comparable<K>, V> {

    @Getter
    @Setter
    static final class Node<K extends Comparable<K>, V> {
        private K key;

        private V value;

        private Node<K, V> up, down, pre, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }


        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", hashcode=" + hashCode() +
                    ", up=" + (up == null ? "null" : up.hashCode()) +
                    ", down=" + (down == null ? "null" : down.hashCode()) +
                    ", pre=" + (pre == null ? "null" : pre.hashCode()) +
                    ", next=" + (next == null ? "null" : next.hashCode()) +
                    '}';
        }
    }

    private Node<K, V> head;//k,v都是NULL

    private Integer levels = 0;

    private Integer length = 0;

    private Random random = new Random(System.currentTimeMillis());

    public SkipList() {
        createNewLevel();
    }

    public void put(K key, V value) {
        if (key == null || value == null) {
            return;
        }

        Node<K, V> newNode = new Node<>(key, value);
        insertNode(newNode);
    }

    private void insertNode(Node<K, V> newNode) {
        Node<K, V> curNode = findNode(newNode.getKey());
        if (curNode.getKey() == null) {
            insertNext(curNode, newNode);
        } else if (curNode.getKey().compareTo(newNode.getKey()) == 0) {
            //update
            curNode.setValue(newNode.getValue());
            return;
        } else {
            insertNext(curNode, newNode);
        }

        int currentLevel = 1;
        Node<K, V> oldTop = newNode;
        while (random.nextInt(100) < 50) {
            Node<K, V> newTop = new Node<>(newNode.getKey(), null);

            if (currentLevel >= levels) {
                createNewLevel();
            }

            while (curNode.getPre() != null && curNode.getUp() == null) {
                curNode = curNode.getPre();
            }

            if (curNode.getUp() == null) {
                continue;
            }

            curNode = curNode.getUp();
            Node<K, V> curNodeNext = curNode.getNext();

            curNode.setNext(newTop);
            newTop.setPre(curNode);
            newTop.setDown(oldTop);
            oldTop.setUp(newTop);

            newTop.setNext(curNodeNext);
            oldTop = newTop;

            currentLevel++;
        }
    }

    private void createNewLevel() {
        Node<K, V> newHead = new Node<>(null, null);
        if (this.head == null) {
            this.head = newHead;
            this.levels++;
            return;
        }

        this.head.setUp(newHead);
        newHead.setDown(this.head);
        this.head = newHead;
        this.levels++;
    }

    private void insertNext(Node<K, V> curNode, Node<K, V> newNode) {
        Node<K, V> curNodeNext = curNode.getNext();
        newNode.setNext(curNodeNext);
        if (curNodeNext != null) {
            curNodeNext.setPre(newNode);
        }
        curNode.setNext(newNode);
        newNode.setPre(curNode);

        this.length++;
    }

    public V get(K key) {
        Node<K, V> node = findNode(key);
        if (key.equals(node.getKey())) {
            return node.getValue();
        }

        return null;
    }

    private Node<K, V> findNode(K key) {
        Node<K, V> curNode = this.head;

        for (; ; ) {
            while (curNode.getNext() != null && curNode.getNext().getKey().compareTo(key) <= 0) {
                curNode = curNode.getNext();
            }

            if (curNode.getDown() != null) {
                curNode = curNode.getDown();
            } else {
                break;
            }
        }

        return curNode;
    }

    public void print() {
        Node<K, V> curI = this.head;

        String[][] strings = new String[levels][length + 1];
        for (String[] string : strings) {
            Arrays.fill(string, "0");
        }

        while (curI.getDown() != null) {
            curI = curI.getDown();
        }

        System.out.println("levels:" + levels + "_" + "length:" + length);

        int i = 0;
        while (curI != null) {
            Node<K, V> curJ = curI;

            int j = levels - 1;
            while (curJ != null) {
                strings[j][i] = String.valueOf(curJ.getKey());

                if (curJ.getUp() == null) {
                    break;
                }
                curJ = curJ.getUp();
                j--;
            }

            if (curI.getNext() == null) {
                break;
            }
            curI = curI.getNext();
            i++;
        }

        for (String[] string : strings) {
            System.out.println(Arrays.toString(string));
        }
    }

    public static void main(String[] args) {

        SkipList<Integer, String> skipList = new SkipList<>();

        skipList.put(2, "B");
        skipList.put(1, "A");
        skipList.put(3, "C");

        skipList.print();

        System.out.println(skipList.get(2));

    }

常见问题

链表

1.判断链表是否有环

参考

【1】https://hadyang.github.io/interview/docs/basic/algo/

【2】https://www.cnblogs.com/onepixel/articles/7674659.html