数据结构——学习笔记——入门必看【建议收藏】
（2）静态查找表&动态查找表的区别用法【顺序查找-线性查找-折半查找-二分查找-有序表查找-插值查找-斐波那契查找-索引顺序表查找-分块查找】单独使用顺序存储结构（即数组）无法很好地实现树的存储概念，不过如果充分利用顺序存储和链式存储结构的特点，则完全可以实现对数的存储结构的表示。深度为 2，则至多只有 3 个结点：根结点，根结点的左子树，根结点的右子树···指的是这样一个数列：1、1、2、3、5
·
文章目录：
第五章：数组和广义表（Arrays and generalized tables）
2.线性表&树&图的【数据元素名称-有无结点-内部之间的关系】
3.图的五种种类【无向图-有向图-简单图-完全无向图-有向完全图】
8.最小生成树连通网的两种算法区别和用法【普里姆(Prim)算法-克鲁斯卡尔(Kruskal)算法】
9. AOV 网（Activity On Vertext Network）
第九章：动态内存管理（Dynamic memory management）
福利◕‿◕
基础【✍理论】 ：数据结构——学习笔记——入门必看【建议收藏】
提升【✍思维】 ：数据结构与算法基础——重要知识点截图【青岛大学-王卓版】
拔高【✍代码】 ：考研[*数据结构*]学习笔记汇总（全）_考研数据结构笔记
题库【✍练题】 ：数据结构题库、数据结构——【十五套卷子】考前题型归纳整理
参考书籍： 《大话数据结构》 《数据结构(C语言版)》严蔚敏_吴伟民 《数据结构与算法分析》参考视频
第一章：数据结构绪论
1.什么是程序
程序 = 数据结构 + 算法
2.逻辑结构&物理结构
3.顺序存储&链式存储
第二章：算法
1.定义
算法是解决特定问题求解步骤的描述
在计算机中表现为指令的有限序列
并且每条指令表示一个或多个操作
简而言之，算法是描述解决问题的方法2.特性
输入、输出、有穷性、确定性和可行性
好的算法：应该具有正确性，可读性，健壮性，高效率和低存储量的特征3.算法时间效率度量
（1）可以忽略加法常数
O(2n + 3) = O(2n)（2）与最高次项相乘的常数可忽略
O(2n^2) = O(n^2)（3） 最高次项的指数大的，函数随着 n 的增长，结果也会变得增长得更快
O(n^3) > O(n^2)（4）判断一个算法的（时间）效率时，函数中常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数
O(2n^2) = O(n^2+3n+1)
O(n^3) > O(n^2)4.时间复杂度&空间复杂度
第三章：线性表（Linear list）
1.定义
零个或多个数据元素的有限序列2.顺序存储结构&链式存储结构
第四章：栈与队列
1.栈（Stack）
是限定仅在表尾（栈顶）进行插入和删除操作的线性表 栈又称为 后进先出（Last In First Out） 的线性表，简称 LIFO 结构 栈的内部实现原理 栈的内部实现原理其实就是数组或链表的操作 而之所以引入 栈 这个概念，是为了将程序设计问题模型化 用高层的模块指导特定行为（栈的先进后出特性），划分了不同关注层次，使得思考范围缩小 更加聚焦于我们致力解决的问题核心，简化了程序设计的问题
（1） 栈顶（top）
我们把允许插入和删除的一端称为 栈顶（2）栈底（bottom）
另一端称为 栈底（3） 空栈
不含任何任何数据元素的栈称为 空栈2.顺序栈&链栈
栈 是线性表的特例，其具备先进后出 FILO 特性（1） 顺序栈
可以使用线性表的顺序存储结构（即数组）实现栈，将之称之为 顺序栈（2）链栈
可以使用单链表结构实现栈，将之称之为 链栈（3）两者示意图如下所示
（4）顺序栈&链栈的异同
A:同【时间复杂度】
顺序栈和链栈的时间复杂度均为O(1)
B:异【空间性能】
a:顺序栈
顺序栈需要事先确定一个固定的长度（数组长度）
可能存在内存空间浪费问题，但它的优势是存取时定位很方便
b:链栈
要求每个元素都要配套一个指向下个结点的指针域
增大了内存开销，但好处是栈的长度无限
因此，如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好使用链栈
反之，如果它的变化在可控范围内，则建议使用顺序栈3.队列（Queue）
（1）定义
是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
队列 是一种 先进先出（First In First Out） 的线性表
线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式
同样，队列作为一种特殊的线性表，也同样存在这两种存储方式（2）队头
允许删除的一端称为对头（3）队尾
允许插入的一端称为队尾第五章：数组和广义表（Arrays and generalized tables）
1.数组是一种特殊的线性表存储结构
其特殊在于表中的元素本身也是一种线性表，内存连续，根据下标在O(1)时间读/写任何元素
数组的顺序存储：行优先顺序和列优先顺序
在行优先顺序中：每一行的第一个元素位于低地址，最后一个元素位于高地址
因此，访问同一行中的元素时，其地址是连续的
在列优先顺序中：每一列的第一个元素位于低地址，最后一个元素位于高地址
因此，访问同一列中的元素时，其地址是连续的
数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构
数组的优点是访问速度快，缺点是插入和删除元素效率较低
2.广义表，又称列表，也是一种线性存储结构
同数组类似，广义表中既可以存储不可再分的元素，也可以存储广义表
记作：LS=(a1,a2,...,an)，其中，LS代表广义表的名称，an表示广义表存储的数据
广义表中每个ai既可以代表单个元素，也可以代表另一个广义表
广义表中存储的单个元素称为"原子"，而存储的广义表称为"子表
广义表的存储结构可以分为两种：深度优先顺序和广度优先顺序
在深度优先顺序中：广义表的每个元素都会被递归地处理，直到到达叶子节点
在广度优先顺序中：广义表的每个元素都会被逐层处理，每一层的元素都按照其在该层中的顺序进行处理
广义表的优点是具有较好的灵活性，可以存储任意类型的数据，缺点是访问速度较慢第六章：串（String）
1.定义
串（string） 是由零个或多个字符组成的有限序列，又名叫 字符串2.串的逻辑结构
串 的逻辑结构和线性表很相似
不同之处在于串针对的是字符集
也就是串中的元素都是字符
因此，对于串的基本操作与线性表是有很大差别的
线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素
但串中更多的是查找子串位置，得到指定位置子串，替换子串等操作3.串的存储结构
（1）串的顺序存储结构
串的顺序存储结构是用 一组地址连续的存储单元 来存储串中的字符序列。一般是用定长数组来定义
由于是定长数组，因此就会存在一个预定义的最大串长度
一般可以将实际的串长度值保存在数组 0 下标位置，也可以放在数组最后一个下标位置
也有些语言使用在串值后面加一个不计入串长度的结束标记符（比如\0）
来表示串值得终结，这样就无需使用数字进行记录（2）串的链式存储结构
对于串的链式存储结构，与线性表是相似的 但由于串结构的特殊性（结构中的每个元素数据都是一个字符） 如果也简单地将每个链结点存储一个字符，就会存在很大的空间浪费 因此，一个结点可以考虑存放多个字符 如果最后一个结点未被占满时，可以使用 "#" 或其他非串值字符补全 串的链式存储结构除了在链接串与串操作时有一定的方便之外 总的来说不如顺序存储灵活，性能也不如顺序存储结构好
第七章：树（Tree）
1.定义
树是n(n>=0)个结点的有限集
当n=0时称为空树
树 其实也是一种递归的实现，即树的定义之中还用到了树的概念2.特点
（1）且仅有一个特定的结点：根结点（Root） （2）当 n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3......Tm 其中每一个集合本身又是一棵树，并且称为根的 子树（SubTree）
下图所示的结构就不符合树的定义，因为它们都有相交的子树：
3.线性结构&树结构
单独使用顺序存储结构（即数组）无法很好地实现树的存储概念 不过如果充分利用顺序存储和链式存储结构的特点，则完全可以实现对数的存储结构的表示
4.二叉树
（1）定义
二叉树（Binary Tree）：是 n(n>=0)个结点的有限集合 该集合或者为空集（称为空二叉树） 或者由一个根结点和两棵互不相交的 分别称为根结点的左子树和右子树的二叉树组成
（2）特点
A:每个结点最多只能有两棵子树 B:左子树和右子树是有顺序的，次序不能任意颠倒 C: 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树
（3）五种基本形态
A：空二叉树 B：只有一个跟结点 C：根结点只有左子树 D：根结点只有右子树 E：根结点既有左子树又有右子树
（4）二叉树的四种遍历方式【前序遍历-中序遍历-后序遍历-层序遍历】
5.赫夫曼编码
树，森林看似复杂,其实它们都可以转化为简单的二叉树来处理 这样就使得面对树和森林的数据结构时，编码实现成为了可能 最基本的压缩编码方法：赫夫曼编码 给定n个权值作为n个叶子结点 构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树
a: 路径和路径长度 定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径 通路中分支的数目称为路径长度 若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1 例子：100和80的路径长度是1 50和30的路径长度是2 20和10的路径长度是3 b: 结点的权及带权路径长度 定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积 例子：节点20的路径长度是3 它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60 c: 树的带权路径长度 定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL 例子：示例中，树的WPL= 1*100 + 2*50 + 3*20 + 3*10 = 100 + 100 + 60 + 30 = 290
比较下面两棵树:
上面的两棵树都是以{10, 20, 50, 100}为叶子节点的树 左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360 右边的树WPL=350 左边的树WPL > 右边的树的WPL 你也可以计算除上面两种示例之外的情况，但实际上右边的树就是{10,20,50,100}对应的哈夫曼树
第八章：图（Graph）
A:在线性表中
数据元素之间是被串起来的，仅有线性关系
每个数据元素只有一个直接前驱和一个直接后驱
B:在树形结构中
数据元素之间有着明显的层次关系
并且每一层上的数据元素可能和下一层中多个元素相关
但只能和上一层中一个元素相关
C:图是一种较线性表和树更加复杂的数据结构
在图形结构中，结点之间的关系可以是任意的
图中任意两个数据元素之间都可能相关1.定义
由顶点的有穷非空集合和顶点之间边的集合组成 通常表示为：G(V,E) G表示一个图 V是图G中的顶点的集合 E是图G中边的集合
2.线性表&树&图的【数据元素名称-有无结点-内部之间的关系】
3.图的五种种类【无向图-有向图-简单图-完全无向图-有向完全图】
4.权
有些图的边或弧具有与它相关的数字，这种 与图的边或弧相关的数叫做权（Weight） 这些权可以表示从一个顶点到另一个顶点的距离或耗费 这种带权的图通常称为网（Network）
图就是一张带权的图 即标识中国四大城市的直线距离的网 此图中的权就是两地的距离 图结构中，路径的长度是路径上的边或弧的数据 第一个顶点到最后一个顶点相同的路径称为 回环 或 环（Cycle） 序列中顶点不重复出现的路径称为 简单路径
5.环
除了第一个顶点和最后一个顶点之外 其余顶点不重复出现的回路，称为 简单回路 或 简单环
如图所示两个图粗线都构成环 左侧的环只有第一个顶点和最后一个顶点都是 B 其余顶点没有重复出现，因此其是一个简单环 而右侧的环，由于顶点 C 的重复，因此它就不是简单环了
6.连通 生成树 有向图 森林
A: 连通
图中顶点间存在 路径，两顶点存在路径则说明是 连通 的
B:简单路径
如果路径最终回到起始点则成为 环，当中不重复叫 简单路径
C:强连通图
若任意两顶点都是连通的，则图就是 连通图，有向则称为 强连通图
D: 强连通分量
图中有子图，若子图极大连通则就是 连通分量，有向的则称为 强连通分量
E:生成树
无向图中连通且n个顶点n-1条边叫 生成树
F:有向树
有向图中一顶点入度为0
其余顶点入度为1的叫 有向树
G:森林
一个有向图由若干棵有向树构成生成 森林7.图的两种遍历【深度优先遍历-广度优先遍历】
8.最小生成树连通网的两种算法区别和用法【普里姆(Prim)算法-克鲁斯卡尔(Kruskal)算法】
9. AOV 网（Activity On Vertext Network）
在一个表示工程的有向图中
用顶点表示活动
用弧表示活动之间的优先关系
这样的有向图为顶点表示活动的网，我们成为 AOV 网（Activity On Vertext Network）
AOV 网中的弧表示活动之间存在的某种制约关系，同时 AOV 网中不能存在回路10.拓扑序列
设 G=(V,E)是一个具有 n个顶点的有向图
V中的顶点序列V1,V1,......Vn
满足若从顶点 Vi到Vj 有一条路径
则在顶点序列中顶点 Vi必在顶点Vj之前
则我们将这样的顶点序列称为一个 拓扑序列
所谓 拓扑排序，其实就是对一个有向图构造拓扑序列的过程
对 AOV 网进行拓扑排序的基本思路是：
A:从 AOV 网中选择一个入度为 0 的顶点输出
B:然后删去此顶点
C:并删除以此顶点为尾的弧
D:继续重复此步骤
E:直到输出全部顶点
或者 AOV 网中不存在入度为 0 的顶点为止11.AOE网
在一个表示工程的带权有向图中
用顶点表示事件
用有向边表示活动
用边上的权值表示活动的持续时间
这种有向图的边表示活动的网
我们称之为 AOE 网（Activity On Edge Network）
A:始点或源点
我们把 AOE 网中没有入边的顶点称为始点或源点
B:终点或汇点
没有出边的顶点称为终点或汇点
由于一个工程，总有一个开始，一个结束，所以正常情况下，AOE 网只有一个源点一个汇点
C:路径长度
我们把路径上各个活动所持续的时间之和称为 路径长度
D:关键路径
从源点到汇点具有最大长度的路径叫 关键路径
E:关键活动
在关键路径上的活动叫关键活动 第九章：动态内存管理（Dynamic memory management）
1.定义：数据结构的动态内存管理就是通过动态分配内存来存储数据，以适应数据结构的大小可变性和灵活性
如果分配成功，则返回指向新分配的内存的指针，否则返回NULL
2.动态内存管理函数
realloc函数：realloc(ptr, size)用来改变之前通过malloc或realloc分配的内存空间的大小
ptr是指向之前分配的内存空间的指针
size是新的空间大小
realloc函数会尝试重新分配一块新的内存空间，并把原空间的内容移动到新空间中
如果分配成功，则返回指向新分配的内存的指针，否则返回NULL
free函数：free(ptr)用来释放之前通过malloc或realloc分配的内存空间
ptr是指向要释放的内存空间的指针。释放后，ptr指向的内存空间将不可再用
calloc函数：calloc(n, size)用来动态分配一块足够存储n个size大小的空间的内存，并将内存初始化为0
reallocarray函数：reallocarray(ptr, n, size)用来将之前通过malloc、calloc或realloc函数分配的内存空间
重新分配为n个size大小的内存空间，并将原内容移动到新的内存空间中
3.目的：动态内存管理的主要目的是为了解决数据结构大小可变的问题
例如在实现链表、动态数组等数据结构时，就需要使用动态内存管理
同时，在使用完已分配的内存后，需要使用free函数及时释放内存，避免内存泄漏的问题第十章：查找（Serarch）
1.查找表
由同一类型的数据元素（或记录）构成的集合2.关键字
（1）键值 是数据元素中的某个数据项的值，又称为 键值，用它可以标识一个数据元素 （2）关键码 也可以标识一个记录的某个数据项（字段），我们称为 关键码 （3）关键字（Primary Key） 若此关键字可以唯一地标识一个记录，则称此关键字为主关键字 （4）次关键字（Secondary Key） 而对于那些可以识别多个数据元素（或记录）的关键字，我们称为 次关键字
3.查找
（1）定义
就是根据给定的某个值，在查找表中确定一个其关键字等于给定值得数据元素（或记录）
从逻辑上来说，查找所基于的数据结构是集合
集合中的记录之间没有本质关系
可是要想获得较高的查找性能
我们就不能不改变数据元素之间的关系
在存储时可以将查找集合组织成表，树等结构
比如，对于静态查找表来说，我们不妨应用线性表结构来组织数据
这样可以使用顺序查找算法，如果再对主关键字排序，则可以应用折半查找等技术进行高效的查找（2）查找类型
顺序查找：是一种简单的查找算法，它逐个遍历数据集合中的每个元素，直到找到目标元素或遍历完所有元素
它适用于数据集合无序或有序的情况，其时间复杂度为O(n)
顺序查找的实现步骤如下：
遍历：从数据集合的第一个元素开始，逐个遍历每个元素，直到找到目标元素或遍历完所有元素
比较：在遍历过程中，将当前元素与目标元素进行比较，判断它们是否相等
如果相等，则返回该元素的位置，否则继续遍历下一个元素
返回：如果遍历完所有元素都没有找到目标元素，则返回一个表示未找到的标记
分块查找（也称块状查找）：是一种将数据集合分块的算法。它将数据集合分成若干块，每块内部有序，然后对每块使用顺序查找
分块查找适用于数据集合较大的有序情况，其时间复杂度为O(log n + k)，其中n是数据集合的大小，k是块的块数
查找的实现步骤如下：
分块：将数据集合分成若干块，每块内部有序
通常可以采用如下方法进行分块：假设数据集合中的元素范围为1~n，块的大小为s，则可以将数据集合分成(n/s+1)块
例如，当元素范围为1~100，块的大小为10时，可以将数据集合分成10块
建立索引表：对于每个块，建立一个索引表，记录该块的最大元素和最小元素
索引表可以用数组或链表来实现
查找过程：在查找时，先通过索引表找到最有可能包含目标元素的块，然后对该块使用顺序查找
计算目标元素所在的块的编号：假设目标元素为x，块的大小为s，则目标元素所在的块的编号为(x-1)/s
通过索引表找到目标元素所在的块，然后对该块进行顺序查找
分块查找的优点是能够减少查找次数，提高查找效率，但需要对数据集合进行预处理，并且需要建立索引表
折半查找（又称二分查找）：是一种高效的查找算法，它适用于数据集合有序的情况
时间复杂度为O(log n)
该算法每次将待查找的元素与中间位置的元素进行比较
根据大小情况不断将查找区间缩小为一半，直到找到目标元素或者查找区间为空
哈希表查找：是一种快速的查找算法，它适用于需要快速查找的数据集合
时间复杂度为O(1)
将键通过哈希函数（Hash Function）转化为一个索引，该索引对应着哈希表中的一个位置
插入操作是将键值对存储到哈希表中，删除操作是从哈希表中删除指定键值对，查找操作是通过键直接访问对应的值
解决哈希冲突，可以采用以下方法：
开放寻址法：当发生哈希冲突时，使用一定的算法在哈希表中寻找下一个可用的空位，直到找到一个空位或回到
链地址法：在哈希表的每个位置存储一个链表，当多个键值对映射到同一索引时，将它们存储在该链表中，常见的链地址法是在每个位置使用一个链表或数组4.索引
（1）定义
就是把一个关键字与它对应的记录相关联的过程（关键字=记录）
数据结构的最终目的就是提高数据的处理速度
索引是为了加快查找速度而设计的一种数据结构
一个索引由若干个索引项构成
每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息
索引技术是组织大型数据库以及磁盘文件的一种重要技术（2）按照结构分类
索引按照结构可以分为：线性索引，树形索引和多级索引（3）三种线性索引&两种表【稠密索引-分块索引-倒排索引-多重表-倒排表】
5.二叉排序树（二叉查找树）
（1）定义
二叉排序树（Binary Sort Tree）：又称为 二叉查找树
它或者是一棵空树
或者是具有下列性质的二叉树：
A:若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
B:若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
C:它的左、右子树也分别为二叉排序树
（2）目的
构造一棵 二叉排序树 的目的，其实并不是为了排序
而是为了提高查找和插入删除关键字的速度
不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的
而二叉排序树这种非线性的结构
也有利于插入和删除的实现
（3）存储方式
A:定义
二叉排序树 是以链接的方式存储
B：执行插入或删除操作时
保持了链接存储结构在执行插入或删除操作时不用移动元素的有点（只需修改链接指针）
插入和删除的时间性能比较好
C:查找操作时
而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径
其比较次数等于给定值得结点在二叉排序树的层数
D:查找次数最少
极端情况下，查找次数最少为 1 次
即根结点就是要找的结点
E:查找次数最多
最多也不会超过树的深度
也就是说，二叉排序树的查找性能取决于二叉排序树的形状
F:二叉排序树的形状
很可惜的是，二叉排序树的形状是不确定的（想象下极端的右斜树或左斜树）
G:解决二叉排序树的形状问题
对于这个问题，解决方案就是让二叉排序树左右子树是比较平衡的
H:深度
即其深度与完全二叉树相同，均为向下取整log_2*n + 1
I:时间复杂度
那么查找的时间复杂度就为O(logn)
J:平衡二叉树（AVL 树）
近似二分查找，这种结构就称为 平衡二叉树
（4）平衡二叉树
是一种二叉排序树
其中每一个结点的左子树和右子树的高度差至多等于 1
（5）平衡因子 BF（Balance Factor）
将二叉树上结点的左子树深度减去右子树深度的值称为 平衡因子 BF
平衡二叉树上所有结点的平衡因子只可能是 -1、0 和 1
只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的
（6）最小不平衡子树
距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树，我们称为 最小不平衡子树
平衡二叉树实现原理
平衡二叉树构建的基本思想就是在构建二叉树排序树的过程中
每当插入一个结点时
先检查是否因插入而破坏了树的平衡性
若是，则找出最小不平衡子树
在保持二叉排序树特性的前提下
调整最小不平衡子树中各结点之间的链接关系
进行相应的旋转，使之成为新的平衡子树6.多路查找树
对于 树 来说，一个结点只能存储一个元素 那么在元素非常多的时候，就会使得要么树的度非常大（结点拥有子树的个数的最大值） 要么树的高度非常大，甚至两者都必须足够大才行 这就使得内存存取外存次数非常多 这显然成了时间效率上的瓶颈 这迫使我们要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念 其每一个结点的孩子树可以多于两个 且每一个结点处可以存储多个元素 由于它是查找树，因此所有元素之间存在某种特定的排序关系（即其是有序的）
7.散列表（哈希表）
（1）定义 散列表（Hash table，也叫哈希表）是一种根据关键码值(Key value)而直接进行访问的数据结构 它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度 这个映射函数叫做散列函数，存放记录的数组叫做散列表 （2）散列表【哈希表（Hash table）】 采用散列技术将记录存储在一块连续的存储空间中 则这块连续存储空间称为 散列表 或 哈希表 （3）散列地址 那么关键字对应的记录存储位置我们称为 散列地址 （4）散列函数设计原则 A:计算简单： 散列函数的计算时间不应该超过其他查找技术与关键字比较的时间 B:散列地址分布均匀： 防止散列冲突最好的办法就是尽量让散列地址均匀地分布在存储空间中 这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间数据结构—— 构造散列函数的六种方法【直接定址法-数字分析法-平方取中法-折叠法-除留余数法-随机数法】_构造散列函数的方法
第十一章：内部排序（Internal sort）
定义：内部排序（也称内部排序算法）是指利用计算机内部存储器（RAM）进行的排序方法 分类：内部排序算法包括 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序、基数排序 内部排序的优缺点： 优点： 算法实现简单，比较适用于数据规模较小的排序 某些排序算法可以利用计算机的快速运算能力，提高排序效率 缺点： 对于数据规模较大的排序，排序效率较低 受计算机内部存储器的影响，排序数据的范围有限 某些排序算法的时间复杂度较高，排序效率较低内部排序算法【直接插入排序-冒泡排序-选择排序-插入排序-希尔排序-归并排序-快速排序-堆排序-折半插入排序-二分查找-路插入排序-表插入排序-简单选择排序-直接选择排序-树形选择】
直接插入排序： 直接插入排序是一种简单的排序算法，其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入 时间复杂度为O(n^2) 折半插入排序： 折半插入排序是对直接插入排序的一种改进，通过利用二分查找的方法确定插入的位置，可以减少比较次数 时间复杂度仍为O(n^2) 希尔排序： 希尔排序也称为缩小增量排序，其基本思想是将原数据集合分割成若干个子序列 然后对子序列分别进行直接插入排序，逐步减小子序列的间隔，直至整个序列基本有序或只剩一个元素时停止 最后再进行一次直接插入排序 时间复杂度为O(n log n) 冒泡排序： 冒泡排序是一种简单直观的排序算法，其工作原理是通过重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来 时间复杂度为O(n^2) 快速排序： 快速排序是一种分治的排序算法，通过选定一个比较基准 然后将数组分为两部分，一部分的所有元素都比另一部分的元素小 然后再对这两部分分别进行快速排序，最终整个序列有序 时间复杂度为平均O(n log n)，最坏情况O(n^2) 简单选择排序： 简单选择排序是一种简单直观的排序算法，其工作原理是首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。如此重复，直到所有元素均排序完毕 时间复杂度为O(n^2) 堆排序： 利用堆这种数据结构所设计的一种排序算法，它可以将一个无序序列构建成一个有序序列 时间复杂度为O(n log n) 归并排序： 归并排序是一种基于分治策略的排序算法，它将原始数组分割成两个子数组，对每个子数组进行排序，然后将结果合并在一起 这个过程可以递归地进行，直到数组的大小为1 时间复杂度为O(n log n) 基数排序： 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字段，然后按每个位数分别比较 时间复杂度取决于最大数的位数，通常为O(nk)，其中k是最大数字的位数
第十二章：外部排序（External sort）
1.定义和分类
定义：外部排序是指当待排序的数据太大而不能全部装入内存时
将数据存储在外部存储器（如磁盘）上，然后通过一系列的输入、输出和部分排序等操作，将数据按一定的顺序排列
外部排序的种类包括：
外部归并排序：与内部归并排序类似，将待排序数据分割成若干个子序列
每个子序列存储在内存中，然后通过多次归并操作将子序列合并为有序序列
外部基数排序：与内部基数排序类似，将待排序数据按照位数分割成若干个子序列
每个子序列存储在内存中，然后按照位数的顺序对子序列进行排序，最后将排序后的子序列
外部分块链表排序：将待排序数据分割成多个块，每个块存储在内存中
然后通过链表的方式将块中的数据进行排序，最后将链表中的有序数据合并2.多路归并与败者树
多路归并排序： 多路归并排序是一种外部排序算法，它将待排序数据分割成多个子序列，每个子序列存储在内存
具体实现过程如下：
（1）将待排序数据按照关键字进行分组，每个组包含多个记录，记录的个数不超过缓冲区的大小
（2）对每个组内的记录进行排序，可以使用稳定的排序算法，如插入排序或归并排序
（3）将每个组内的有序记录写入磁盘，形成多个子序列
（4）创建一个最小堆，将每个子序列的第一个元素加入堆中
（5）取出堆顶元素（即当前最小的元素），将其加入输出序列中
（6）从该元素所在的子序列中取出下一个元素，将其与堆顶元素进行比较，如果比堆顶元素小，则将它加入堆中
重复这个过程，直到该子序列中的所有元素都被处理过。
（7）如果堆不为空，重复步骤5和6，直到输出序列中包含了所有记录
多路归并排序的时间复杂度为O(nlogm)，其中n是待排序记录的数量，m是子序列的个数
空间复杂度取决于每次归并所需的缓冲区大小，一般为O(m)
败者树：败者树是一种基于比较的外部排序算法，它可以用于外部归并排序、外部基数排序等多种排序算法中
败者树是一种树状数据结构，它将待排序数据分成若干个子序列，每个子序列存储在内存中，然后通过比较操作将子序列中的记录按照一定的顺序排列
具体实现过程如下：
（1）将待排序数据按照关键字进行分组，每个组包含多个记录，记录的个数不超过缓冲区的大小
（2）对每个组内的记录进行比较操作，将较小的记录放入较低的优先级队列中，较大的记录放入较高的优先级队列中
（3）重复步骤2，直到只剩下一个队列为止。此时，该队列中的记录按照关键字从小到大排列
（4）将该队列中的记录按照一定的顺序输出即可得到有序序列。
败者树的时间复杂度为O(nlogm)，其中n是待排序记录的数量，m是子序列的个数
空间复杂度取决于每次比较所需的缓冲区大小，一般为O(m)
败者树是一种高效的外部排序算法，它可以有效地处理大量数据，并且具有较好的稳定性
在实际应用中，败者树可以与其他外部排序算法结合使用，以提高外部排序的效率3.最佳归并树
定义：最佳归并树是一种基于比较的排序算法
它采用了二分法和完全二叉树的思路，能够在归并过程中选择最小的元素进行归并
从而达到总比较次数最少的归并效果。它是归并排序算法中的一种最优情况
但需要预处理，构造时间较长
最佳归并树的构造方法如下：
（1）将待排序的记录序列分成若干个子序列，每个子序列包含的记录数量不超过缓冲区的大小
（2）对每个子序列进行排序
（3）将所有子序列按照从左到右的顺序排列，形成一个完全二叉树的层次结构
（4）从根节点开始，每次取出两个最小的子序列进行归并，直到只剩下一个子序列为止
（5）每次归并时，记录下比较的次数，最后将所有比较次数相加即可得到总比较次数十三章：文件（Document）
更多推荐
3140
0- 0
已为社区贡献1条内容
所有评论(0)