六、数据结构与算法基础

雨点打透心脏的1/2处 2023-09-26 15:32 28阅读 0赞

#### 数据结构与算法基础 ####

*  6.1 数组与矩阵
 *   *  1、数组
     *  2、矩阵
 *  6.2 线性表和广义表
 *   *  1、线性表
     *   *  栈和队列
     *  2、广义表
 *  6.3 树、二叉树和图
 *   *  1、树和二叉树
     *  2、图
 *  6.4 算法基础和查找排序
 *   *  1、算法基础
     *  2、查找
     *  3、排序

*  这一部分的内容是非常重要的，在上午综合会考到，也会在下午设计中考到。
 *  包含的内容主要有数组与矩阵、线性表、广义表、树与二叉树、图、排序查找、算法基础及常见算法，  
    **数组与矩阵：** 主要是数组下标转化的问题，稀疏矩阵、上三角下三角矩阵；  
    **线性表：** 主要是两种基本数据结构栈和队列，它们的基本特性和相关应用每次都会考到。  
    *广义表：* 了解基本的概念和操作，偶尔考到。  
    **树和二叉树：** 基本特性及解决的问题，一些有特点的二叉树的基本知识，每次必考。  
    *图：* 了解基本概念。  
    **排序与查找：** 排序和查找的算法。算法的特性和操作流程，时间复杂度空间复杂度等问题。非常重要。  
    **算法基础和常见算法：** 算法的基本概念和常见算法的基本知识。

## 6.1 数组与矩阵 ##

### 1、数组 ###

*  主要了解存储地址的计算、以及在二维数组中按行存储和按列存储的区别。  
    ![在这里插入图片描述][ddaca1f8dfdf45f59ac979d4dd314816.png]  
    某个数组变量的存储地址是以数组首地址为偏移来算的。上图中的len表示每个元素所占存储空间。
    
    二维数组在计算机中都是以一维数组的形式顺次存储。按行存储就是一行一行来存，第二个元素的下标是\[0\]\[1\]；按列存储就是一列一列来存，第二个元素的下标是\[1\]\[0\]。
    
    例题： 已知5行5列的二维数组a中各元素占两个字节，求元素a\[2\]\[3\]按行优先存储的存储地址？  
    根据上面公式可得：(2×5+3)×2。

### 2、矩阵 ###

*  主要是计算稀疏矩阵中某一个元素对应的以为数组的下标，考试中可以通过公式计算也可以用代入法排除。  
    ![在这里插入图片描述][061fd1264fa24a1ca71e142afff02770.png]  
    稀疏矩阵：大部分的元素都为0。所以为了节省空间，只存有效数据。
    
    例题：  
    ![在这里插入图片描述][c8e7ea04d2a945e1ba2d94e8b9b071e5.png]  
    **题解：** 首先代入A\[0\]\[0\]，它要存的是位置是M\[1\]，可以排除B和C；再代入A\[1\]\[1\]，它要存的位置是M\[3\]，排除D。答案就是A。

## 6.2 线性表和广义表 ##

*  **数据结构**
    
    就是计算机存储以及组织数据的方式。选择不同的数据结构运行效率不同。
    
    从逻辑层面上可分线性和非线性结构，非线性又包含了树和图。

### 1、线性表 ###

*  是线性结构的基本表现，有两种存储方式，分别是顺序存储即顺序表，链式存储即链表。  
    ![在这里插入图片描述][480c66c51b0c4138aa687614eabaf1b7.png]
 *  **顺序表：** 就是开辟了连续的空间，采用一维数组的方式存储，实际上就是数组。
 *  **链表：** 每一个存储单元包含了存数据的地方和存指针的地方，是离散的不连续的空间，通过指针来连接。链表又分为单链表、循环链表、双向链表。  
    **单链表：** 指针是单向的，头结点即头指针指向第一个元素，第一个指向第二个，以此类推。又分为有头结点和无头结点的，头结点不存任何信息，有头结点的好处是让所有结点的操作方式一致。
    
    **循环链表：** 尾指针指向头结点。如果当前指针在尾元素，再定位任何一个元素的时候可以继续next往下走，不用再重新定位到头结点开始。
    
    **双向链表：** 每一个结点都有两个指针，一个指向它的前驱结点，另一个指向它的后继结点。这样就可以双向移动。
    
    **链表的操作：** 考试主要是单链表的删除和插入结点的操作。![在这里插入图片描述][0ba40f2b85ef4a288bd8910d9595d3a0.png]  
    **单链表删除结点：** p->next=q->next。  
    **单链表插入结点：** s->next=p->next，p->next=s。
 *  **顺序存储和链式存储的区别：**  
    ![在这里插入图片描述][d61a3d28dffd490aa8cd85cd91409c94.png]
    
     *  存储密度：顺序存储是在一段连续的空间上存数据，没有空间上的浪费；而链式存储每个结点除了存数据还有指针，空间利用率较低，所以顺序存储更优。
     *  容量分配：顺序存储要事先确定需要多少空间，而链式存储可以动态分配空间，灵活性较高，所以链式存储更优。
     *  查找：在内容无序的情况下，它们的时间复杂度是一样的，而在内容有序涉及到二分查找的情况下顺序存储更优。
     *  读取：顺序表更优，如果读取第n个元素的时候，顺序存储直接读取a\[n-1\]就可以了，而链式存储要定位到头结点，头结点指向第一个元素的话，要一直next到第五个元素才能读取。
     *  插入：链表更优，链表插入时只需对插入位置的结点的指针进行操作，而顺序表需要把插入元素后所有的元素都向后移一位再插入元素。
     *  删除：其实和插入是相同的，链式存储更优。

