数据结构

一、线性表

1.1 数组和链表的区别

线性表是具有相同数据类型的n个数据元素的有限序列

物理存储结构不同：
数组是顺序存储结构，存储长度是固定的，它不能适应数据动态增减的情况；
链表是链式存储结构，能够动态分配存储空间以适应数据动态增减的情况；
内存分配方式不同：
数组的存储空间一般采用静态分配；
链表的存储空间一般采用动态分配；
元素的存取方式不同：
数组元素为直接存取；
链表元素的存取需要遍历链表；
元素的插入和删除方式不同：
数组进行元素插入和删除时，需要移动数组的元素；
链表进行元素插入和删除时，无需移动链表内的元素；

1.2 链表种类

单链表
双链表
循环单链双链表

好处：单链表只能从表头结点开始遍历所有结点，而循环单链表可以从表中的任一结点开始遍历整个链表。对单链表我们常常设立头指针，这样在表头表尾操作的时间复杂度分别为O(1)和O(n)，而对于循环列表常常设立尾指针，时间复杂度都为O(1)

静态链表：借助数组描述线性表的链式存储结构，需要预先分配一块连续的内存空间。

优点：增删改查不用移动大量元素。

缺点：不能随机存取，容量固定不可变。(不支持指针的语言)

尾插法得遍历(维护长度)

头插法直接在前面插入

==1.3 栈与队列==

栈：是只允许在一端进行插入或删除操作的线性表

队列：也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除

栈：顺序栈利用一组地址连续的存储单元存放数据元素，同时附设一个指针指示当前栈顶元素位置。链栈是利用一个单链表存储数据元素，并将表头作为栈顶进行插入和删除操作。

队列：顺序存储是利用一组地址连续的存储单元存放数据元素，并附设两个指针，通常front指针指向队头元素，rear指针指向队尾元素的下一个位置。链式存储是利用一个带有头指针和尾指针的链表存储数据元素。

==1.4 数据存储方式==

顺序存储结构的优点：

顺序存储是指在内存中开辟连续的存储空间来存放数据，把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。

可以随机存取，即通过首地址和元素序号可在时间O(1)内找到指定的元素，链表只能从表头开始遍历，顺序存取元素。
存储密度高，每个节点只存储数据元素（链式存储还要存指针）

缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。

链式存储结构的优点：

链式存储的存储空间不是连续的，借助指针来表示元素间的逻辑关系。还需要存放一个指向其后继的指针，指向下一元素。

进行插入、删除操作时很方便，不需要移动数据元素。

顺序存储在进行插入操作时需要将插入位置之后的元素全部后移一位，时间复杂度为O(n)，而链式存储只需要修改插入位置前驱后继节点指针的指向，时间复杂度为o(1)；
不用预先估计存储空间的规模，在需要时向内存申请空间即可，操作灵活。

而顺序存储包含两种方式，静态分配和动态分配，若采用静态分配，一旦存储空间满了就不能再扩充，因此为了规避内存溢出的风险，只能尽量分配足够大的存储空间，但这样又会导致空间的浪费。而动态分配虽然可以扩充存储空间，但是需要移动大量元素，操作效率低。
不会出现碎片现象，能充分利用所有存储单元
每个元素因存储指针而占用额外的存储空间

索引存储：

优点：检索速度快
缺点：附加的索引表额外占用存储空间，增加和删除元素时也要修改索引表。

散列存储：根据元素的关键字直接计算出该元素的存储地址。

优点：检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元冲突，而解决冲突会增加时间空间开销。

1.5 头指针和头节点的区别

⭐⭐

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息，它是为了方便做的一种处理。

引入头结点的优点：

由于第一个数据节点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在链表其他位置上的操作一致，无需进行特殊处理。
无论链表是否为空，其头指针都是指向头结点的非空指针，因此空表和非空表的处理也得到了统一。

==1.6 判断链表是否有环==

