[toc]

软件设计师笔记03_数据结构

下面的内容参考自《软件设计师教程(第5版)》 这本书的第3章 数据结构。

该章节的架构图如下。可以分为线性结构、非线性结构与数据的运算三个部分。

线性结构

线性结构的特点是数据元素之间呈现一种线性关系，即元素 “一个接一个排列”。

线性表

线性表是最简单、最基本的线性结构。

线性表通常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。

线性表的存储结构

线性表常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。

• 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻
• 链式存储：存储各数据元素的结点的地址并不要求是连续的，各个数据元素逻辑上相邻，物理上分开

栈

栈是一种“先进后出”的线性表。在栈中进行插入和删除操作的一端称为栈顶，另一端称为栈底。

队列

队列是一种“先进先出”（FIFO）的线性表，即在表的一端插入元素，在另一端删除元素。在队列中允许插入元素的一端称为队尾，允许删除元素的一端称为队头。

串

串是由字符构成的有限序列，也是一种线性表，一般记为 s = “a1a2...an”（n>0）。其中 s 是串的名称，用单引号括起来的字符序列是串值。

串的几个基本概念

• 空串：长度为 0 的串称为空串，空串不包含任何字符。
• 空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。
• 子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。空串是任意串的子串。
• 串相等:指两个串长度相等且对应序号的字符也相同。
• 串比较:两个串比较大小时以字符的ASCII码值(或其他字符编码集合)作为依据。实质上，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大。若其中一个串先结束，则以串长较大者为大。

串的存储结构

串可以进行顺序存储或链式存储。

• 串的顺序存储结构。是指用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。

• 串的链式存储结构。当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符，此时要考虑存储密度问题。在链式存储结构中，结点大小的选择会直接影响对串的处理效率。

串的模式匹配

子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。

朴素的模式匹配算法

改进的模式匹配算法（KMP算法）

非线性结构

一维数组

一维数组是最简单的数组形式，它是一组具有相同数据类型的数据元素的有序集合。数组中的每个元素通过下标（索引）来唯一标识。

一维数组的特点

1. 数据元素数目固定：数组一旦定义，其长度就固定不变。
2. 数据元素类型相同：数组中的所有元素必须是同一数据类型。
3. 元素有序性：数组中的元素按照线性顺序排列，每个元素都有唯一的下标。
4. 随机访问性：可以通过下标直接访问数组中的任意元素，时间复杂度为O(1)。

一维数组的定义和初始化

c语言中的一维数组的定义和初始化。如下示例

int arr[5] = {1, 2, 3, 4, 5};
int arr[5] = {1, 2, 3};  // 未指定的元素自动初始化为0
int arr[] = {1, 2, 3, 4, 5};  // 编译器自动计算数组长度

二维数组

二维数组的特点如下：

1. 数据元素数目固定。
2. 数据元素具有相同的类型。
3. 数据元素的下标关系具有上下界约束且下标有序。

一个m行n列的数组表示如下

数组存储地址的计算公式

假设每个数组元素占用内存长度为len，起始地址为a，存储地址计算如下：

对称矩阵

稀疏矩阵

三对角矩阵

常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。

树

树是一种非线性结构，树中的每一个数据元素可以有两个或两个以上的直接后继元素，用来描述层次结构关系。

如图所示。

树的基本概念

1. 双亲、孩子和兄弟。结点的子树的根称为该节点的孩子结点；相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。
2. 结点的度。一个结点拥有子树的个数称为该结点的度。例如，如图 3-10 中，A 的度为 3，B 的度为 2，C 的度为 0，D 的度为 1。
3. 叶子结点。叶子结点是指度为 0 的结点。例如，图 3-10 中的 E、F、C、G 都是叶子结点。
4. 内部结点。除根结点外，度不为 0 的结点称为内部结点。例如，图 3-10 中的 B、D 都是内部结点。
5. 结点的层次。例如，图 3-10 中的 A 在第一层，B、C、D 在第二层，E、F、G 在第三层。
6. 树的深度。一棵树的最大层数为该树的深度（或高度）。例如，图 3-10 中的树的深度为 3。
7. 有序/无序树。如果树中各结点的各个子树是从左到右有序排列且不能交换时，则称该树为有序树，否则称为无序树。