#### 栈和队列 ####

![在这里插入图片描述][0e2e930bbb9f4c9b847eaba3c954754d.png]

*  **队列：** 遵循先进先出的原则，能从队尾和队头两端操作。
    
    **循环队列：** 就是把队头和队尾连起来。
    
     *  队空条件是头指针head和尾指针tail指向同一个空间，即head=tail。
     *  队满条件是尾指针的下一个元素是头指针，即(tail+1)%size=head。size队长表示队列最多存储的元素个数。
     *  给出队头和队长，存了几个元素计算队尾的时候也是通过取余来求。例题： 一个总的空间数为5的，下标是0-4的循环队列，队头在4的位置，顺时针存了3个元素，那么队尾的位置就是(4+3)%5=2。
 *  **栈：** 遵循先进后出的原则，只能从栈顶一端操作。
    
    习题： 元素按照a、b、c的顺序入栈，请尝试写出所有可能的出栈序列。  
    题解：同一个入栈顺序不同的出栈顺序有不同的出栈序列。  
    a入栈就出栈，bc入栈，得到acb；  
    a入栈就出栈，b入栈就出栈，c入栈，得到abc；  
    ab入栈就出栈，c入栈，得到bac;  
    abc入栈，得到cba。
    
    例题： 栈和队列结合变化应用的情况。  
    ![在这里插入图片描述][0fdc62de8ad449ea9c79e07378093e78.png]  
    题解：题目要求依次输入，所以e1和e2在出队序列中必须是相邻的，所以选择D。考试中基本都是将栈和队列结合或者演变之后进行考察。

### 2、广义表 ###

![在这里插入图片描述][806225cfd38c474e9290a7709930fee1.png]

*  **表头：** 最外层的第一个表元素。
 *  **表尾：** 除了第一个元素外的其它所有元素。
    
    例1中广义表的长度为3，深度为2。例2中操作为head(head(tail(LS1)))。

## 6.3 树、二叉树和图 ##

### 1、树和二叉树 ###