==（非常重要！）⭐⭐⭐⭐⭐⭐⭐==

快慢指针：创建两个指针fast和slow，开始时两个指针都指向链表头head，在每一步操作中slow向前走一步，fast向前走两步，由于fast比slow移动的快，如果有环，两个指针就会相遇。

==1.7 循环队列==

有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是front，rear，现在求Q中元素的个数？⭐⭐

因为出队操作会导致队头的存储空间空闲，当rear指针指到maxsize的时候，其实是一种“假溢出”，这时候队列并没有满。为了解决这个问题，我们把存储队列元素的表从逻辑上视为一个环，称为循环队列。

初始：front=rear=0；

出队：front = (front+1)%maxsize 队头指针加一取模

入队：rear = (raer+1)%maxsize 队尾指针加1取模

队列长度=(rear-front+maxsize)%maxsize

如何区分循环队列是队空还是队满？

队满条件和队空条件都是rear = front

因此为了区分这两个条件，可以采用的处理方式为：

入队时少用一个存储单元，将差一个不满的条件视为队满，判断队空条件不变：队头和队尾指针在同一位置时，队空 rear = front，判断队满条件变为：队头指针在队尾指针的下一位置时，队满，也就是（rear+1）%maxsize = front
增设一个数据成员记录元素个数，队空条件为size = 0；队满条件为size=maxsize。

1.8 栈的应用

（1）括号匹配：匹配过程为从左至右扫描表达式，每当遇到一个右括号时，就判断他和最后出现的那个左括号是否匹配，因此用栈存储被扫描到的左括号。每当扫描到右括号时，就让栈顶的左括号出栈。

（2）后缀表达式的运算：运算过程是从左到右扫描表达式，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体成一个新的操作数。最后出现的操作数最先被运算，所以用栈来存储操作数。

（3）中缀表达式转后缀表达式：栈中存储还未确定运算顺序的运算符。

（4）递归

（5）进制转换

（6）深度优先搜索图

（7）前序遍历二叉树

1.9 队列的应用

（1）层次遍历

（2）图的广度优先遍历

（3）打印机缓冲区（主机和外部设备速度不匹配）：先进入缓冲区排队的先打印

（4）CPU资源竞争中的先来先服务策略

==二、串==

⭐⭐⭐

朴素的匹配算法和KMP算法

朴素模式匹配算法：这个方法也称为暴力匹配。就是从源字符串开始搜索，若出现不能匹配，则从原搜索位置+1进行搜索。

主串长度：n，模式串长度m，最坏情况下共需对比n-m+1个子串，每个子串对比m个字符，时间复杂度为O(n*m)。

KMP算法：

KMP算法的思想是利用匹配失败后的信息，尽量减少子串与主串的匹配次数以达到快速匹配的目的。

算法实现的关键是求出next数组，next[j]表示：在子串的第j个字符与主串发生失配时，则跳到子串指针应该移动到的位置。

求next数组的方法：在不匹配的位置前，画一个分界线，模式串一步步右移，直到分界线之前能匹配或者模式串完全跨过分界线为止。此时子串指针j指向哪儿，next数组的值就是多少。

next数组：next[i]表示在i位置之前的字符串中，同时也是模式串的后缀和前缀匹配的最大长度。

next[1]=0 next[2]=1

匹配方法：匹配过程产生失配时，主串指针i不变，子串指针j退回到next[j]的位置并重新进行比较。

时间复杂度：求next数组O(m)，模式匹配O(n),O(m+n)，主要优点是主串不回溯。

三、树

3.1 树的性质

树中的结点数等于所有结点的度数之和加1
度为m的树中第i层上至多有m^i-1个结点(i>=1)
高度为h的m叉树至多有m^h-1/(m-1)个结点
具有n个结点的m叉树的最小高度为ceil[logm (n(m-1)+ 1)]。

3.2 哈夫曼树与哈夫曼编码