二叉树

二叉树与普通树的区别在于，每个节点最多只有两个孩子结点。二叉树中结点的子树分为左子树和右子树。

如图所示

二叉树的重要特性

• 一个深度为k的二叉树最多有 2^k^-1 个结点（k>=1）。
• 在二叉树的第i层上最多有个 2^(i-1)^ 个结点(i>=1)。
• 对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。即度为0的结点数比度为2的结点数多1个。

满二叉树与完全二叉树与非完全二叉树

• 满二叉树：如果一个二叉树的层数为 K，结点总数为 2^k^ - 1 个，则它就是满二叉树，如图a所示。
• 完全二叉树：在一个深度为 h 的完全二叉树中，除第 h 层外（最后一层），其他各层都是满的。第 h 层所有的结点都必须从左到右依次放置，不能留空，如图 b 所示。
• 非完全二叉树：除了上面两个情况之外的二叉树就是非完全二叉树，图 c 为非完全二叉树。

二叉树的存储结构

顺序存储

二叉树的顺序存储结构：顺序存储，就是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。

在采用顺序存储时，完全二叉树与一般的二叉树相比节省了空间，这是因为一般二叉树需要添加一些“虚结点”而造成了空间的浪费，如图所示。

链式存储

二叉树的链式存储结构：一般用二叉链表来存储二叉树节点，二叉链表中除了该节点本身的数据外，还存储有左孩子结点的指针、右孩子结点的指针。每个二叉链表节点存储一个二叉树节点，头指针则指向根节点

在采用链式存储时，二叉树的链式存储可以分为二叉链表和三叉链表的存储结构，如图所示

二叉树的遍历

二叉树是一个非线性结构，而对二叉树的遍历本质上是对一个非线性结构进行线性访问的过程。通过这种遍历，可以将二叉树这种非线性结构的数据转换为线性结构的数据，从而方便存储或处理等操作。

二叉树的遍历可以分为前序、中序、后序和层次遍历四种形式。这四种遍历方式产生的结果如图所示。

• 先序（前序）遍历：根左右
• 中序遍历：左根右
• 后序遍历：左右根
• 层次遍历：按层次，从上到下，从左到右

先序遍历

先序遍历二叉树的过程如下：

1. 访问根节点
2. 先序遍历左子树
3. 先序遍历右子树

中序遍历

中序遍历二叉树的过程如下：

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树

后序遍历

后序遍历二叉树的过程如下：

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根节点

层次遍历

层次遍历二叉树的过程如下：

1. 访问根节点（第一层）
2. 从左到右访问第2层的所有节点
3. 从左到右访问第3层的所有节点，依此类推，直到访问到第h层的所有节点。

二叉树的构造（通过遍历的序列）

单独一个序列无法确定一个二叉树。唯有根据先序遍历和中序遍历或后序遍历和中序遍历才能唯一确定一个二叉树。

必须是中序遍历搭配其他序列才能唯一确定一个二叉树。

根据先序遍历和中序遍历构造二叉树

根据先序遍历和中序遍历构造二叉树的过程如下：

1. 先序遍历的第一个节点就是根节点
2. 在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
3. 递归地对左子树和右子树进行构造

根据后序遍历和中序遍历构造二叉树

根据后序遍历和中序遍历构造二叉树的过程如下：

1. 后序遍历的最后一个节点就是根节点
2. 在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
3. 递归地对左子树和右子树进行构造

根据层序遍历和中序遍历构造二叉树

根据层序遍历和中序遍历构造二叉树的过程如下：

1. 层序遍历的第一个节点就是根节点
2. 在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树
3. 递归地对左子树和右子树进行构造

二叉排序树

二叉排序树（Binary Sort Tree）：又称为二叉查找树或二叉搜索树，是一种特殊的二叉树。

在二叉排序树中，每个节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

如图所示

平衡二叉树

平衡二叉树（Balanced Binary Tree）：又称为 AVL 树，是一种自平衡的二叉搜索树。

