公告

随便写写

标签

“指令流水线” 408 408学习 408排序算法 408操作系统 408数据结构 408数据链路层 408文件系统 408网络层 408计算机 408计算机组成原理 408计算机统考 408计算机网络 408计算机考研 660题复盘 802.11 ARP B+树 BFS B树 B树与B+树 CPU调度 CSMA协议 DFS DNS ICMP IO接口 IO方式 IO系统 IO缓冲 IPv4 IP多播 OSPF协议 RIP协议 SPOOLING技术 TCP协议 UDP VLAN 一元微分学一元微分概念一元积分几何应用一元积分学一元积分学几何应用一元积分学强化一元积分计算一维随机变量一轮复习三重积分上分位点不等式证明专业课复习专业课复盘专业课学习记录中值定理中央处理器中断与异常中断和异常习题复盘二分查找二叉查找树二叉树二叉树与森林转换二叉树遍历二次型二维连续型随机变量二维随机变量二重积分交错级数假设检验偏导数定义傅里叶级数全微分全概率公式关键路径冒泡排序最小生成树最短路径算法几何应用函数极限函数极限与连续函数连续函数连续与极限函数连续性分布函数分布函数法分段虚拟存储系统刷题复盘区间估计十字链表协方差单词背诵卷积公式卷积法历年真题去心邻域参数估计反常积分变限积分古典概型同步互斥向量代数向量组向量组线性相关性固态硬盘图的基本概念图的存储结构图论知识点图论算法基数排序基础巩固堆排序备考休息日备考休整复习休整复合函数求导多元函数微分学多元微分多元微分学多元微分学几何应用多元积分学多元积分学几何应用多线程模型多维随机变量多维随机变量分布大数定律大数定律与中心极限定理大题专项训练子网划分存储器存储系统学习复盘学习日志学习计划复盘学习记录孩子兄弟表示法定积分几何应用定积分强化定积分物理应用对称性与中值定理导数导数与微分导数复习导数定义差错控制编码常微分方程常见概率分布幂级数展开幂级数求和并查集广域网应用层协议张宇1000题强化习题复盘强化课程选型强化阶段规划归并排序微分中值定理微分方程微分方程强化微程序控制器快速排序总线事务与定时总线知识点拉格朗日中值定理拉格朗日乘数法括号处理排序算法操作系统操作系统进程线程收敛半径散列表数列极限数字特征数据结构数据通路数理统计数理统计三大分布文件保护文件系统文件系统索引存储方程根存在性无穷积分无穷级数无穷级数求和时间复杂度曲率曲线曲面积分曲线积分曲面积分有界性判定极值点与拐点极值问题极坐标积分次序交换极大似然估计极限极限与连续极限计算极限证明题栈与队列树的双亲表示法树的基础树的遍历概率论概率论与数理统计概率论强化概率论数字特征正态总体抽样分布武忠祥高数强化死锁泰勒公式深度优先搜索(DFS) 渐近线滑动窗口协议物理应用特征值与特征向量知识点梳理矩阵矩阵存储矩阵秩硬件驱动硬布线控制器磁盘管理积分不等式积分中值定理积分判别法第一类曲线积分第二类曲线积分第二类曲面积分等价无穷小算法复杂度系统调用红宝书单词级数级数专题级数复习级数强化级数收敛判定级数收敛判断线性代数线性代数二次型线性方程组线性表线性表链式存储线程与进程经典同步问题网络互联设备置信区间考研408 考研专业课考研学习考研数学考研英语自动重传请求薄弱点复盘虚拟存储虚拟存储器行列式表达式树表达式转换计算机组成原理计算机网络计算机网络综合题贝叶斯公式路由器路由聚合进程与线程进程管理进程资源共享连续函数连续型一维随机变量连续型随机变量连续多元随机变量分布迪杰斯特拉邻接表链表链表学习错题整理长难句长难句分析阶段性复盘隐函数求导随机变量数字特征霍夫曼编码页式存储页面置换算法顺序表题型梳理高数三重积分高数竞赛高等数学高阶求导高阶矩阵

公告

随便写写

Learn More

标签