*  **基本概念**  
    ![在这里插入图片描述][92fd13522d7342bb8e856dd1e607e23f.png]  
    结点的度：孩子结点数。比如上图二叉树中结点1的度为2，结点3的度为1，结点7的度为0。  
    树的度：所有结点度数最高的度。上图二叉树中树的度为2。  
    叶子结点：没有孩子结点的结点。上图中结点4578。  
    分支结点：非叶子结点，上图中结点1236。  
    内部结点：除根结点的非叶子结点，上图中结点236。  
    父结点和子结点：相对而言的。比如上图中的对于结点2它的父结点是结点1，子结点是结点45。  
    兄弟结点：同一个父结点下的子结点。上图中的结点4和5。  
    层次：上图中的树的层数为4。
 *  **特殊的二叉树**  
    ![在这里插入图片描述][3c9c1efc28cd4761a8820d78474af28c.png]
    
     *  **二叉树：** 每个结点至多只有两颗子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。
     *  **满二叉树：** 在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子都在同一层上的二叉树。
     *  **完全二叉树：** 对于一棵具有n个节点的二叉树按层次编号，如果编号为i（1<=i<=n）的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同，其特点是叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
 *  **二叉树的重要特性**  
    ![在这里插入图片描述][1c1b4c1b22ce4f05bca8b8a28cd971b7.png]
 *  **二叉树的遍历**
    
     *  前序遍历：先访问根结点，再访问左子树，最后访问右子树（根左右）。
     *  中序遍历：先访问左子树，再访问根结点，最后访问右子树（左根右）。
     *  后序遍历：先访问左子树，再访问右子树，最后访问根结点（左右根）。
     *  层次遍历：按层次一层一层从左到右遍历。  
        ![在这里插入图片描述][3b73d1a744654a5da011a98c9eec8059.png]  
        习题： 上图中二叉树各种方式的遍历结果：  
        前序遍历：12457836。  
        中序遍历：42785136。  
        后序遍历：48752631。  
        层次遍历：12345678。  
        注： 二叉树遍历的时候分支结点要嵌套访问。
 *  **反向构造二叉树**
    
     *  知道一定的二叉树的遍历序列，反向构造推出二叉树。知道前中序或者中后序都能构造出二叉树，只知道前后无法构造出二叉树。考试中一般给出两种序列，构造二叉树或者求另一种遍历序列。
     *  例题：  
        ![在这里插入图片描述][f026116666ed44888410a108862a8f79.png]  
        构造的二叉树如下：  
        ![在这里插入图片描述][c88b1ac1cce14bd1afd2cf209c9b92f0.png]  
        注： 通过前后遍历序列可以确定根结点，通过中序遍历可以确定左右子树的结点。
 *  **树转二叉树**  
    ![在这里插入图片描述][479cf50834a74b2b9ab0db40f6b2c672.png]  
    **转化原则：** 一个结点的孩子结点都会成为该结点的左子树结点，它的兄弟结点都会成为该结点的右子树结点。  
    **简单方法：** 多个孩子结点只保留第一个，兄弟结点直接平连起来，最后把这棵树做一下旋转就得到最终的二叉树。
 *  **查找二叉树**  
    **定义：** 特殊的二叉树，把所有左子树小于根结点，右子树大于根结点的数叫查找二叉树，又叫排序二叉树。  
    **特点：** 提高查找效率。  
    **插入和删除操作：**  
    ![在这里插入图片描述][8402469c23aa43ed8162f317d650cf05.png]
 *  **最优二叉树**
    
     *  又叫哈夫曼树，是一种用于哈夫曼编码的工具，而哈夫曼编码是一种无损的压缩编码方式，缩短编码长度节省存储空间和传输带宽。
     *  **基本概念**  
        树的路径长度：所有叶子结点的路径长度和。  
        权：叶子结点有一个数值，代表了某一种字符出现的频率。  
        带权路径长度：根结点到叶子结点的路径长度再乘以结点的权值。  
        树的带权路径长度（WPL，树的代价）：所有叶子结点的带权路径长度和。  
        基本原理：构造哈夫曼树，让树的带权路径长度最短。
     *  **构造过程**  
        例题：  
        ![在这里插入图片描述][cf12249796eb4243a2e37fbd1b0ce5c3.png]  
        先在权值数列中找到最小的两个数合并，以它们为左右子树、它们的和为根结点构造新的二叉树，然后从数列中删除它们，并将它们的和加入数列，重复以上步骤直至数列中最后只有一个数为止。  
        构造的树的带路径长度：WPL=5×5+3×5+7×4+14×3+29×2+8×3+11×3+23×2。
 *  **线索二叉树**  
    ![在这里插入图片描述][d541feba404947db80b522a8c2e64026.png]
    
     *  **线索二叉树**  
        在二叉树的基础上，添加一些虚线即线索箭头把很多结点串起来。
     *  **为什么要有线索二叉树**  
        在二叉树中有很多结点是处于空闲的状态，有很多指针是空的没有利用起来。所以就通过这些空闲的指针来方便遍历。
     *  **线索二叉树的表示**  
        前序线索二叉树：线索箭头是按前序序列生成的。  
        中序线索二叉树：线索箭头是按中序序列生成的。  
        后序线索二叉树：线索箭头是按后序序列生成的。
     *  **二叉树转线索二叉树**  
        左子树的结点的指针是指向当前结点遍历序列的前一个结点，右子树结点的指针是指向当前结点遍历序列的后一个结点。
 *  **平衡二叉树**  
    ![在这里插入图片描述][06271cd0090a4204bc8df919a7efa137.png]
    
     *  **提出原因：** 使二叉树更加平衡合理，提高查找效率。
     *  **定义：** 任意结点的左右子树深度相差不超过1，每个结点的平衡度只能为-1、0或1，也叫平衡树（AVL树）。结点的平衡度是左与右子树深度的差，也叫平衡因子。
     *  **构造过程及动态平衡调整**  
        在二叉排序树中插入新结点，从插入点往回找第一个不平衡点即平衡，调整以该结点为根的子树，只要将最小不平衡子树调整平衡，则其它祖先结点都会平衡。
        
        调整最小不平衡子树A可分为四种情况：  
        LL型：在A的左孩子的左子树中插入导致不平衡。A的左孩子结点右上旋。  
        ![ef2efaa7c05240ea9979d371e61ff83e.png][]  
        RR型：在A的有孩子的右子树中插入导致不平衡。A的右孩子结点左上旋。  
        ![在这里插入图片描述][f75be5dbd03a494f8725d538e8c6ccc5.png]  
        LR型：在A的左孩子的右子树中插入导致不平衡。A的左孩子的右孩子先左上旋，再右上旋。  
        ![在这里插入图片描述][a49051c72d7944fda9c0c8e576658664.png]  
        RL型：在A的右孩子的左子树中插入导致不平衡。A的右孩子的左孩子先右上旋，再左上旋。  
        ![在这里插入图片描述][74905ae25bf04e31a1002fad3ddcc27a.png]  
        例题： 依次输入数据\{100，90，80，60，70，50，120，110，150，87\}构造平衡二叉树。  
        ![在这里插入图片描述][e74a6ac458e84324bb447f5be346eed5.png]  
        ![在这里插入图片描述][0aae070aa4374df7a70cf404390b11eb.png]  
        ![在这里插入图片描述][3ddb2711023943f39d9b96c6f49c4ee2.png]  
        注： 以上四种情况的图示和例题转自链接：[原文][Link 1]。

### 2、图 ###

