目录
第一章绪论1.1数据布局的基本概念1.2数据布局的三要素1.2.1数据的逻辑布局1.2.2数据的存储（物理）布局：1.2.3数据的运算1.3算法的基本概念第二章线性表2.1线性表的存储布局2.2顺序表与链表的比较2.3栈2.4队列2.4数组与特殊矩阵2.5串第三章树和二叉树3.1树和森林3.1.1树的基本术语3.1.2树的性质3.1.3树与森林的遍历3.1.4树的存储布局3.1.5树转二叉树3.2二叉树3.2.1二叉树的性质3.2.4线索二叉树3.3哈夫曼树和哈夫曼编码第四章图4.1图的基本概念4.2图的存储布局4.3最小生成树4.3.1Prim算法4.3.2算法（克鲁斯卡尔）4.4最短路径4.5有向⽆环图（DAG）4.6拓扑排序4.7关键路径第五章查找5.1顺序查找（线性查找）5.2折半查找5.3分块查找5.4二叉排序树5.5平衡二叉树5.6红黑树5.7B树5.8B+树5.9哈希表（Hash）5.9.1构造哈希函数5.9.2处理冲突第六章排序6.1直接插入排序6.2希尔排序6.3冒泡排序6.4快速排序6.5简单选择排序6.6堆排序6.6.1建立大根堆6.6.2堆的插入与删除6.7归并排序6.8基数排序6.9外部排序6.9.1败者树6.9.2置换-选择排序6.9.3最佳归并树第一章绪论1.1数据布局的基本概念数据：所有能输入到计算机中并能被程序识别和处理的符号集合。包括:数值数据：整数、实数等。非数值数据：图形、图象、声音、文字等。
数据元素：数据的基本单位，在程序中作为一个整体进行考虑和处理。
数据项：构成数据元素的最小单位
关联图:
1.2.3数据的运算根据逻辑布局来定义,根据存储布局来实现。
1.3算法的基本概念算法:是对特定问题求解步骤的一种描述，是指令的有限序列。程序=数据布局+算法;算法必须是有穷的，而程序可以是无穷的
算法的基本特性：
好算法的特点：
高效性正确性健壮性:能处理一些异常可理解性抽象分级算法分析：
时间复杂度：当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶——关注的是增长趋势，用大O记号表示
常见的时间复杂度：Ο(1)＜O()＜O(n)＜O()＜O()＜O()＜O(n!)O(nn)(常对幂指阶)
空间复杂度：算法在执行过程中需要的辅助空间数量,递归程序看递归深度与问题规模n的关联。
第二章线性表线性表的逻辑布局：n（n≥0）个具有相同类型的数据元素的有限序列。
2.1线性表的存储布局顺序表：静态存储分配，编译时确定容量，用一段地址连续的存储单元依次存储线性表的数据元素，逻辑关联通过存储位置（下标）来实现（随机存储）
链表：动态存储分配，运行时分配空间，用一组任意的存储单元存放线性表的元素，用指针来反映数据元素之间的逻辑关联（顺序存储）
备注:位序从1开始。
顺序表与单链表图:
双链表示意图:
循环链表示意图:
静态链表示意图:
2.2顺序表与链表的比较存储密度比较：
顺序表：只存储数据元素、预分配存储空间链表：指针的布局性开销、链表中的元素个数没有限制按位查找：
顺序表：O(1)，随机存取链表：O(n)，顺序存取插入和删除：
顺序表：O(n)，平均移动表长一半的元素链表：不用移动元素，合适位置的指针——Ｏ(1)时间复杂度：
顺序表：若线性表频繁查找却很少进行插入和删除操作链表：若线性表需频繁插入和删除时空间复杂度：
顺序表：知道线性表的大致长度，空间效率会更高链表：若线性表中元素个数变化较大或者未知2.3栈定义：限定仅在一端（栈顶）进行插入和删除操作的线性表，后进先出。
栈示意图：
时间复杂度(插入与删除)：顺序栈与链栈均为O(1)
空间复杂度：链栈多一个指针域，布局性开销较大，使用过程中元素个数变化较大时，用链栈；反之顺序栈。
出栈元素不同排列的个数:(卡特兰数)
共享栈:两个栈共享一片内存空间,两个栈从两边往中间增长。
存储布局:
顺序栈初始化：top=-1链栈初始化：top=NULL栈的应用:
1)括号匹配
2)递归
3)后缀表达式
4)中缀表达式：设两个栈（数据栈和运算符栈），根据运算符栈的优先级进行运算。
2.4队列定义:只允许在一端插入,在另一端删除。具有先进先出的特点。
队列示意图:
时间复杂度：均为O（1）
空间复杂度：链队列多一个指针域，布局性开销较大；循环队列存在浪费空间和溢出问题。使用过程中元素个数变化较大时，用链队列；反之循环队列。
双端队列:只允许从两端插入、两端删除的线性表。
双端队列示意图：
存储布局:
链队列:队头指针指向队头元素的前一个位置，队尾指针指向队尾元素，先进先出。
循环队列：
1）队空：=rear
2）队满：(rear+1)%=
3）队列元素个数：（队尾-队头+队长）%队长==(rear-+)%
队列的应用:
1)树的层次遍历
2)图的广度优先遍历
2.4数组与特殊矩阵一维数组的存储布局：
二维数组的存储布局：
对称矩阵的压缩(行优先)：
下三角矩阵的压缩(行优先)：
上三角(行优先):
三对角矩阵的压缩(行优先)：
稀疏矩阵压缩：
十字链表法压缩稀疏矩阵：
2.5串串，即字符串（）是由零个或多个字符组成的有限序列。串是一种特殊的线性表，数据元素之间呈线性关联。
字符串模式匹配：
1）朴素模式匹配算法
2）KMP算法
手算KMP的next数组示意图:
求next[2]:
求next[3]:
求next[4]:
求next[5]:
C语言求KMP的next数组代码示例:
void(char*sub,int*next){(sub!=!=NULL);intj=2;//模式串的next指针intk=0;//next数组的回溯值,初始化为next[1]=0int=(sub);(!=0);next[0]=-1;next[1]=0;(){if(sub[j-1]==sub[k]){next[j]=++k;j++;}else{k=next[k];if(k==-1){k=0;next[j]=k;j++;}}}}求:
void(char*sub,int*next){int=(sub);for(intj=2;;j++){if(sub[j]==sub[next[j]])next[j]=next[next[j]]}}备注:
1)实现next有多种不同方式,对应不同的next数组使用
2)根据实现方式不同,next数组整体+1不影响KMP算法。
第三章树和二叉树3.1树和森林定义（树）：n（n≥0）个结点（数据元素）的有限集合，当n＝0时，称为空树。
3.1.1树的基本术语结点的度：结点所拥有的子树的个数。
叶子结点：度为0的结点，也称为终端结点。
分支结点：度不为0的结点，也称为非终端结点。
孩子：树中某结点子树的根结点称为这个结点的孩子结点。
双亲：这个结点称为它孩子结点的双亲结点。
兄弟：具有同一个双亲的孩子结点互称为兄弟。
路径：结点序列n1,n2,…,nk称为一条由n1至nk的路径，当且仅当满足结点ni是ni+1的双亲（1=ik）的关联。
路径长度：路径上颠末的边的个数。
祖先、子孙：如果有一条路径从结点x到结点y，则x称为y的祖先，而y称为x的子孙。
结点所在层数：根结点的层数为1；对其余结点，若某结点在第k层，则其孩子结点在第k+1层。
树的深度（高度）：树中所有结点的最大层数。
树的宽度：树中每一层结点个数的最大值。
树的度：树中各结点度的最大值。
树的路径长度:从根到每个结点的路径长度总和
备注:在线性布局中，逻辑关联表现为前驱——后继,一对一;在树布局中，逻辑关联表现为双亲——孩子,一对多。
森林:森林是m（m≥0）棵互不相交的树的集合,m可为0,即空森林。
3.1.2树的性质结点数=总度数+1
度为m的树第i层至多有个结点（i≥1）
高度为h的m叉树至多有个结点
具有n个结点的m叉树的最小高度为
最小高度推理过程图:
3.1.3树与森林的遍历树的遍历:
先根遍历(先根后子树)后根遍历(先子树后根)层序遍历森林的遍历:
前序遍历(先根,后子树)中序遍历(先子树后根,其实就是后序遍历树)区别与接洽:
1)树的前序遍历等价于其树转化二叉树的前序遍历！
2)树的后序遍历等价于其树转化二叉树的中序遍历！
3.1.4树的存储布局双亲表示法图:
孩子表示法图:
孩子兄弟表示法图(树/森林转化为二叉树):
3.1.5树转二叉树在树转为二叉树后,有以下结论:
1)树的叶子结点数量=二叉树左空指针数量(形象理解为树越宽,兄弟越多,越是向右长)
2)树的非叶子结点数量=二叉树右空指针-1(树越高,有儿子定是非结点,越是向左长)
3.2二叉树3.2.1二叉树的性质斜树：
左斜树：所有结点都只有左子树的二叉树右斜树：所有结点都只有右子树的二叉树满二叉树：所有分支结点都存在左子树和右子树，且所有叶子都在同一层上的二叉树
完全二叉树：在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树
完全二叉树特点：
叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面完全二叉树中如果有度为1的结点，只能够有一个，且该结点只有左孩子深度为k的完全二叉树在k-1层上一定是满二叉树在同样结点个数的二叉树中，完全二叉树的深度最小性质：在二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2+1
证明:设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：
n＝n0＋n1＋n2
在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：
n＝n1＋2n2＋1
性质：二叉树的第i层上最多有个结点（i≥1）
性质：一棵深度为k的二叉树中，最多有个结点
性质：具有n个结点的完全二叉树的深度为向下取整+1(或向上取整)
证明：设具有n个结点的完全二叉树的深度为k，则：
≤n
对不等式取对数，有：
k-1≤＜k
即：
＜k≤+1
由于k是整数，故必有
k＝+1
性质：对一棵具有n个结点的完全二叉树中从1开始按层序编号，对于任意的序号为i（1≤i≤n）的结点（简称结点i），有：
如果i＞1，则结点i的双亲结点的序号为i/2，否则结点i无双亲结点如果2i≤n，则结点i的左孩子的序号为2i，否则结点i无左孩子如果2i+1≤n，则结点i的右孩子的序号为2i+1，否则结点i无右孩子性质：若已知一棵二叉树的前序序列和中序序列，或者中序序列和后序序列，能唯一确定一颗二叉树。
3.2.2二叉树的遍历
从根结点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次。
前序遍历（深度优先遍历）中序遍历后序遍历层序遍历（广度优先遍历）3.2.3二叉树的存储
链式存储图:
顺序存储图:
3.2.4线索二叉树利用二叉树中n+1个空指针,将指针指向结点的前驱和后继。
存储布局:
示例图:
三种线索化的对比图:
各自特点:
3.3哈夫曼树和哈夫曼编码带权路径长度(WPL)：从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和
最优二叉树（哈夫曼树）：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树
特点：
权值越大的叶子结点越接近根结点只有度为0和度为2的结点，不存在度为1的结点前缀编码：在一组编码中，任一编码都不是其它任何编码的前缀,前缀编码保证了在解码时不会有多种能够。
第四章图定义：顶点集V和边集E组成，记为G=(V,E)
注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集,边集E可认为空
子图：若图G=(V,E)，G'=(V',E')，如果V'ÍV且E'ÍE，则称图G'是G的子图
4.1图的基本概念图的分类:
无向边：表示为(vi,vj)，顶点vi和vj之间的边没有方向
有向边（弧）：表示为vi,vj，从vi到vj的边有方向,vi为弧尾,vj为弧头
稠密图：边数很多的图
稀疏图：边数很少的图
无向完全图：无向图中，任意两个顶点之间都存在边
有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧
度、入度和出度：
顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)
顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；
顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)；
握手定理:
路径：
回路（环）：第一个顶点和最后一个顶点相同的路径
简单路径：序列中顶点不重复出现的路径
简单回路（简单环）：除第一个和最后一个顶点外，其余顶点不重复出现的回路。
路径长度：非带权图——路径上边的个数
路径长度：带权图——路径上边的权值之和
无向连通图：
连通顶点：在无向图中，如果顶点vi和顶点vj(i≠j)之间有路径，则称顶点vi和vj是连通的
连通图：在无向图中，如果任意两个顶点都是连通的，则称该无向图是连通图
连通分量：非连通图的极大连通子图、连通分量是对无向图的一种划分
连通分量示意图:
有向强连通图、强连通分量：
强连通顶点：在有向图中，如果从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称顶点vi和vj是强连通的
强连通图：在有向图中，如果任意两个顶点都是强连通的，则称该有向图是强连通图
强连通分量：非强连通图的极大连通子图
强连通分量示意图:
子图与生成子图:
常考点
无向图:
所有顶点的度之和=2|E|
若G是连通图，则最少有n-1条边（树），若|E|n-1，则一定有回路
若G是非连通图，则最多能够有条边(n-1个完全图+1个孤点)
无向完全图共有条边
有向图:
所有顶点的出度之和=入度之和=|E|
所有顶点的度之和=2|E|
若G是强连通图，则最少有n条边（形成回路）
有向完全图共有条边
图的遍历：从图中某一顶点出发访问图中所有顶，并且每个结点仅被访问一次。
深度优先遍历序列（dfs）广度优先遍历序列（bfs）备注:调⽤BFS/DFS函数的次数=连通分量数
4.2图的存储布局邻接矩阵：
一维数组：存储图中顶点的信息二维数组（邻接矩阵）：存储图中各顶点之间的邻接关联特点：一个图能唯一确定一个邻接矩阵，存储稀疏图时，浪费空间。空间复杂度为:O()。
示意图:
性质(行*列):
邻接表：
顶点表：所有边表的头指针和存储顶点信息的一维数组边表（邻接表）：顶点v的所有邻接点链成的单链表示意图:
特点：空间复杂度为：O（n+e）,适合存储稀疏图。
两者区别:
十字链表法图:
备注:
1)十字链表只用于存储有向图
2)顺着绿色线路找:找到指定顶点的所有出边
3)顺着橙色线路找:找到指定顶点的所有入边
4)空间复杂度：O(|V|+|E|)
邻接多重表图:
备注:
1)邻接多重表只适用于存储无向图
2)空间复杂度：O(|V|+|E|)
四者区别:
4.3最小生成树生成树：连通图的生成树是包含全部顶点的一个极小连通子图,可用DFS和BFS生成。
生成树的代价：在无向连通网中，生成树上各边的权值之和
最小生成树：在无向连通网中，代价最小的生成树
性质:各边权值互不相等时,最小生成树是唯一的。边数为顶点数-1
生成森林示意图:
4.3.1Prim算法从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。基于贪心算法的策略。
时间复杂度：O(|V|2)适合⽤于边稠密图。
4.3.2算法（克鲁斯卡尔）每次选择⼀条权值最⼩的边，使这条边的两端连通（原本已经连通的就不选）,直到所有结点都连通。基于贪心算法的策略。
时间复杂度：O(|E|log2|E|)适合⽤于边稀疏图。
4.4最短路径非带权图:边数最少的路径（广度优先遍历）
带权图:边上的权值之和最少的路径
4.4.1算法时间复杂度：O(n2)
备注:算法不适⽤于有负权值的带权图
4.4.2算法核心代码:
时间复杂度：O(n3)
备注:可以⽤于负权值带权图,不能解决带有“负权回路”的图
三者区别:
4.5有向⽆环图（DAG）描述表达式(简化前):
描述表达式(简化后):
4.6拓扑排序AOV⽹(On，⽤顶点表示活动的⽹)：⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边表示活动Vi必须先于活动Vj进⾏
如图:
拓扑排序的实现：
①从AOV⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。
②从⽹中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。
逆拓扑排序（可用DFS算法实现）:
①从AOV⽹中选择⼀个没有后继（出度为0）的顶点并输出。
②从⽹中删除该顶点和所有以它为终点的有向边。
③重复①和②直到当前的AOV⽹为空
4.7关键路径在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹
示意图:
关键活动:从源点到汇点的有向路径能够有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动。
事件vk的最早发⽣时间:决意了所有从vk开始的活动能够开⼯的最早时间。
时间复杂度:O(n)。
有序顺序查找的ASL图:
无序查找失败时的平均查找长度:n+1次(带哨兵的情况)
5.2折半查找：元素必须是有序的，如果是无序的则要先进行排序操作。
基本思想：用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较成果确定下一步查找哪个子表。
公式：mid=(low+high)/2,即mid=low+1/2*(high-low);
1）相等，mid位置的元素即为所求
2），low=mid+1;
3），high=mid-1。
时间复杂度:
备注：对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，不建议使用。
5.3分块查找分块查找，⼜称索引顺序查找。
基本思想：将查找表分为若干子块,块内的元素可以无序,块间的元素是有序的,即前一个快的最大元素小于后一个块的最大元素。再建立索引表,索引表中的每个元素含有各块的最大关键字和第一个元素的地址。索引表按关键字有序排列。
示意图:
备注:
1)设索引查找和块内查找的平均查找⻓度分别为LI、LS，则分块查找的平均查找⻓度为
ASL=LI+LS
2)将长度为n的查找表平均分为b块,每块s个记录,在等概率情况下,若在块内和索引表中均采用顺序查找,则平均查找长度为:
5.4二叉排序树又称二叉查找树（BST，Tree）,是具有如下性质的二叉树：左子树结点值根结点值右子树结点值
二叉排序树的插入:新插入的结点一定是叶子。
二叉排序树的删除
1)情况一,删除叶结点,直接删除
2)情况二,待删除结点只有一颗子树,让子树代替待删除结点
3)情况三,待删除结点有左,右子树,则令待删除的直接前驱(或直接后继(中序遍历))代替待删除结点。
示意图:(30为直接前驱,60为直接后继)
平均查找效率:次要取决于树的高度。
时间复杂度:
5.5平衡二叉树简称平衡树（AVL树）,树上任一结点的左子树和右子树的高度之差不超过1。结点的平衡因子=左子树高-右子树高。
平衡二叉树的插:
LL型:
RR型:
RL型:
LR型:
平衡二叉树的删除:同上
考点:
假设以表示深度为h的平衡树中含有的最少结点数。则有=0,=1,=2，并且有=+
时间复杂度:
5.6红黑树与AVL树相比,插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。因为AVL是高度差严格要求不超过1,红黑树高度差不超过2倍,较为宽泛。
定义:
①每个结点或是红色，或是黑色的
②根节点是黑色的
③叶结点（外部结点、NULL结点、失败结点）均是黑色的
④不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）
⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同
口诀:左根右，根叶黑不红红，黑路同
示例图:
性质:
性质1：从根节点到叶结点的最长路径不大于最短路径的2倍(红结点只能穿插在各个黑结点中间)
性质2：有n个内部节点的红黑树高度
结论:若根节点黑高为h，内部结点数（关键字）最多有,最少有
示例图:
红黑树的插入操作:
红黑树的插入示例图:
红黑树的删除:和“二叉排序树的删除”一样!具体还是算了吧,放过自己。。。
时间复杂度:
5.7B树B树，⼜称多路平衡查找树，B树中所被允许的孩⼦个数的最⼤值称为B树的阶，通常⽤m表示。
m阶B树的特性:
1）树中每个结点⾄多有m棵⼦树，即⾄多含有m-1个关键字。
2）若根结点不是终端结点，则⾄少有两棵⼦树。
3）除根结点外的所有⾮叶结点⾄少有棵⼦树，即⾄少含有个关键字。
4)所有的叶结点都出现在同⼀层次上，并且不带信息,(指向这些结点的指针为空)。
5)最小高度:
6)最大高度:
7)所有⼦树⾼度要相同
示例图:
B树的插入(5阶为例):
B树的删除:
1)若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限⌈m/2⌉−1）
2)若被删除关键字在⾮终端节点，则⽤直接前驱或直接后继来替代被删除的关键字
删除77:
5）所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。所有⾮叶结点仅起索引作⽤，
6)所有⼦树⾼度要相同
B+树与B树的对比图:
5.9哈希表（Hash）根据数据元素的关键字计算出它在散列表中的存储地址。
哈希函数：建⽴了“关键字”→“存储地址”的映射关联。
冲突（碰撞）：在散列表中插⼊⼀个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为“冲突（碰撞）”
同义词：若不同的关键字通过散列函数映射到同⼀个存储地址，则称它们为“同义词”
复杂度分析：对于无冲突的Hash表而言，查找复杂度为O(1)
5.9.1构造哈希函数1)除留余数法——H(key)=key%p,取⼀个不⼤于m但最接近或等于m的质数p
适⽤场景：较为通⽤，只要关键字是整数即可
2)直接定址法——H(key)=key或H(key)=a*key+b
适⽤场景：关键字分布基本连续
3)数字分析法——选取数码分布较为平均的若⼲位作为散列地
适⽤场景：关键字集合已知，且关键字的某⼏个数码位分布平均
4)平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址
适⽤场景：关键字的每位取值都不够平均。
5.9.2处理冲突拉链法示意图:
开放定址法:
1)线性探测法
2)平⽅探测法
3)双散列法
4)伪随机序列法
示意图:
删除操作:采用开放定址法时,只能逻辑删除。
装填因子:表中记录数/散列表长度。
备注:平均查找长度的查找失败包含不放元素的情况。(特殊:根据散列函数来算:2010真题)
聚集:处理冲突的方法选取不当,而导致不同关键字的元素对同一散列地址进行争夺的现象
第六章排序不变：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
参考博客：
超详细十大经典排序算法总结（java代码）c或者cpp的也可以明白的博客-CSDN博客
6.1直接插入排序动图演示：
优化:折半插入排序
6.2希尔排序又称缩小增量排序,先将待排序表分割成若⼲形如L[i,i+d,i+2d,…,i+kd]的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。建议每次将增量缩⼩⼀半。
示例图:
6.3冒泡排序动图演示:
6.4快速排序算法思想：
1)在待排序表L[1…n]中任取⼀个元素作为枢轴（或基准）
2)通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于，L[k+1…n]中的所有元素⼤于等于，则放在了其最终位置L(k)上，这个过程称为⼀次“划分”。
3)然后分别递归地对两个⼦表重复上述过程，直每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。
示例图:
6.5简单选择排序算法思想:每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列。
动画演示:
6.6堆排序⼤根堆:若满⾜：L(i)≥L(2i)且L(i)≥L(2i+1)（1≤i≤n/2）
⼩根堆:若满⾜：L(i)≤L(2i)且L(i)≤L(2i+1)（1≤i≤n/2）
大根堆示例图:
6.6.1建立大根堆思路：从开始,把所有⾮终端结点都检查⼀遍，是否满足大根堆的要求，如果不满⾜，则进⾏调整。若元素互换破坏了下⼀级的堆，则采⽤相同的方法继续往下调整（⼩元素不断“下坠”）
小元素下坠示例图:
结论:建堆的过程，关键字对⽐次数不超过4n，建堆时间复杂度=O(n)
6.6.2堆的插入与删除插入:将新增元素放到表尾,而后根据大小根堆进行上升调整。
删除:被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌
排序动图演示:
6.7归并排序该算法是采用分治法,把两个或多个已经有序的序列合并成⼀个。
2路归并图:
结论：n个元素进⾏2路归并排序，归并趟数(高度)=⌈⌉
6.8基数排序基数排序是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；
动图演示:
时间复杂度:⼀趟分配O(n)，⼀趟收集O(r)，总共d趟分配、收集，总的时间复杂度=O(d(n+r)）,其中把d为关键字拆为d个部分,r为每个部分能够取得r个值。
基数排序适用场景:
①数据元素的关键字可以⽅便地拆分为d组，且d较⼩
②每组关键字的取值范围不⼤，即r较⼩
③数据元素个数n较⼤
如:
内部排序总结:
6.9外部排序数据元素太多，⽆法⼀次全部读⼊内存进⾏排序,读写磁盘的频率成为衡量外部排序算法的次要因素。
示例图:
结论:采⽤多路归并可以减少归并趟数，从⽽减少磁盘I/O(读写)次数。对r个初始归并段，做k路归并，则归并树可⽤k叉树表示若树⾼为h，则归并趟数=h-1=。K越大,r越小,读写磁盘次数越少。
6.9.1败者树