“指令流水线” 408 408学习 408排序算法 408操作系统 408数据结构 408数据链路层 408文件系统 408网络层 408计算机 408计算机组成原理 408计算机统考 408计算机网络 408计算机考研 660题复盘 802.11 ARP B+树 BFS B树 B树与B+树 CPU调度 CSMA协议 DFS DNS ICMP IO接口 IO方式 IO系统 IO缓冲 IPv4 IP多播 OSPF协议 RIP协议 SPOOLING技术 TCP协议 UDP VLAN 一元微分学一元微分概念一元积分几何应用一元积分学一元积分学几何应用一元积分学强化一元积分计算一维随机变量一轮复习三重积分上分位点不等式证明专业课复习专业课复盘专业课学习记录中值定理中央处理器中断与异常中断和异常习题复盘二分查找二叉查找树二叉树二叉树与森林转换二叉树遍历二次型二维连续型随机变量二维随机变量二重积分交错级数假设检验偏导数定义傅里叶级数全微分全概率公式关键路径冒泡排序最小生成树最短路径算法几何应用函数极限函数极限与连续函数连续函数连续与极限函数连续性分布函数分布函数法分段虚拟存储系统刷题复盘区间估计十字链表协方差单词背诵卷积公式卷积法历年真题去心邻域参数估计反常积分变限积分古典概型同步互斥向量代数向量组向量组线性相关性固态硬盘图的基本概念图的存储结构图论知识点图论算法基数排序基础巩固堆排序备考休息日备考休整复习休整复合函数求导多元函数微分学多元微分多元微分学多元微分学几何应用多元积分学多元积分学几何应用多线程模型多维随机变量多维随机变量分布大数定律大数定律与中心极限定理大题专项训练子网划分存储器存储系统学习复盘学习日志学习计划复盘学习记录孩子兄弟表示法定积分几何应用定积分强化定积分物理应用对称性与中值定理导数导数与微分导数复习导数定义差错控制编码常微分方程常见概率分布幂级数展开幂级数求和并查集广域网应用层协议张宇1000题强化习题复盘强化课程选型强化阶段规划归并排序微分中值定理微分方程微分方程强化微程序控制器快速排序总线事务与定时总线知识点拉格朗日中值定理拉格朗日乘数法括号处理排序算法操作系统操作系统进程线程收敛半径散列表数列极限数字特征数据结构数据通路数理统计数理统计三大分布文件保护文件系统文件系统索引存储方程根存在性无穷积分无穷级数无穷级数求和时间复杂度曲率曲线曲面积分曲线积分曲面积分有界性判定极值点与拐点极值问题极坐标积分次序交换极大似然估计极限极限与连续极限计算极限证明题栈与队列树的双亲表示法树的基础树的遍历概率论概率论与数理统计概率论强化概率论数字特征正态总体抽样分布武忠祥高数强化死锁泰勒公式深度优先搜索(DFS) 渐近线滑动窗口协议物理应用特征值与特征向量知识点梳理矩阵矩阵存储矩阵秩硬件驱动硬布线控制器磁盘管理积分不等式积分中值定理积分判别法第一类曲线积分第二类曲线积分第二类曲面积分等价无穷小算法复杂度系统调用红宝书单词级数级数专题级数复习级数强化级数收敛判定级数收敛判断线性代数线性代数二次型线性方程组线性表线性表链式存储线程与进程经典同步问题网络互联设备置信区间考研408 考研专业课考研学习考研数学考研英语自动重传请求薄弱点复盘虚拟存储虚拟存储器行列式表达式树表达式转换计算机组成原理计算机网络计算机网络综合题贝叶斯公式路由器路由聚合进程与线程进程管理进程资源共享连续函数连续型一维随机变量连续型随机变量连续多元随机变量分布迪杰斯特拉邻接表链表链表学习错题整理长难句长难句分析阶段性复盘隐函数求导随机变量数字特征霍夫曼编码页式存储页面置换算法顺序表题型梳理高数三重积分高数竞赛高等数学高阶求导高阶矩阵

公告

随便写写

Learn More

标签