平衡二叉树是指该二叉树中的任意一个结点的左子树和右子树的高度之差的绝对值最多为 1。如果在插入或删除节点后，树的高度差超过了 1，就需要进行旋转操作来恢复平衡。

线索二叉树

性价比不高

最优二叉树（哈夫曼树）

哈夫曼树又称为最优二叉树，是一种带权路径长度最短的二叉树。

所谓树的带权路径长度，就是树中所有的叶子结点的权值乘上其到根结点的路径长度（若根结点为 0 层，叶子结点到根结点的路径长度为叶子结点的层数）。

基本概念

• 权：节点代表的值
• 路径：树中一个结点到另一个结点之间的通路
• 结点的路径长度：路径上的分支数目
• 树的路径长度：根节点到达每一个叶子节点之间的路径长度之和
• 结点的带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值

树的带权路径长度（WPL）：树中所有叶子节点的带权路径长度之和。

构造最优二叉树（哈夫曼算法）

如何构造最优二叉树？构造最优二叉树的哈夫曼算法步骤如下。

1. 假设有一组给定的权值集合 F，集合 F 里面包含一些权值节点。（比如{w₁, w₂, ..., wₙ}）。我们需要用这些权值节点构建一个最优二叉树。
2. 第一步：
   • 从集合F 中选择两个权值最小的节点。将它们作为左、右子树构造一棵新的二叉树，新树的根节点的权值为这两个节点的权值之和。
   • 把集合F 中删除这两个节点。并将新树根节点的权值加入到集合 F 中。
3. 第二步：
   • 从集合 F 剩下的节点中再次选择两个权值最小的节点，将它们作为新树的左、右子树，新树的根节点的权值为这两个节点的权值之和。
   • 把集合F 中删除这两个节点。并将新树根节点的权值加入到集合 F 中。
4. 重复上面步骤，直到所有节点都被合并为一棵树。

注意：

• 在构造新树的过程中，对于选出的两个权值节点，哪个作为左子树、哪个作为右子树并没有明确规定。这就导致：对于相同的一组权值，可能会构造出不同形状的最优二叉树。不过，不管形状如何变化，这些树的带权路径长度（WPL值）都是相同的，这是由权值本身决定的。
• 建议，每次选择两个权值最小的节点时，先选择权值较小的节点作为左子树，权值较大的节点作为右子树。

构造最优二叉树的示例、

哈夫曼编码

哈夫曼编码是一种基于字符出现频率的压缩编码方法。

构造最优二叉树（哈夫曼树）的过程如下：

1. 统计每个字符出现的频率，将字符和频率作为节点构建一个森林。
2. 从森林中选择两个频率最小的节点，将它们合并为一个新节点，新节点的频率为两个节点的频率之和。
3. 重复步骤 2，直到森林中只剩下一个节点，该节点就是最优二叉树的根节点。

哈夫曼编码的过程如下：

1. 从根节点开始，向左走为 0，向右走为 1，直到到达叶子节点。
2. 将从根节点到叶子节点的路径上的 0 和 1 组成的序列作为该叶子节点的编码。

图

图是比树结构更复杂的一种非线性结构。

• 在线性结构中，除首结点没有前驱、末尾结点没有后继外，一个结点只有唯一的一个直接前驱和唯一的一个直接后继。
• 在树结构中，除根结点没有前驱结点外，其余的每个结点只有唯一的一个前驱(双亲)结点和多个后继(子树)结点。
• 而在图结构中，图中任意两个结点之间都可能有直接的关系，所以图中一个结点的前驱结点和后继结点的数目是没有限制的。

图的介绍

图的定义

图 G 是由集合V和E构成的二元组，记作 G=(V,E),其中 V 是图中顶点的非空有限集合, E 是图中边的有限集合。

从数据结构的逻辑关系角度来看，图中任一顶点都有可能与其他顶点有关系，而图中所有顶点都有可能与某一顶点有关系。在图中，数据元素用顶点表示，数据元素之间的关系用边表示。

图的种类