哈夫曼树：在含有n个带权叶结点的二叉树中，带权路径长度(WPL)最小的二叉树

构造步骤：

将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
重复步骤2和3，直至F中只剩下一棵树为止。

前缀编码：任何一个编码都不是其他编码的前缀（最左子串），哈夫曼编码就是最优前缀编码

==3.3 树的分类及构造==

⭐⭐⭐

满二叉树
完全二叉树
二叉树排序
平衡二叉树：树上任一结点左子树和右子树深度之差不超过1.

二叉树的顺序存储,二叉树的链式存储

如何由遍历序列构造一颗二叉树？/已知先序序列和后序序列能否重现二叉树？

不能，没有中序遍历序列的情况下是无法确定一颗二叉树的

线索二叉树

在含有n个结点的二叉树中会有n+1个空指针，可以利用这些指针存放当前结点的前驱和后继指针，引入线索二叉树可以加快查找结点前驱和后继的速度。
要增加两个标志域标识指针域是指向左（右）孩子的还是指向前驱（后继）的。

3.4 树与森林

树–>二叉树：
加线。在所有的兄弟结点之间加一条线。
去线。树中的每个结点，只保留它与第一个孩子结点的连线，删除其他孩子结点之间的连线。
以树的根结点为轴心，将整个树调节一下（第一个孩子是结点的左孩子，兄弟转过来的孩子是结点的右孩子）
每个结点左指针指向它的第一个孩子，右指针指向它在树中相邻的右兄弟。
森林–>二叉树：将森林中的每棵树都转换为二叉树，将第二棵二叉树作为第一棵的右子树，将第三棵二叉树作为第二棵二叉树的右兄弟，以此类推，直至只剩下唯一一棵二叉树。
二叉树–>森林：将根节点右链断开形成两棵二叉树，以此类推直至所有二叉树根节点都不存在右子树，最后将每棵二叉树都转换为树，得到森林。

3.5 并查集

每一个集合以森林中的一棵树表示，集合的并操作就转化成了合并两棵树（只需要改变第二棵树根节点的指向），集合的查操作就转化成了判断两个结点是否在同一棵树中。

四、图

邻接矩阵适合稠密图邻接表适合稀疏图

==4.1 最小生成树==

图的所有生成树中具有边上的权值之和最小的树

Prim算法的基本思想是选点：
初始时从图中任取一顶点加入树T，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作T中的顶点数和边数都加1。
以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。
实现方法：两个数组，一个用来存储各顶点加入生成树的最小代价，一个用来存储各顶点是否已经加入了最小生成树。每次归并一个新顶点前，要遍历这两个数组找到还未加入树且权值最小的顶点；归并一个新顶点后要更新这两个数组。

时间复杂度：此算法是双层循环，外层循环控制次数，一共要归并n个顶点，因此要循环n-1次，内层并列两个循环，每个循环负责遍历一个数组，因此此算法的时间复杂度为O(n²)，时间复杂度只与顶点有关，与边无关，适用于稠密图。
Kruskal算法的基本思想是选边：
初始时构造只有n个顶点但是没有边的非连通图，每个顶点自成一个连通分量，然后按边的权值升序枚举每条边
- 若该边依附的顶点落在T中不同的连通分量上，则将此边加入T
- 否则舍弃此边而选择下一条权值最小的边
以此类推，直至T中所有顶点都在一个连通分量上，得到的T就是最小生成树。
实现方法：将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。

时间复杂度：用堆来存放边的集合O(logE)，用并查集来判断2顶点是否连通（是否属于同一个集合），O(ElogE)

时间复杂度只与边有关，适合边稀疏顶点多的图

==4.2 最短路径==