“指令流水线” 408 408学习 408排序算法 408操作系统 408数据结构 408数据链路层 408文件系统 408网络层 408计算机 408计算机组成原理 408计算机统考 408计算机网络 408计算机考研 660题复盘 802.11 ARP B+树 BFS B树 B树与B+树 CPU调度 CSMA协议 DFS DNS ICMP IO接口 IO方式 IO系统 IO缓冲 IPv4 IP多播 OSPF协议 RIP协议 SPOOLING技术 TCP协议 UDP VLAN 一元微分学一元微分概念一元积分几何应用一元积分学一元积分学几何应用一元积分学强化一元积分计算一维随机变量一轮复习三重积分上分位点不等式证明专业课复习专业课复盘专业课学习记录中值定理中央处理器中断与异常中断和异常习题复盘二分查找二叉查找树二叉树二叉树与森林转换二叉树遍历二次型二维连续型随机变量二维随机变量二重积分交错级数假设检验偏导数定义傅里叶级数全微分全概率公式关键路径冒泡排序最小生成树最短路径算法几何应用函数极限函数极限与连续函数连续函数连续与极限函数连续性分布函数分布函数法分段虚拟存储系统刷题复盘区间估计十字链表协方差单词背诵卷积公式卷积法历年真题去心邻域参数估计反常积分变限积分古典概型同步互斥向量代数向量组向量组线性相关性固态硬盘图的基本概念图的存储结构图论知识点图论算法基数排序基础巩固堆排序备考休息日备考休整复习休整复合函数求导多元函数微分学多元微分多元微分学多元微分学几何应用多元积分学多元积分学几何应用多线程模型多维随机变量多维随机变量分布大数定律大数定律与中心极限定理大题专项训练子网划分存储器存储系统学习复盘学习日志学习计划复盘学习记录孩子兄弟表示法定积分几何应用定积分强化定积分物理应用对称性与中值定理导数导数与微分导数复习导数定义差错控制编码常微分方程常见概率分布幂级数展开幂级数求和并查集广域网应用层协议张宇1000题强化习题复盘强化课程选型强化阶段规划归并排序微分中值定理微分方程微分方程强化微程序控制器快速排序总线事务与定时总线知识点拉格朗日中值定理拉格朗日乘数法括号处理排序算法操作系统操作系统进程线程收敛半径散列表数列极限数字特征数据结构数据通路数理统计数理统计三大分布文件保护文件系统文件系统索引存储方程根存在性无穷积分无穷级数无穷级数求和时间复杂度曲率曲线曲面积分曲线积分曲面积分有界性判定极值点与拐点极值问题极坐标积分次序交换极大似然估计极限极限与连续极限计算极限证明题栈与队列树的双亲表示法树的基础树的遍历概率论概率论与数理统计概率论强化概率论数字特征正态总体抽样分布武忠祥高数强化死锁泰勒公式深度优先搜索(DFS) 渐近线滑动窗口协议物理应用特征值与特征向量知识点梳理矩阵矩阵存储矩阵秩硬件驱动硬布线控制器磁盘管理积分不等式积分中值定理积分判别法第一类曲线积分第二类曲线积分第二类曲面积分等价无穷小算法复杂度系统调用红宝书单词级数级数专题级数复习级数强化级数收敛判定级数收敛判断线性代数线性代数二次型线性方程组线性表线性表链式存储线程与进程经典同步问题网络互联设备置信区间考研408 考研专业课考研学习考研数学考研英语自动重传请求薄弱点复盘虚拟存储虚拟存储器行列式表达式树表达式转换计算机组成原理计算机网络计算机网络综合题贝叶斯公式路由器路由聚合进程与线程进程管理进程资源共享连续函数连续型一维随机变量连续型随机变量连续多元随机变量分布迪杰斯特拉邻接表链表链表学习错题整理长难句长难句分析阶段性复盘隐函数求导随机变量数字特征霍夫曼编码页式存储页面置换算法顺序表题型梳理高数三重积分高数竞赛高等数学高阶求导高阶矩阵

1382 字

4 分钟

考研专业课学习记录2026-07-19

2026-07-19

major

考研专业课

/

408排序算法

/

学习记录

考研专业课学习记录 | 2026-07-19#

今日学习内容#

两个半小时外部排序和内部排序的总结

AI知识点带复盘#

一、内部排序核心考点复盘#

内部排序指全部数据可载入内存完成的排序操作，根据实现逻辑可分为5大类，是408选择题、大题高频考察模块：