• 无向图：图的顶点之间连接线是没有箭头的，不分方向。如图所示。
• 有向图：图的顶点之间连接线是箭头，表示从一个节点到另一个节点。如图所示。
• 无向完全图：在无向图中，若每个顶点都与其他顶点之间都有一条边相连，则称该图为无向完全图。无向完全图的n个结点的连线数为(n-1)+(n-2)+...+1 = n(n-1) / 2;
• 有向完全图：在有向图中，若每个顶点都与其他顶点之间都有两条有向边互相相连，则称该图为有向完全图。即顶点两两之间都有互通的两个箭头，则 n个节点有向完全图的的连线数为n(n-1)

图的基础概念

• 度：顶点的度是关联与该顶点的边的数目。若在有向图中，一个顶点的度为该顶点的出度和入度之和。
• 出度是以该顶点为起点的有向边的数目。
• 入度是以该顶点为终点的有向边的数目。
• 路径：存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的。
• 连通图：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。
• 连通分量：无向图G中的极大连通子图称为其连通分量。
• 强连通图：针对有向图。若有向图任意节个顶点间都互相存在路径即存在v到u，也存在u到v的路径，则称为强连通图。
• 强连通分量：有向图G中的极大连通子图称为强连通分量。
• 网：若图中的边带有权值，则称该图为网。

图的存储结构

图的基本存储结构有领接矩阵表示法和领接链表表示法两种。

领接矩阵表示法

邻接矩阵表示法是指用一个矩阵来表示图中顶点之间的关系。对于具有n个顶点的图G=(V,E)，其对应的邻接矩阵是一个n阶矩阵。该n阶矩阵需要满足下面关系。

简而言之

• 若无向图中的顶点i到顶点j有连线，则矩阵A[i][j]=1，否则为0。
• 若有向图中的顶点i到顶点j有连线，且连接方向为i->j，则矩阵A[i][j]=1，否则为0。

如图所示

• 若是无向图，其领接矩阵肯定是沿对角线对称的，只需要存储上三角或者下三角就可以了，而有向图则不一定对称
• 若是有向图，其领接矩阵不一定对称，因为有向图的边是有方向的，而无向图的边是无方向的。

邻接链表表示法

邻接链表表示法是指为图中的每一个顶点建立一个单链表。邻接链表中的结点有表结点(或边结点)和表头结点两种类型，如图所示。

示例

如图所示，一个有向图及其对应的邻接链表表示法。

• 先用一个一维数组将图中所有顶点存储起来。并用编号表示各个顶点。
• 而后，给一维数组的每个顶点元素，使用链表挂上和其有连线关系的顶点的编号和权值

图的遍历

图的遍历是指从图中的某个顶点出发，沿着某条路径对图中所有顶点进行访问且只访问一次的过程。

图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。

图的遍历要比树的遍历复杂得多。因为图的任一个顶点都可能与其余顶点相邻接，所以在访问了某个顶点之后，可能沿着某路径又回到该顶点上，为了避免对顶点进行重复访问，在图的遍历过程中必须记下每个已访问过的顶点。

图的遍历的方法主要分为深度优先搜索和广度优先搜索。

深度优先遍历

深度优先遍历：从任一顶点出发，遍历到底，直至返回。再选取任一其他节点出发，重复这个过程直至遍历完整个图。

如图所示

深度优先遍历的时间复杂度

• 当图使用邻接矩阵表示时，深度优先搜索遍历该图的时间复杂度为O(n^2^)
• 当图使用邻接链表来表示时，深度优先搜索遍历该图的时间复杂度为O(n+e)。其中n为节点数，e为边数。

广度优先遍历

广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

广度优先遍历的时间复杂度

广度优先遍历和深度优先搜索遍历图的时间复杂度相同，其不同之处仅仅在于对顶点的访问次序不同。

拓扑排序

暂无

数据运算

复杂度排序

复杂度是指算法执行所需要的时间和空间资源的量。分为时间复杂度和空间复杂度。

如图是一些不同数量级的复杂度，复杂度由小到大排列。

时间复杂度

算法的时间复杂度分析主要是分析算法重复执行的次数，即算法从开始到结束所需要的执行次数作为算法的时间度量。