Dijkstra算法是求单源最短路径算法，用于求某一顶点到其他顶点的最短路径
迪杰斯特拉算法的基本思想是逐步找到从起始节点到其他节点的最短路径，通过不断更新节点的距离信息来实现。算法维护一个距离数组，其中存储了从起始节点到每个节点的当前最短路径估计
算法的具体步骤如下：
1. 初始化距离数组，将起始节点的距离设为0，其他节点的距离设为无穷大。
2. 从距离数组中选择当前距离最小的节点，标记为已访问。
3. 遍历以该节点为起点的所有边，更新与这些边相连的节点的距离。如果通过当前节点可以获得更短的路径，就更新距离数组中的值。
4. 重复步骤2和3，直到所有节点都被访问过或者目标节点的距离已经确定为最短路径。
  
  时间复杂度为O(n²) ，其中n为图中的顶点数。
Floyd算法是求任意顶点之间的最短路径的算法，其边的权值可为负权。
Floyd算法的基本思想是采用动态规划的方法，通过逐步迭代来更新节点之间的最短路径距离。
算法的核心是一个三重循环，第一层循环遍历各个节点作为中间节点，第二、三层循环遍历源点i和终点j，看是否能通过这个中间节点来获得更短的路径。

4.3 拓扑排序

AOV网：以顶点为活动，边为活动间先后顺序关系的有向图

在AOV网中如果不存在回路，则可以把所有的活动排列成一个序列，称该序列为拓扑序列

拓扑排序可以决定哪些子工程必须要先执行，哪些子工程要在某些工程完成后才能执行。

步骤：

在有向图中任意选择一个没有前驱的节点输出
从图中删去该节点以及与它相连的边
重复步骤1、2，直到所有的顶点都输出或者当前图中不存在无前驱的顶点为止，后者代表该图是有环图

时间复杂度：由于删除每个顶点的同时还要删除以他为起点的边，因此每个顶点和每条边都会被遍历一次。采用邻接表存储方式：O(V+E)，采用邻接矩阵存储方式：O(V²)

4.4 关键路径

AOE网：用顶点表示事件，边表示活动，边的权值表示两个活动持续的时间。

AOE网从源点到汇点的路径中，具有最大路径长度的路径为关键路径，关键路径上的活动称为关键活动

步骤：

按拓扑序依次求各个事件的最早发生时间ve
求各个事件的最晚开始时间vl
求各个活动的最早开始时间e
求各个活动的最晚开始时间l
求所有活动的时间余量，余量为0的活动为关键活动

4.5 图的基本概念

完全图：在全图的任意两个顶点间都存在边
连通图：图中任意两个顶点连通
连通分量：无向图中的极大连通子图
强连通：在有向图中，如果有一对顶点v和w，从v到w和从w到v都有路径，则称这两个顶点是强连通的
强连通分量：极大强连通子图
生成树：包含图中全部顶点的极小连通子图。

⭐

邻接矩阵法（适用于存储稠密图）：用一个一维数组存储图中顶点信息，用一个二维数组存储图中边的信息,存储顶点之间邻接关系的二维数组称为邻接矩阵。空间复杂度O(n²)。
邻接表法（适用于存储稀疏图）：图中顶点用一个一维数组存储，存储顶点数据和边表头指针。为每个顶点建立一个单链表，存储依附于此顶点的边，这个单链表就成为边表（对于有向图来说叫出边表）空间复杂度：无向图（每条边存储了两次）：O(V+2E) 有向图O(V+E)

==4.6 DFS和BFS==

⭐⭐⭐

广度优先搜索

时间复杂度=访问顶点的时间+找邻接顶点的时间，采用邻接表存储方式：O(V+E)，采用邻接矩阵存储方式：O(V²)
深度优先搜索：深度优先搜索类似于树的先序遍历，他的策略是尽可能深的搜索一个图。

基本思想是：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接但未被访问的顶点w1，再访问与W1邻接但未被访问的顶点w2…..重复上述过程，当不能再向下访问时，依次退回到最近被访问的结点，若他还有顶点未被访问过，则从该点开始继续上述的搜索过程，直至图中所有顶点都被访问过为止。

