排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
「数据结构与算法」图(Graph)
图(Graph)。和树比起来,这是一种更加复杂的非线性表结构,由顶点和连接每对顶点的边所构成的抽象网络就是图。
图的定义:图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E)
,其中,G
表示一个图,V
是顶点的集合,E
是边的集合。
图中的元素叫做顶点(vertex)
。顶点与其他顶点建立的连接关系叫做边(edge)
。跟顶点相连接的边的条数叫做顶点的度(degree)
。
如果图中任意两个顶点之间的边都是无向边(边没有方向),则称该图为无向图(Undirected graphs)
。
以此类推,把边有方向的图称为有向图(Directed graphs)
。
- 完全图:
- ①无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。
- ②有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。
- 当一个图接近完全图时,则称它为
稠密图(Dense Graph)
,而当一个图含有较少的边时,则称它为稀疏图(Spare Graph)
。
「数据结构与算法」堆(Heap)
堆的两点要求:
- 堆是一个完全二叉树;
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
- 对于每个节点的值都大于等于子树中每个节点值的堆,我们叫做大顶堆。
- 对于每个节点的值都小于等于子树中每个节点值的堆,我们叫做小顶堆。
「数据结构与算法」红黑树(Red-Black Tree)
平衡二叉查找树其实有很多,比如,红黑树(Red-Black Tree,简称 R-B Tree)、伸展树(Splay Tree)、树堆(Treap)等,但是我们提到平衡二叉查找树,听到的基本都是红黑树,它是一种不严格的平衡二叉查找树。
红黑树是一种含有红黑节点并能自平衡的二叉查找树。它必须满足下面性质:
- 每个节点要么是红色,要么是黑色;
- 根节点是黑色的;
- 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
- 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
- 任意一节点到每个叶子节点的路径,都包含相同数目的黑色节点;
「数据结构与算法」AVL树
AVL
树(得名于发明者G. M. Adelson-Velsky 和 E. M. Landis)本质上是一棵带有平衡条件的二叉搜索树。AVL
树具有以下2
个性质:
- 左子树和右子树的深度之差的绝对值不超过
1
; - 左子树和右子树全都是
AVL
树。
「数据结构与算法」二叉树
树:树是一种非线性的数据结构,一棵树是n
(n>=0
)个节点的集合。
用来连接相邻节点之间的关系,我们叫做“父子关系”。
我们把没有父节点的节点叫做根节点,节点的上一层节点是其父节点,下一层节点是其子节点,拥有相同父节点的子节点之间互称为兄弟节点。
「数据结构与算法」哈希算法
哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一组输入数据进行计算,得到一个固定长度的输出摘要。
哈希算法最重要的特点就是:相同的输入一定得到相同的输出;不同的输入大概率得到不同的输出。
「数据结构与算法」散列表(Hash Table)
散列表(Hash Table
),也叫“哈希表”或者“Hash表”。是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。
通常,我们把这个关键字称为 Key
,把对应的记录称为 Value
,所以也可以说是通过 Key
访问一个映射表来得到 Value
的地址。而这个映射表,也叫作散列函数或者哈希函数,存放记录的数组叫作散列表。
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。
「数据结构与算法」跳表(Skip List)
跳表(Skip List)是一个动态数据结构(链表加多级索引),可以支持快速地插入、删除、查找操作的有序链表。
跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。