一般不必要精确计算出算法的时间复杂度，只需要大致计算出响应的数量级即可，例如O(1)、O(n)、O(n^2^)等。

空间复杂度

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。

查找

查找是一种常用的基本运算。查找表是指同一类型的数据元素构成的集合。

查找分为静态查找和动态查找。

• 静态查找：分为顺序查找，二分查找等。
• 动态查找：分为二叉排序树查找，平衡二叉树查找等。

顺序查找

将待查的元素从头到尾与表中元素依次进行比较，如果存在，则查找成功；否则，查找失败。

• 顺序查找对于顺序存储结构和链式存储结构都适用。
• 顺序查找的平均查找长度为 (n+1)/2。
• 顺序查找的时间复杂度为 O(n)

折半查找（二分查找）

折半查找的基本思想

假设元素存储在一维数组A[1,…,n]中，并且表中的元素已经按递增方式排序的情况下。进行折半查找的方法是:

• 首先将待查元素Key 与表中间位置上(下标为 mid)的元素进行比较.
• 若 key = A[mid]，表示查找成功;
• 若 key > A[mid]，表示待查元素Key大于中间元素A[mid]，则说明待查元素Key只可能在后半个子表A[mid+1,…,n]中，下一步应在后半个子表中进行査找。
• 若 key < A[mid]，表示待查元素Key小于中间元素A[mid]，则说明待查元素Key只可能在前半个子表A[1,…,mid-1]中，下一步应在前半个子表中进行査找。
• 重复上面步骤，逐步缩小范围，直到查找成功或子表为空时失败为止。
• 每进行一次折半查找，数组规模减半。重复上面步骤，逐步缩小范围，直到查找成功或子表为空时为止。

折半查找的特点

• 折半查找的前提是查找表中的元素有序（一般是升序）。
• 折半查找的时间复杂度为：O(log2n) （以2为底的n的对数）
• 折半查找的平均查找长度为：O(log2n+1) （以2为底的n的对数加1）

哈希查找

哈希查找顾名思义是在哈希表上的查找。哈希查找的查找方式与哈希表有关。

什么是哈希表？

哈希表：是指根据提前设定的哈希函数和处理冲突的方法，将一个个元素映射到一个有限的连续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置。

示例

假设一个序列为{47、34、13、12、52、38、33、27、3}，哈希表长为 11，哈希函数为 Hash(key)=key mod 11，则有

• Hash(47) = 47 mod 11= 3，Hash(34) = 34 mod 11= 1，Hash(13) =13 mod 11= 2，
• Hash(12) = 12 mod 11= 4，Hash(52) = 52 mod 11= 8，Hash(38) = 38 mod 11= 5，
• Hash(33) = 33 mod 11= 0，Hash(27) = 27 mod 11= 6，Hash(3) =3 mod 11= 7。

对于各个元素产生的冲突，哈希函数可以采用线性探测法解决冲突，哈希地址和关键字的对应关系如表所示。

哈希函数的构造

常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。

对于哈希函数的构造，应解决好两个主要问题。

• 哈希函数应是一个压缩映像函数，它应具有较大的压缩性，以节省存储空间。
• 哈希函数应具有较好的散列性，虽然冲突是不可避免的，但应尽量减少。

要减少冲突，就要设法使哈希函数尽可能均匀地把关键字映射到存储区的各个存储单元，这样就可以提高查找效率。在构造哈希函数时，一般都要对关键字进行计算，且尽可能使关键字的所有组成部分都能起作用。

哈希表解决冲突的方法

解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。

常见的处理冲突的方法有以下几种。

• 开放定址法
• 再哈希法：就是使用多个哈希函数。即在发生地址冲突时，使用另一个哈希函数计算地址，直到冲 突不再发生。这种方法不易产生聚集现象，但增加了计算时间。
• 链地址法：链地址法(或拉链法)是一种经常使用且很有效的方法。它在哈希表的每一个记录中增加一个链域，链域中存放下一个具有相同哈希函数值的记录的存储地址。利用链域，就把若干个发生冲突的记录链接在一个链表内。