*  在考试中考察的频率较低，主要是了解图的一些基本概念。
 *  **基本概念**  
    ![在这里插入图片描述][70f067eb8f9a45f88377d80e438f517b.png]  
    **无向图和有向图：** 根据顶点之间的关系即边是否有方向性可将图分为无向图（上图中左图）和有向图（上图中右图）。  
    **完全图：** 在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图；在有向图中，若每对顶点之间有两条有向边相连，则称该图为完全图。
 *  **图的存储**
    
     *  **邻接矩阵**  
        ![在这里插入图片描述][78a742b7f8944c2ebafb96c6f0eb16ac.png]  
        特点：按对角线矩阵是对称的， 如果要节省存储空间，可以只存上三角或下三角。
     *  **邻接表**  
        ![在这里插入图片描述][53ea423384cc4cb080b34224b88e170b.png]  
        用一个数组记录各个结点，再用一个链表来记录每个顶点可以到的顶点情况。
 *  **图的遍历**  
    ![在这里插入图片描述][0f26ecdd3d844378adc03c7c076ab94c.png]
    
     *  **深度优先（DFS）：** 根据线索一层一层深入下去，只有无法深入才退回来进入下一个分支。
     *  **广度优先（BFS）：** 把一个结点所相邻的所有结点访问完，再继续下一个层次。
 *  **拓扑排序**  
    ![在这里插入图片描述][71b019022cb44b6eba1a66e22e3e9824.png]  
    拓扑排序实际上是用一个序列来表示一个图中哪些事件可以先执行，哪些事件可以后执行。  
    同一个AOV网络可能有多个不同拓扑序列，在考试中往往是问下列哪一个不是该图的拓扑序列。
 *  **图的最小生成树**  
    树和图的最大区别是在于树没有环路。图的最小生成树就是把这个图当中很多的边去掉，只留下权值较小的边，从而使留下来的树所有边的权值和最小。
    
    求最小生成树有两种常用算法，普里姆算法和克鲁斯卡尔算法。
    
     *  **普里姆算法**  
        从任意结点出发，寻找与其相连的所有边，在这些边中选权值最小的边，且这个边必须有一个顶点没被访问过（不能形成环路），将该边和顶点加入到生成树中，再找与当前生成树集合相连的所有边，重复以上步骤直至所有点都连接完成。
     *  **克鲁斯卡尔算法**  
        将图中的所有边按权重大小（每条边上的权值）排序，每次选权重最小边和两个顶点加入生成树中，但不能形成环路。重复该步骤直至所有的结点都连接完成。
        
        例题： 求下图中图的最小生成树。  
        ![在这里插入图片描述][f6ac697567f54f8084910c6db38e5849.png]  
        了解 普里姆算法主要对结点操作常用于稠密图，克鲁斯卡尔算法主要对边操作常用于稀疏图，都是贪心算法。

## 6.4 算法基础和查找排序 ##

### 1、算法基础 ###

*  **算法特性**  
    ![在这里插入图片描述][1fdd4fd325f74f10b2e6be30aac57ed1.png]
 *  **算法的复杂度**  
    算法的复杂度主要有两个维度，时间复杂度和空间复杂度。  
    ![在这里插入图片描述][23f49c1d0fd647ca98c54fddc1b85488.png]  
    在考试中主要会在下午设计题中考察时间复杂度，空间复杂度考的较少。
    
     *  **时间复杂度**  
        用来衡量算法执行大概需要耗费多长时间，时间的量级的情况。在常见时间复杂度的度量中，像log2n这种对数形式的主要是在树的处理中会经常用到。
     *  **空间复杂度**  
        指执行过程中要用到的临时空间或交换空间的数量。这部分内容我们会在后面排序算法提到。

### 2、查找 ###

主要是顺序查找和二分查找。

*  **顺序查找**  
    ![在这里插入图片描述][7b4954ca9a44473b8517053b7ba9465c.png]  
    逐个比对，找到一致的关键字就查找成功，如果把所有的元素都比较完没有发现匹配的就查找失败。从上面的平均查找长度可以得到顺序查找的时间复杂度为O(n)。
 *  **二分查找**  
    顺序查找比较简单，但是效率较低，为了提高查找效率，就出现了二分查找。  
    ![在这里插入图片描述][775e26b218bf471cad216c74bb26a0e3.png]  
    与查找二叉树的思想类似，并不是所有的序列都能用二分查找法，它的前提是查找的序列是有序排列的。
    
    例题：  
    ![在这里插入图片描述][c15c8c67d51a42e8b602e0a9b4b340c4.png]  
    二分查找的次数和时间复杂度的情况如下：  
    ![在这里插入图片描述][8912ac77cc654f8f9870c602292996c4.png]
 *  **散列表**  
    散列表是一种按内容存储的机制。  
    ![在这里插入图片描述][4eb2e150d38d49c3b6a1943a257b9614.png]  
    例题：  
    ![在这里插入图片描述][8925e433e9ec4c7fbddfb651a8584dba.png]  
    通过散列函数求元素的存储位置时，就会出现冲突，常用的有两种处理机制，线性探测法和伪随机数法。主要介绍线性探测法。  
    **线性探测法**  
    ![在这里插入图片描述][4e7f4e23f0bd4b22adf576761bfa6a05.png]  
    如果当前空间被占了，就把它顺次放到下一个单元。

### 3、排序 ###