时间复杂度=访问顶点的时间+找邻接顶点的时间，用邻接表存储方式：O(V+E)，采用邻接矩阵存储方式：O(V²）

五、查找

5.1 顺序查找分块查找

平均查找长度（ASL）所有查找过程中进行关键字的比较次数的平均值

按顺序查找优化思路：若每个元素被查的概率不等，则将被查概率大的放在靠前的位置。

按块查找(区间)索引结构

将查找表分为若干子块，块内元素无序，块间有序，即第一个块中的最大关键字小于第二个块中所有记录的关键字，以此类推。再建立一个索引表索引，表中的每个元素含有各块的最大关键字和各块第一个元素的地址，索引表按关键字有序排列。

查找过程分为两步，第一步是在索引表中确定待查记录所在的块，可以顺序或折半查找索引表；第二步是在块内顺序查找。

5.2 折半查找

首先将给定值key与有序表的中间位置的元素比较；
若相等，则查找成功，返回该元素的存储位置；
若不等，则所需查找的元素只需继续查找中间元素的前半部分或后半部分；
- 然后在缩小的范围内继续进行同样的查找，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

时间复杂度O(log_n)，要求查找表为顺序存储结构并且有序；

5.3 二叉排序树

若该树有左子树，则其左子树的所有节点值小于根的值；
若该树有右子树，则其右子树的所有节点值均大于根的值；
其左右子树也分别为二叉排序树

构造：从一棵空树出发，依次输入元素，将他们插入二叉排序树中的合适位置，使其符合二叉排序树定义。

删除：如果删除节点是叶节点，则直接删除；如果是非叶节点且只有一棵子树，则让这棵子树成为被删除结点父节点的子树；若是非叶节点且有左右两棵子树，则用被删除节点的直接前驱或者直接后继(中序遍历)替代。

平均查找长度：二叉排序树的平均查找长度主要取决于树的高度。最好情况：二叉排序树的平衡的(左右子树高度之差不超过1)，O(log2 n)；最坏情况：二叉排序树是一个只有左（右）孩子的单支树，O(n)

5.4 平衡二叉树：

又称为AVL树，它具有如下特点：

他的左右子树高度差的绝对值不能大于1，且他的左右子树也都是平衡二叉树。

特点：执行插入和删除操作后，非常频繁地调整全树整体拓扑结构

插入：每当在二叉排序树中插入（删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。如果导致了不平衡，则先找到插入路径上离插入节点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树（最小平衡子树）进行旋转。

如果由于在结点A的左孩子的左子树上插入新节点而导致失去平衡，则通过一次右单旋转调整。
如果由于在结点A的右孩子的右子树上插入新节点而导致失去平衡，则通过一次左单旋转调整。
如果由于在结点A的左孩子的右子树上插入新结点而导致失去平衡，则先通过一次左旋再通过一次右旋调整。
如果由于在结点A的右孩子的左子树上插入新结点而导致失去平衡，则先通过一次右旋再通过一次左旋调整。

平均查找长度：含有n个节点的平衡二叉树的最大深度为O(log2 n)，因此平衡二叉树的平均查找长度为O(log2 n)

左旋：将右子树的左子树链接到父亲节点的右孩子结点

==5.5 红黑树==

⭐⭐⭐

BST 插入删除修改都是O(n)

红黑树和二叉排序树都是O(log2n)

一棵红黑树是满足如下红黑性质的二叉排序树：

每个结点或是红色，或是黑色的。
根结点是黑色的。
叶结点都是黑色的。
不存在两个相邻的红结点
对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。
结论1：从根到叶结点的最长路径不大于最短路径的2倍。
结论2：有n个内部结点的红黑树的高度h≤2log_2(n+ 1)。

红黑树的“适度平衡”，由 AVL树的“高度平衡”，降低到“任意一个结点左右子树的高度，相差不超过2倍”，也降低了动态操作时调整的频率。放宽条件。对于红黑树来说，插入删除操作很多时候不会破坏其红黑特性，无需频繁调整树的形态，红黑树常数级时间内能完成修改

C++中的map和set、Java中的TreeMap和TreeSet都是用红黑树实现的。

插入：先进行查找操作，确定插入位置并插入。如果新结点是根，则染为黑色，若新节点非根，则染为红色。如果插入后不满足红黑树定义，则需要调整使其重新满足红黑树定义。

5.6 B树

关键字顺序类比BST

查找：1.在B树里找结点 2.在结点里找关键字

插入：

首先进行查找操作，找出插入该关键字的最低层中的某个非叶节点。
进行插入操作，如果插入后被插入节点的关键字个数超过m-1，则需要对节点进行分裂。
分裂方法是：从中间位置将关键字一分为二，左部分放在原结点中，右部分放在新结点中，中间位置的关键字插入原节点的父结点中。若此时导致父节点关键字个数也超过上限，则继续分裂。

删除：如果被删除的关键字k不在终端结点中时，可以用k的前驱或者后继来替代k。如果被删除的关键字在终端结点，则有2种情况：如果被删除关键字所在节点删除前的关键字个数>=m/2，则直接删除。反之需要重新调整结点，向兄弟结点借一个关键字或者与兄弟节点和双亲结点中的关键字进行合并。

用作数据库索引

==5.7 B+树==

⭐⭐⭐

与分块查找类似

具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；
叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中；
叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址；

B数和B+树的区别

B+树具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树。而在B树中，具有n个关键字的结点含有n+1棵子树。
B+树叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中。而在B树中，叶结点包含的关键字与其他结点包含的关键字是不重复的。
B+树非叶节点仅起索引作用，叶结点包含关键字对应记录的存储地址.而B树的结点中都包含关键字对应记录的存储地址。

为什么有了B树还要提出B+树

结构差异：B树的关键字分布在所有节点中，而B+树的所有关键字都存储在叶子节点中。
查询效率：对于单点查询，B树和B+树的效率相近。但对于范围查询，B+树由于叶子节点间的链接，效率更高。
空间利用率：B+树由于非叶子节点不存储数据，空间利用率更高，能够存储更多的关键字。

==5.8 哈希表==

⭐⭐⭐⭐

哈希表又称为散列表，通过把关键码的值直接映射到表中的一个位置，以加快查找速度。

构造方法：

直接定址法：直接取某个线性函数值作为散列地址
除留取余法：取一个最接近散列表表长的质数p，散列函数为key%p
数字分析法：选取数码分布较为均匀的若干位作为散列地址
平方取中法：取平方值的中间几位作为散列地址。

处理冲突的方法：

开放定址法：指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
线性探测法：冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元，缺点：大量元素在相邻的散列地址上堆积起来，降低了查找效率。
平方探测法：增量序列为0²,1²,-1²,2²…以此类推。优点：避免出现堆积问题，缺点：不能探测到散列表上的所有单元。
双散列法：需要使用两个散列函数，当通过第一个散列函数得到的地址发生冲突时，则利用第二个散列函数计算该关键字的地址增量。
伪随机序列法：增量为随机数。
拉链法：不同的关键字会通过散列函数映射到同一地址时，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。

==六、排序==

基本思想是什么？时间复杂度？是否稳定？给一个例子，问冒泡和快速排序在最坏的情况下比较几次？★★★★★★

6.1 插入排序

将序列分为有序部分和无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应位置上。

6.2 希尔排序

把元素按下标的一定增量d进行分组，对每组使用直接插入排序。随着增量逐渐减少，当增量减至1时，整个文件恰被分为一组，算法终止。

优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多

6.3 简单选择排序

将序列分为有序部分和无序部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。

优点是：实现简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。

6.4 堆排序

堆是特殊的完全二叉树，树中任意节点均大于或小于其左右孩子

将无序序列构建成一个堆，根据升序和降序需求选择大根堆或者小根堆，将堆顶元素与末尾元素交换，通过up和down操作重新调整堆，反复执行调整交换步骤，直到整个序列有序。

6.5 冒泡排序

基本思路为：每一趟都将相邻两元素进行比较，出现逆序情况则进行交换。

6.6 快速排序

基本思路为：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。

每次由一个枢轴将待排序序列分成左右两部分，这个过程类似于构造一棵二叉树，最小高度为log2 n,最大高度为n

优点是：每一趟能确定一个元素，时间效率较高。

6.7 基数排序

从最低位开始，对所有元素按照当前位的数值进行排序，直到对最高位进行排序。

设置r个空队列，按照各个关键字位权重递增的次序，对d个关键字位分别进行分配和收集操作。

分配：顺序扫描各个元素，根据当前处理的关键字位将元素插入相应队列。

收集：把各个队列中的结点依次出队并连接。

6.8 归并排序

将待排序表中的n个记录视为n个有序子表，每个子表长度为1。然后两两归并，得到n/2个长度为2的有序表，继续两两归并，直至归并成一个长度为n的有序表为止。

初始化两个数组A和B，将两个要进行归并操作的有序表复制到数组B的相邻位置，每次从B中的两个有序表分别取出一个关键字进行比较，将大的存入A，重复上述操作直至B空。

==七、其它==

7.1 时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n), 它是该算法问题规模n的函数，时间复杂度主要分析T(n) 的数量级。T(n) = O(f(n))