插入排序类
- 直接插入排序：稳定排序，时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ ，适用于基本有序的小规模数据场景，考研常考察哨兵优化、折半插入的改进逻辑。
- 希尔排序：不稳定排序，通过分组插入降低逆序对数量，平均时间复杂度 $O(n^{1.3}\sim n^2)$ ，空间复杂度 $O(1)$ ，是直接插入排序的优化版本，考研常考察增量序列设计与稳定性问题。
交换排序类
- 冒泡排序：稳定排序， $O(n^2)$ 时间复杂度，适合小规模数据，考研常考察Early Exit优化逻辑。
- 快速排序：不稳定排序，平均时间复杂度 $O(n\log_2n)$ ，最坏 $O(n^2)$ （数据已有序、枢轴选择不合理时触发），空间复杂度 $O(\log_2n\sim n)$ ，是考研大题核心考点，需掌握Partition划分过程、递归/非递归实现、最优枢轴选择方法（三数取中法）。
选择排序类
- 简单选择排序：不稳定排序， $O(n^2)$ 时间复杂度，空间复杂度 $O(1)$ ，每次选择最值元素交换，考研常考察其与堆排序的区别。
- 堆排序：不稳定排序，时间复杂度 $O(n\log_2n)$ ，空间复杂度 $O(1)$ ，需掌握大顶堆/小顶堆建堆、堆调整、完整执行流程，是选择类排序的核心考察点。
归并排序：稳定排序，时间复杂度 $O(n\log_2n)$ ，空间复杂度 $O(n)$ （依赖辅助数组），基于分治思想，考研常考察二路归并的递归/非递归实现、与其他排序的复杂度对比。
基数排序：稳定排序，基于关键字分配+收集实现，时间复杂度 $O(d(n+r))$ （ $d$ 为关键字位数， $r$ 为基数），空间复杂度 $O(n+r)$ ，适用于多关键字排序场景，考研常考察执行流程与复杂度分析。

二、外部排序核心考点复盘#

外部排序指数据量过大无法全部载入内存，需结合磁盘等外部存储完成的排序，核心流程为「生成初始归并段→多路归并」，考研考察重点如下：

外部排序时间构成：总耗时 = 读写磁盘时间 + 内部排序时间 + 归并段归并时间，其中磁盘读写耗时占比最高，是优化核心。
初始归并段生成：常规方法是将文件分块读入内存完成内部排序后写回磁盘，得到等长初始归并段；通过置换-选择排序算法可以生成长度更长的初始归并段，减少后续归并趟数。
多路归并与败者树
- $k$ 路归并的归并趟数 $s=\lceil\log_k m\rceil$ （ $m$ 为初始归并段总数）， $k$ 越大归并趟数越少，但单次归并的内部处理耗时增加，考研常考察 $k$ 值对总IO次数的影响。
- 败者树可以优化 $k$ 路归并的比较次数，将单次归并的比较次数从 $O(k)$ 降低到 $O(\log_2k)$ ，是考研考察的核心优化考点。
最佳归并树：通过构造哈夫曼树，将归并段长度作为权值，最小化总归并IO次数；考研常考察当初始归并段数量无法构成满 $k$ 叉树时，需要补充长度为0的虚段调整结点数。

问题与反思#

前期容易混淆各类内部排序算法的稳定性与适用场景，曾将希尔排序、快速排序误记为稳定排序，后续需要通过对比表格强化记忆。
外部排序最佳归并树的虚段补充规则容易出错，尤其是当 $k\neq2$ 时，对 $(k-1)|(n-1)$ 的验证逻辑掌握不熟练。
多路归并的总IO次数推导逻辑不够熟练，需要结合经典例题重新梳理读写次数的计算方法。

收获与总结#

完整梳理了内部排序5大类算法的核心特性、复杂度、稳定性与考察方向，形成了清晰的对比框架，可以快速区分不同算法的适用场景。
掌握了外部排序的完整流程与优化手段，明确磁盘IO耗时是外部排序优化的核心目标，理解了置换-选择、败者树、最佳归并树的设计逻辑与作用。
明确了408排序模块的出题规律：选择题多考察稳定性、复杂度对比、外部排序IO计算；大题多考察快速排序、堆排序的实现与外部排序综合计算。

💡 碎碎念：踏实吃透每一个知识点！

文档内容由 AI 辅助生成

如果这篇文章对你有帮助，欢迎分享给更多人！

考研专业课学习记录2026-07-19

https://elysiaweb.vercel.app/posts/408/7-19/

作者

程翊雪

发布于

2026-07-19

许可协议

Unlicensed

部分信息可能已经过时

考研数学学习记录2026-07-20

考研英语学习记录2026-07-19

一点碎碎念

考研专业课学习记录 | 2026-07-19#

今日学习内容#

AI知识点带复盘#

一、内部排序核心考点复盘#

二、外部排序核心考点复盘#

问题与反思#

收获与总结#

目录