*  是数据结构与算法中非常重要的知识点，考试必考，上午题和下午题都可能会出现。
    
    **稳定与不稳定排序：** 按值相同的数经过排序算法处理后是否保持原来的先后顺序，分为稳定和不稳定排序。比如说分数的排名，总分一样的情况下，可能已经有一个其它指标进行初步的排序，然后再在相同的情况下择优。
    
    **内排序和外排序：** 内排序指在内存中进行的排序，外排序会涉及到外部的存储空间。
    
    **排序算法分类：**  
    插入类排序：直接插入排序和希尔排序。直接插入排序较简单，但比希尔排序效率低。  
    交换类排序：冒泡排序和快速排序。快速排序效率较高，过程较复杂。  
    选择类排序：简单选择排序和堆排序。堆排序效率很高，但过程也很复杂。  
    归并排序和基数排序。
    
    考试中考察较多的往往是希尔排序、快速排序、堆排序这些复杂的排序算法，其它的相对考察较少且简单。
 *  **直接插入排序（插入排序）**  
    ![在这里插入图片描述][660b7c7d46d349cdb2964270f8f08d18.png]  
    ![在这里插入图片描述][0460371702464d35a5ea0accc9ce213a.png]  
    基本思想：通过构建有序序列（一般是从小到大），对于未排序数据，在已排序序列中从后往前扫描，找到相应位置插入。（有序序列是从小到大就在比它小的元素后面插入，如果待插入元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
    
    Java代码实现：
    
        public class InsertSort implements IArraySort {
              
        
            @Override
            public int[] sort(int[] sourceArray) throws Exception {
              
                // 对 arr 进行拷贝，不改变参数内容
                int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        
                // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
                for (int i = 1; i < arr.length; i++) {
              
        
                    // 记录要插入的数据
                    int tmp = arr[i];
        
                    // 从已经排序的序列最右边的开始比较，找到比其小的数
                    int j = i;
                    while (j > 0 && tmp < arr[j - 1]) {
              
                        arr[j] = arr[j - 1];
                        j--;
                    }
        
                    // 存在比其小的数，插入
                    if (j != i) {
              
                        arr[j] = tmp;
                    }
        
                }
                return arr;
            }
        }
 *  **希尔排序**  
    ![在这里插入图片描述][449b7884256d40aca6b92d981dc287cb.png]  
    基本思想：是插入排序的一种更高效的改进版本。先将整个待排序序列分割成若干子序列分别进行直接插入排序，等整个序列基本有序时，再对整个序列进行一次直接插入排序。（第一趟排序选择增量一般取整个序列长度的一半，第二次的是第一次的一半，以此类推，并且每次增量取奇整数）
    
    Java代码实现：
    
        public static void shellSort(int[] arr) {
              
            int length = arr.length;
            int temp;
            for (int step = length / 2; step >= 1; step /= 2) {
              
                for (int i = step; i < length; i++) {
              
                    temp = arr[i];
                    int j = i - step;
                    while (j >= 0 && arr[j] > temp) {
              
                        arr[j + step] = arr[j];
                        j -= step;
                    }
                    arr[j + step] = temp;
                }
            }
        }
 *  **直接选择排序（选择排序）**  
    ![在这里插入图片描述][56c148685cf7486ea9c6deb7ac8a3e69.png]  
    基本思想：首先在未排序序列中找出最小的元素放大排序序列的起始位置，再从剩余未排序序列找到最小的元素放到已排序序列的末尾。
    
    Java代码实现：
    
        public class SelectionSort implements IArraySort {
              
        
            @Override
            public int[] sort(int[] sourceArray) throws Exception {
              
                int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        
                // 总共要经过 N-1 轮比较
                for (int i = 0; i < arr.length - 1; i++) {
              
                    int min = i;
        
                    // 每轮需要比较的次数 N-i
                    for (int j = i + 1; j < arr.length; j++) {
              
                        if (arr[j] < arr[min]) {
              
                            // 记录目前能找到的最小值元素的下标
                            min = j;
                        }
                    }
        
                    // 将找到的最小值和i位置所在的值进行交换
                    if (i != min) {
              
                        int tmp = arr[i];
                        arr[i] = arr[min];
                        arr[min] = tmp;
                    }
        
                }
                return arr;
            }
        }
 *  **堆排序**
    
     *  堆的基本概念
        
        堆：所有的孩子结点大于父结点即小顶堆，所有的孩子结点小于父结点即大顶堆。  
        ![在这里插入图片描述][3bbe9f1c874c468a86abadd1e65abf1a.png]
        
        基本思想：先建立一个堆，然后取走堆顶，再将剩下的序列重建堆，再取走堆顶，以此类推直到所有 元素都排序完成。  
        ![在这里插入图片描述][05728284f4ad479f9f19a17cee8af5f4.png]
        
        例题：  
        ![在这里插入图片描述][f39ebfddd0c343ff8686cc95a982b19a.png]  
        初建堆首先顺次构造完全二叉树，然后再调整为堆。调整方法：从最后一个非叶子结点开始，看它是否大于它的两个孩子（建大顶堆，小顶堆相反），如果大于不变动，否则就把孩子中的最大值与该结点交换，最后调整完根结点才是初建堆。后面的调整过程通过下图中例题演示。  
        ![在这里插入图片描述][ba9f23ad89c1495a82ccde3795760c02.png]  
        序列初建已经是堆了，然后取走堆顶元素， 把堆尾即完全二叉树的最后一个结点（按层序顺次编号）作为新的堆顶元素，现在再进行堆的调整（与上面初建堆中调整过程一样）。调整完成后重复以上步骤直到完成整个序列的排序。非常适于在很多个数据中找出排在前几的元素（每次高效选出一个元素）。
        
        Java代码实现：
        
            public class HeapSort implements IArraySort {
                    
                @Override
                public int[] sort(int[] sourceArray) throws Exception {
                    
                    // 对 arr 进行拷贝，不改变参数内容
                    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
                    int len = arr.length;
                    buildMaxHeap(arr, len);
                    for (int i = len - 1; i > 0; i--) {
                    
                        swap(arr, 0, i);
                        len--;
                        heapify(arr, 0, len);
                    }
                    return arr;
                }
                private void buildMaxHeap(int[] arr, int len) {
                    
                    for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
                    
                        heapify(arr, i, len);
                    }
                }
                private void heapify(int[] arr, int i, int len) {
                    
                    int left = 2 * i + 1;
                    int right = 2 * i + 2;
                    int largest = i;
                    if (left < len && arr[left] > arr[largest]) {
                    
                        largest = left;
                    }
                    if (right < len && arr[right] > arr[largest]) {
                    
                        largest = right;
                    }
                    if (largest != i) {
                    
                        swap(arr, i, largest);
                        heapify(arr, largest, len);
                    }
                }
                private void swap(int[] arr, int i, int j) {
                    
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
 *  **冒泡排序**  
    ![在这里插入图片描述][e91a513473be4fe5b879b3a55503bf91.png]  
    基本思想：每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。而每一趟都需要从第一位开始进行与相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。
    
    Java代码实现：
    
        public class BubbleSort implements IArraySort {
              
        
            @Override
            public int[] sort(int[] sourceArray) throws Exception {
              
                // 对 arr 进行拷贝，不改变参数内容
                int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        
                for (int i = 1; i < arr.length; i++) {
              
                    // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
                    boolean flag = true;
        
                    for (int j = 0; j < arr.length - i; j++) {
              
                        if (arr[j] > arr[j + 1]) {
              
                            int tmp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = tmp;
        
                            flag = false;
                        }
                    }
        
                    if (flag) {
              
                        break;
                    }
                }
                return arr;
            }
        }
 *  **快速排序**  
    ![在这里插入图片描述][075061f63b04496c83e676a75ef290d1.png]  
    基本思想：从数列中挑一个元素作基准（为了方便一般选第一个数），设置两个指针left和right，分别指向数列的第一个元素和最后一个元素，right指针从右往左扫描，找到比基准小的元素交换，left指针往右移一个开始从左往右扫描，找到比基准大的元素交换，right指针往左移一个又开始从右往左扫描，找比基准小的元素交换，重复以上步骤直到基准左边所有数据比基准都小，右边所有数据比基准都大时一趟排序完成。通过一趟排序将要排序的数据分割成独立的两部分，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。
    
    Java代码实现：
    
        public class QuickSort implements IArraySort {
              
        
            @Override
            public int[] sort(int[] sourceArray) throws Exception {
              
                // 对 arr 进行拷贝，不改变参数内容
                int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        
                return quickSort(arr, 0, arr.length - 1);
            }
        
            private int[] quickSort(int[] arr, int left, int right) {
              
                if (left < right) {
              
                    int partitionIndex = partition(arr, left, right);
                    quickSort(arr, left, partitionIndex - 1);
                    quickSort(arr, partitionIndex + 1, right);
                }
                return arr;
            }
        
            private int partition(int[] arr, int left, int right) {
              
                // 设定基准值（pivot）
                int pivot = left;
                int index = pivot + 1;
                for (int i = index; i <= right; i++) {
              
                    if (arr[i] < arr[pivot]) {
              
                        swap(arr, i, index);
                        index++;
                    }
                }
                swap(arr, pivot, index - 1);
                return index - 1;
            }
        
            private void swap(int[] arr, int i, int j) {
              
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        
        }
 *  **归并排序**  
    ![在这里插入图片描述][78ddc05c4de34fda903ac82787f413bf.png]  
    基本思想：先将无序序列利用二分法划分为子序列，直至每个子序列只有一个元素(单元素序列必有序)，然后再对有序子序列逐步(两两)进行合并排序。合并方法是循环的将两个有序子序列当前的首元素进行比较，较小的元素取出，置入合并序列的左边空置位，直至其中一个子序列的最后一个元素置入合并序列中。最后将另一个子序列的剩余元素按顺序逐个置入合并序列尾部即可完成排序。
    
    下图是合并两个有序序列的过程：  
    ![在这里插入图片描述][522df5eae3744851ba8cf44695dc8f76.png]  
    Java代码实现：
    
        public class MergeSort implements IArraySort {
              
        
            @Override
            public int[] sort(int[] sourceArray) throws Exception {
              
                // 对 arr 进行拷贝，不改变参数内容
                int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        
                if (arr.length < 2) {
              
                    return arr;
                }
                int middle = (int) Math.floor(arr.length / 2);
        
                int[] left = Arrays.copyOfRange(arr, 0, middle);
                int[] right = Arrays.copyOfRange(arr, middle, arr.length);
        
                return merge(sort(left), sort(right));
            }
        
            protected int[] merge(int[] left, int[] right) {
              
                int[] result = new int[left.length + right.length];
                int i = 0;
                while (left.length > 0 && right.length > 0) {
              
                    if (left[0] <= right[0]) {
              
                        result[i++] = left[0];
                        left = Arrays.copyOfRange(left, 1, left.length);
                    } else {
              
                        result[i++] = right[0];
                        right = Arrays.copyOfRange(right, 1, right.length);
                    }
                }
        
                while (left.length > 0) {
              
                    result[i++] = left[0];
                    left = Arrays.copyOfRange(left, 1, left.length);
                }
        
                while (right.length > 0) {
              
                    result[i++] = right[0];
                    right = Arrays.copyOfRange(right, 1, right.length);
                }
        
                return result;
            }
        
        }
 *  **基数排序**  
    ![在这里插入图片描述][ee9963e91c564832b0cc85ba5e62ebc5.png]  
    基本思想：借助多关键字排序的思想对单逻辑关键字排序的方法，或拆成多个关键字（多个维度）再排序，如上图中的先排个位，再排十位和百位，如果相同用链接的形式表示（直接排在后面）。相当于它把一个数列每一个元素拆成了三个不同的关键字，对三个不同的关键字排序最后得到相应的结果。
    
    在考试中考察较少，所以代码实现不做介绍。
 *  **排序算法的区别**  
    ![在这里插入图片描述][9ea2e492e0db4b5cbec2376c205d7cc6.png]  
    时间复杂度以n2为主，其次是logn对数形式的都会涉及到二分或者树。空间复杂度基本都是常数没有用到额外的空间。以上八种排序算法稳定的有插入、冒泡、归并、基数；不稳定的有希尔、选择、堆、快速。
 *  注： 排序一般都是从小到大，如果是从大到小思路过程其实都是一样的。算法的基本思想和Java代码实现主要都是菜鸟教程上的，链接：[菜鸟教程][Link 2]。

[ddaca1f8dfdf45f59ac979d4dd314816.png]: https://img-blog.csdnimg.cn/ddaca1f8dfdf45f59ac979d4dd314816.png
[061fd1264fa24a1ca71e142afff02770.png]: https://img-blog.csdnimg.cn/061fd1264fa24a1ca71e142afff02770.png
[c8e7ea04d2a945e1ba2d94e8b9b071e5.png]: https://img-blog.csdnimg.cn/c8e7ea04d2a945e1ba2d94e8b9b071e5.png
[480c66c51b0c4138aa687614eabaf1b7.png]: https://img-blog.csdnimg.cn/480c66c51b0c4138aa687614eabaf1b7.png
[0ba40f2b85ef4a288bd8910d9595d3a0.png]: https://img-blog.csdnimg.cn/0ba40f2b85ef4a288bd8910d9595d3a0.png
[d61a3d28dffd490aa8cd85cd91409c94.png]: https://img-blog.csdnimg.cn/d61a3d28dffd490aa8cd85cd91409c94.png
[0e2e930bbb9f4c9b847eaba3c954754d.png]: https://img-blog.csdnimg.cn/0e2e930bbb9f4c9b847eaba3c954754d.png
[0fdc62de8ad449ea9c79e07378093e78.png]: https://img-blog.csdnimg.cn/0fdc62de8ad449ea9c79e07378093e78.png
[806225cfd38c474e9290a7709930fee1.png]: https://img-blog.csdnimg.cn/806225cfd38c474e9290a7709930fee1.png
[92fd13522d7342bb8e856dd1e607e23f.png]: https://img-blog.csdnimg.cn/92fd13522d7342bb8e856dd1e607e23f.png
[3c9c1efc28cd4761a8820d78474af28c.png]: https://img-blog.csdnimg.cn/3c9c1efc28cd4761a8820d78474af28c.png
[1c1b4c1b22ce4f05bca8b8a28cd971b7.png]: https://img-blog.csdnimg.cn/1c1b4c1b22ce4f05bca8b8a28cd971b7.png
[3b73d1a744654a5da011a98c9eec8059.png]: https://img-blog.csdnimg.cn/3b73d1a744654a5da011a98c9eec8059.png
[f026116666ed44888410a108862a8f79.png]: https://img-blog.csdnimg.cn/f026116666ed44888410a108862a8f79.png
[c88b1ac1cce14bd1afd2cf209c9b92f0.png]: https://img-blog.csdnimg.cn/c88b1ac1cce14bd1afd2cf209c9b92f0.png
[479cf50834a74b2b9ab0db40f6b2c672.png]: https://img-blog.csdnimg.cn/479cf50834a74b2b9ab0db40f6b2c672.png
[8402469c23aa43ed8162f317d650cf05.png]: https://img-blog.csdnimg.cn/8402469c23aa43ed8162f317d650cf05.png
[cf12249796eb4243a2e37fbd1b0ce5c3.png]: https://img-blog.csdnimg.cn/cf12249796eb4243a2e37fbd1b0ce5c3.png
[d541feba404947db80b522a8c2e64026.png]: https://img-blog.csdnimg.cn/d541feba404947db80b522a8c2e64026.png
[06271cd0090a4204bc8df919a7efa137.png]: https://img-blog.csdnimg.cn/06271cd0090a4204bc8df919a7efa137.png
[ef2efaa7c05240ea9979d371e61ff83e.png]: https://img-blog.csdnimg.cn/ef2efaa7c05240ea9979d371e61ff83e.png
[f75be5dbd03a494f8725d538e8c6ccc5.png]: https://img-blog.csdnimg.cn/f75be5dbd03a494f8725d538e8c6ccc5.png
[a49051c72d7944fda9c0c8e576658664.png]: https://img-blog.csdnimg.cn/a49051c72d7944fda9c0c8e576658664.png
[74905ae25bf04e31a1002fad3ddcc27a.png]: https://img-blog.csdnimg.cn/74905ae25bf04e31a1002fad3ddcc27a.png
[e74a6ac458e84324bb447f5be346eed5.png]: https://img-blog.csdnimg.cn/e74a6ac458e84324bb447f5be346eed5.png
[0aae070aa4374df7a70cf404390b11eb.png]: https://img-blog.csdnimg.cn/0aae070aa4374df7a70cf404390b11eb.png
[3ddb2711023943f39d9b96c6f49c4ee2.png]: https://img-blog.csdnimg.cn/3ddb2711023943f39d9b96c6f49c4ee2.png
[Link 1]: https://blog.csdn.net/Drifter_Galaxy/article/details/107454567
[70f067eb8f9a45f88377d80e438f517b.png]: https://img-blog.csdnimg.cn/70f067eb8f9a45f88377d80e438f517b.png
[78a742b7f8944c2ebafb96c6f0eb16ac.png]: https://img-blog.csdnimg.cn/78a742b7f8944c2ebafb96c6f0eb16ac.png
[53ea423384cc4cb080b34224b88e170b.png]: https://img-blog.csdnimg.cn/53ea423384cc4cb080b34224b88e170b.png
[0f26ecdd3d844378adc03c7c076ab94c.png]: https://img-blog.csdnimg.cn/0f26ecdd3d844378adc03c7c076ab94c.png
[71b019022cb44b6eba1a66e22e3e9824.png]: https://img-blog.csdnimg.cn/71b019022cb44b6eba1a66e22e3e9824.png
[f6ac697567f54f8084910c6db38e5849.png]: https://img-blog.csdnimg.cn/f6ac697567f54f8084910c6db38e5849.png
[1fdd4fd325f74f10b2e6be30aac57ed1.png]: https://img-blog.csdnimg.cn/1fdd4fd325f74f10b2e6be30aac57ed1.png
[23f49c1d0fd647ca98c54fddc1b85488.png]: https://img-blog.csdnimg.cn/23f49c1d0fd647ca98c54fddc1b85488.png
[7b4954ca9a44473b8517053b7ba9465c.png]: https://img-blog.csdnimg.cn/7b4954ca9a44473b8517053b7ba9465c.png
[775e26b218bf471cad216c74bb26a0e3.png]: https://img-blog.csdnimg.cn/775e26b218bf471cad216c74bb26a0e3.png
[c15c8c67d51a42e8b602e0a9b4b340c4.png]: https://img-blog.csdnimg.cn/c15c8c67d51a42e8b602e0a9b4b340c4.png
[8912ac77cc654f8f9870c602292996c4.png]: https://img-blog.csdnimg.cn/8912ac77cc654f8f9870c602292996c4.png
[4eb2e150d38d49c3b6a1943a257b9614.png]: https://img-blog.csdnimg.cn/4eb2e150d38d49c3b6a1943a257b9614.png
[8925e433e9ec4c7fbddfb651a8584dba.png]: https://img-blog.csdnimg.cn/8925e433e9ec4c7fbddfb651a8584dba.png
[4e7f4e23f0bd4b22adf576761bfa6a05.png]: https://img-blog.csdnimg.cn/4e7f4e23f0bd4b22adf576761bfa6a05.png
[660b7c7d46d349cdb2964270f8f08d18.png]: https://img-blog.csdnimg.cn/660b7c7d46d349cdb2964270f8f08d18.png
[0460371702464d35a5ea0accc9ce213a.png]: https://img-blog.csdnimg.cn/0460371702464d35a5ea0accc9ce213a.png
[449b7884256d40aca6b92d981dc287cb.png]: https://img-blog.csdnimg.cn/449b7884256d40aca6b92d981dc287cb.png
[56c148685cf7486ea9c6deb7ac8a3e69.png]: https://img-blog.csdnimg.cn/56c148685cf7486ea9c6deb7ac8a3e69.png
[3bbe9f1c874c468a86abadd1e65abf1a.png]: https://img-blog.csdnimg.cn/3bbe9f1c874c468a86abadd1e65abf1a.png
[05728284f4ad479f9f19a17cee8af5f4.png]: https://img-blog.csdnimg.cn/05728284f4ad479f9f19a17cee8af5f4.png
[f39ebfddd0c343ff8686cc95a982b19a.png]: https://img-blog.csdnimg.cn/f39ebfddd0c343ff8686cc95a982b19a.png
[ba9f23ad89c1495a82ccde3795760c02.png]: https://img-blog.csdnimg.cn/ba9f23ad89c1495a82ccde3795760c02.png
[e91a513473be4fe5b879b3a55503bf91.png]: https://img-blog.csdnimg.cn/e91a513473be4fe5b879b3a55503bf91.png
[075061f63b04496c83e676a75ef290d1.png]: https://img-blog.csdnimg.cn/075061f63b04496c83e676a75ef290d1.png
[78ddc05c4de34fda903ac82787f413bf.png]: https://img-blog.csdnimg.cn/78ddc05c4de34fda903ac82787f413bf.png
[522df5eae3744851ba8cf44695dc8f76.png]: https://img-blog.csdnimg.cn/522df5eae3744851ba8cf44695dc8f76.png
[ee9963e91c564832b0cc85ba5e62ebc5.png]: https://img-blog.csdnimg.cn/ee9963e91c564832b0cc85ba5e62ebc5.png
[9ea2e492e0db4b5cbec2376c205d7cc6.png]: https://img-blog.csdnimg.cn/9ea2e492e0db4b5cbec2376c205d7cc6.png
[Link 2]: https://www.runoob.com/w3cnote/ten-sorting-algorithm.html