时间复杂度描述了算法所需的时间资源随着输入规模的增加而增加的速度。它是一种用来描述算法运行时间增长速度的渐近符号。大O记法表示算法时间复杂度的上界，即在最坏情况下，算法的运行时间不会超过某个常数乘以某个函数。

取f(n) 中随n增长最快的项，将其系数置为1 作为时间复杂度的度量。例如， f(n) = an³ + bn²+ cn 的时向复杂度为O(n³)

7.2 空间复杂度

空间复杂度描述了算法所需的存储空间与输入规模之间的关系。空间复杂度可以衡量算法对内存的利用情况

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

7.3 算法

算法是指解决特定问题或执行特定任务的一系列步骤或规则。算法是独立于编程语言的，它描述了解决问题的方法，而不是具体的实现方式。算法是一种用来描述解决问题的有限步骤集合。

7.4 数据结构三要素

数据结构三要素是什么？逻辑结构包括什么？存储结构包括什么？

逻辑结构、存储结构、数据运算

逻辑结构包括线性结构和非线性结构

线性结构包括线性表、栈、队列，非线性结构包括树、图集合

存储结构包括顺序存储、链式存储、索引存储和散列存储

7.5 循环与递归

循环和递归两者是可以互换的，不能决定性的说循环的效率比递归高。

递归的优点是：代码简洁清晰，容易检查正确性；缺点是：当递归调用的次数较多时，要增加额外的堆栈处理，有可能产生堆栈溢出的情况，对执行效率有一定的影响。

循环的优点是：结构简单，速度快；缺点是：它并不能解决全部问题，有的问题适合于用递归来解决不适合用循环。

7.6 贪心动态规划及分治法

贪心算法顾名思义就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，得到最后的结果，它不能保证全局最优解。

动态规划是把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。动态规划是从下到上，一步一步找到全局最优解。（各子问题重叠）

分治法：将原问题划分成n个规模较小而结构与原问题相似的子问题；

递归地解决这些子问题，然后再合并其结果，就得到原问题的解。（各子问题独立）

分治模式在每一层递归上都有三个步骤

分解：将原问题分解成一系列子问题；

解决：递归地解各个子问题。若子问题足够小，则直接求解；

合并：将子问题的结果合并成原问题的解。

例如归并排序。