[科普中国]-算法列表

数据结构链表

链表是一种由节点（Node）组成的线性数据集合，每个节点通过指针指向下一个节点。它是一种由节点组成，并能用于表示序列的数据结构。

单链表：每个节点仅指向下一个节点，最后一个节点指向空（null）。

双链表：每个节点有两个指针p，n。p指向前一个节点，n指向下一个节点；最后一个节点指向空。

循环链表：每个节点指向下一个节点，最后一个节点指向第一个节点。1

时间复杂度：

索引：O(n)

查找：O(n)

插入：O(1)

删除：O(1)

栈栈是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。

后进先出的数据结构（Last In First Out, LIFO）1

时间复杂度

索引：O(n)

查找：O(n)

插入：O(1)

删除：O(1)

队列队列是一个元素集合，支持两种基本操作：enqueue 用于添加一个元素到队列，dequeue 用于删除队列中的一个元素。

先进先出的数据结构（First In First Out, FIFO）。

时间复杂度

索引：O(n)

查找：O(n)

插入：O(1)

删除：O(1)

树树是无向、联通的无环图。

二叉树二叉树是一个树形数据结构，每个节点最多可以有两个子节点，称为左子节点和右子节点。

满二叉树（Full Tree）：二叉树中的每个节点有 0 或者 2 个子节点。

完美二叉树（Perfect Binary）：二叉树中的每个节点有两个子节点，并且所有的叶子节点的深度是一样的。

完全二叉树：二叉树中除最后一层外其他各层的节点数均达到最大值，最后一层的节点都连续集中在最左边。

二叉查找树二叉查找树（BST）是一种二叉树。其任何节点的值都大于等于左子树中的值，小于等于右子树中的值。

时间复杂度

索引：O(log(n))

查找：O(log(n))

插入：O(log(n))

删除：O(log(n))

字典树字典树，又称为基数树或前缀树，是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值，而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀，根节点则是空字符串。2

排序算法快速排序稳定：否

时间复杂度

最优：O(nlog(n))

最差：O(n^2)

平均：O(nlog(n))

合并排序合并排序是一种分治算法。这个算法不断地将一个数组分为两部分，分别对左子数组和右子数组排序，然后将两个数组合并为新的有序数组。

稳定：是

时间复杂度：

最优：O(nlog(n))

最差：O(nlog(n))

平均：O(nlog(n))

桶排序桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序，或递归调用桶排序。

时间复杂度

最优：Ω(n + k)

最差: O(n^2)

平均：Θ(n + k)

基数排序基数排序类似于桶排序，将元素分发到一定数目的桶中。不同的是，基数排序在分割元素之后没有让每个桶单独进行排序，而是直接做了合并操作。

时间复杂度

最优：Ω(nk)

最差: O(nk)

平均：Θ(nk)2