链地址法如图所示

排序

排序介绍

排序的基本概念

给定一个包含 n 个元素的集合，每个元素包含一个关键字，要求某个条件对该集合中的元素进行排序，使排序后的集合中的元素按顺序进行排列。

在排序过程中需要进行下列两种基本操作:

• 比较两个关键字的大小;
• 将记录从一个位置移动到另一个位置。

前一种操作对大多数排序方法来说都是必要的，后一种操作可以通过改变记录的存储方式来避免。

如图是各个排序的时间空间复杂度的对比

直接插入排序

直接插入排序是一种简单的排序方法。其时间复杂度为O(n^2^)。在排序过程中仅需要一个元素的辅助空间，空间复杂度为O(1)。

直接插入排序的具体做法是

在插入第 i 个记录时，R1,R2,...,Ri-1 均已排好序，这时将第 i 个记录依次与 Ri-1,...,R2,R1进行比较，找到合适的位置插入，插入位置及之后的记录依次向后移动。

例如：43 55 70 30 -> 30 43 55 70

直接插入排序在最好情况下的时间复杂度为 O(n)，在最坏情况下的时间复杂度为 O(n^2)

希尔排序

希尔排序又称为“缩小增量排序”，它是对直接插入排序方法的改进。

希尔排序的基本思想是:先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

希尔排序的具体做法是:

• 先选择第一个增量d1，把序列的全部记录按增量d1进行分组，即序列中序号为d1整数倍的记录为一组。然后在各组内进行直接插入排序;
• 然后取第二个增量d2 （d2 < d1）,重复上述分组和排序工作。
• 依此类推，直到最后选择的增量为1时。此时即有记录放在同一组进行直接插入排序为止。

如图所示

简单选择排序

假设给定一个n个记录的集合。则简单选择排序的方法是:

每一趟从待排序的数据元素中选出最小的元素，顺序放在待排序数列的最前面，直到全部待排 序的数据元素全部排完。简单选择排序的时间复杂度为 O(n^2)。

例如假设一个序列为

• 第一趟从序列 {43, 55, 70, 30} 中选出最小值 30 与序列中的第一个元素交换。此时序列为 30 55 70 45
• 第二趟从序列 {55, 70, 45} 中选出最小值 45 与序列中第二个元素交换：30 45 70 55
• 第三趟从序列 {55, 70} 中选出最小值 55 与序列中第三个元素交换：30 45 55 70
• 依此类推

冒泡排序

假设给定一个n个记录的集合。则进行冒泡排序的方法是:

1. 首先将第一个记录和第二个记录进行比较，若为逆序，则交换这两个记录的值（小的在前面，大的在后面），然后比较第二个记录和第三个记录，依此类推，直到第n-1个记录和第n个记录的关键字比较过为止。上述过程称为第一趟冒泡排序，其结果是最大的记录被交换到第n个记录的位置上。（即最大的记录就被移动到集合尾部了。）
2. 然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作（即对第1个记录到第n-1个记录进行比较交换，因为最大的记录已经被移动到了尾部，所以不需要再比较交换了）。其结果是次大的记录被交换到第n-1个记录的位置上，即倒数第二个位置。
3. 最多进行n-1 趟冒泡排序，则所有记录按照从小到大的顺序进行排列。
4. 若在某趟冒泡排序过程没有进行相邻位置的元素交换处理，表示当前集合已经有序，则可结束排序过程。

冒泡排序由于本质是通过集合中的相邻元素（i 与 i-1）之间的比较和交换，将排序较小的元素逐渐从集合前面移向集合后面。整个过程像水底的气泡逐渐向上冒，由此而得名冒泡排序。

• 冒泡排序的时间复杂度为 O(n^2^)。在排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为0(1)。

快速排序

快速排序是对冒泡排序的一种改进。

快速排序的基本思想是:通过一趟排序将待排的记录划分为独立的两部分，称为前半区和后半区，其中前半区中记录均不大于后半区记录，然后再分别对这两部分记录继续进行快速排序，从而使整个序列有序。

如图所示为快速排序的示例

常见排序对比