广州做一个网站多少钱,html5企业网站,照明网站建设,广东广电网络东莞分公司前言
本文基础知识部分来自于b站#xff1a;分享笔记的好人儿的思维导图与王道考研课程#xff0c;感谢大佬的开源精神#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析#xff0c;本人技术…前言
本文基础知识部分来自于b站分享笔记的好人儿的思维导图与王道考研课程感谢大佬的开源精神习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析本人技术有限最终数据清洗结果不够理想相关CSDN文章便没有发出。
考研真题待更新 欢迎订阅专栏408直通车 请注意本文中的部分内容来自网络搜集和个人实践如有任何错误请随时向我们提出批评和指正。本文仅供学习和交流使用不涉及任何商业目的。如果因本文内容引发版权或侵权问题请通过私信告知我们我们将立即予以删除。 文章目录 前言第八章 排序概述排序算法的稳定性根据数据是否在内存中进行分类小结 插入排序直接插入排序折半插入排序小结 希尔排序小结 交换排序概述冒泡排序小结 快速排序 选择排序概述简单选择排序小结 堆排序小结 堆的插入删除插入删除 二路归并排序实现过程 基数排序基本概念实现过程性能分析稳定性应用补充 排序算法的分析结论 外部排序外部排序基本概念构造初始“归并段第一趟归并第二趟归并第三趟归并 外部排序的方法优化都减少归并趟数s减少磁盘读写次数多路平衡归并与败者树置换-选择排序生成初始归并段最佳归并树k叉哈夫曼树 代码快排归并二分查找可用于折半 第八章 排序
概述
排序
将无序序列排成一个有序序列的运算如果排序的数据结点包含多个数据域排序针对一个域
算法的稳定性 能够使任何数值相等的元素排序以后相对次序不变 稳定性只对结构类型数据排序有意义例先按数学成绩排序再按总分排序
根据数据是否在内存中进行分类 内部排序 在排序期间元素全部存放在内存中的排序 外部排序 在排序期间元素无法全部同时存放在内存中必须在排序的过程中根据要求不断地在内、外存之间移动的排序
小结 插入排序
直接插入排序 概念 首先以一个元素为有序的序列然后讲后面的元素依次插入到有序的序列中适合的位置直到所有元素都插入有序序列 实现过程 排序某时刻将待排序表分割为三部分顺序查出L(i)在L[1…i-1]的插入位置k 将L[k…i-1]中的所有元素依次后移一个位置将L(i)复制到L(k) 哨兵 性能分析 时间复杂度平均O(n^2) 最好有序O(n) 最坏逆序O(n^2) 空间复杂度O(1) 稳定性 稳定 补充提高速度 减少元素比较次数引入折半插入排序 减少元素的移动次数引入希尔排序每次移动步幅增大
折半插入排序 实现过程 首先确定折半插入排序的范围利用折半查找找到插入的位置然后一次性对数据进行移动最后插入该元素 性能分析 时间复杂度比较次数减少O(nlogn)移动次数不变整体O(n^2) 空间复杂度O(1) 稳定性 稳定 小结 希尔排序 概念 本质上还是插入排序只是把待排序列分成几个子序列分别对子序列进行直接插入排序 实现过程 先取一个小于n的步长d把表中数据分为d组所有距离为d的倍数记录在同一组组内进行直接插入排序 缩小步长d不断重复直到d1为止 若d5跨越6个数 性能分析 时间复杂度平均O(n^1.3) 最坏O(n^2) 空间复杂度O(1) 稳定性 不稳定
小结 交换排序
概述
根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置
冒泡排序 实现过程 从前往后从后往前两两比较相邻元素的值若逆序则交换直到序列比较完 每一趟会将最大的元素交换到待排序列最后一个位置将较小的元素交换到待排序列第一个位置 进行下一趟排序前一趟确定元素不参与 如果某一趟排序过程中未发生交换则可以提前结束 性能分析 时间复杂度平均O(n^2) 最好O(n) 最坏O(n^2) 空间复杂度O(1) 稳定性 稳定 补充 冒泡排序产生的有序子序列一定全局有序即每趟会将一个元素放到最终的位置上
小结 快速排序 实现过程 首先选取一个元素作为枢轴以枢轴为界将排序表分为两个部分左边小于枢轴右边大于枢轴 然后对着两部分分别递归重复上述步骤直到每个部分内只有一个元素或空为止 性能分析 时间复杂度 快速排序的运行时间与划分是否对称有关应尽量选取可以将数据中分的枢轴元素想象一颗二叉树 最好情况待排序列越无序算法效率越高O(nlog2n) 最坏情况待排序列越有序算法效率越高O(n^2) 平均情况快速排序平均情况下与最优情况下运行时间很接近是所有内部排序算法中平均时间最优的排序算法 空间复杂度平均O(log2n) 最好O(log2n) 最坏O(n) 稳定性 不稳定 优化划分均匀 选头中尾三个位置的元素取中间值为枢轴元素 随机选一个元素作为枢轴元素 选择排序
概述 每一趟如第i躺在后面n-i1i1,2,…,n-1个待排序元素中选取关键字最小的元素作为有序子序列的第i个元素直到第n-1趟完成 选择排序的时间性能不随记录序列中关键字的分布而改变
简单选择排序 实现过程 假设排序表为L[1…n]第i躺排序即从L[1…n]中选择关键字最小的元素与L(i)交换 i每次增加每趟排序可以确定一个元素的最终位置 性能分析 时间复杂度O(n^2) 空间复杂度O(1) 稳定性 不稳定
小结 堆排序 基本概念 堆 堆是一棵完全二叉树而且满足任何一个非叶结点的值都不大于或不小于其左右孩子结点的值 大根堆 每个结点的值都不小于它的左右孩子结点的值 小根堆 每个结点的值都不大于它的左右孩子结点的值 实现过程 建大小根堆O(n) 从后向前调整所有非终端结点使其满足堆的性质[0, ⌊n/2⌋] 检查是否根大于小于等于左右孩子小大元素不断下坠下坠过程需不断检查与左右孩子的大小 调整大小根堆O(nlog2n) 将最大小根结点与最后一个结点互换 按建堆过程调整结点 性能分析 时间复杂度O(nlog2n) 空间复杂度O(1) 稳定性 不稳定
小结 堆的插入删除
插入 删除 二路归并排序 实现过程 假定待排序表有n个记录可以看成n个有序子表每个子表长度1两两归并得到⌈n/2⌉个长度为2或1的有序表再两两归并直到合并为长度n的有序表 性能分析 时间复杂度O(nlog2n) 空间复杂度O(n) 稳定性 稳定 特点 比较次数与初始状态无关 只有归并排序O(nlog2n)且稳定
基数排序
基本概念 最高位优先MSD法按关键字位权重递减依次逐层划分成若干更小的子序列最后将所有子序列依次连接成一个有序序列 最低位优先LSD法按关键字位权重递增依次进行排序最后形成一个有序序列
实现过程
采用多关键字排序思想即基于关键字各位的大小进行排序的借助“分配”和“收集”两种操作对单逻辑关键字进行排序直到所有关键字均已排序完毕 性能分析 时间复杂度 基数排序需要进行k躺分配和收集一趟分配需要O(n)一趟收集需要O(m)所以时间复杂度为O(k(nm)) 空间复杂度 链式存储王道O(m)一趟需要辅助存储空间mm个桶的头尾指针 顺序存储O(nm)桶临时存放数组
稳定性
稳定
应用 关键字便于分k组即k较小时 每组关键字取值范围不大即m较少时 元素个数n较大时
补充
对数字排序时仅能使用最低位优先法若高位优先最后排低位时会打乱顺序
排序算法的分析 王道书中基数排序d为待排元素的维度r为基数的个数空间复杂度王道采用链式存储故额外空间仅每个桶的头尾指针
结论 若文件初始状态接近有序则选用直接排序或冒泡排序为宜 要求排序稳定且时间复杂度O(nlog2n)则选用归并排序 若n很大记录关键字位数较少且可分解时采用基数排序 当记录信息量较大为避免消耗大量时间移动记录可用链表作为存储结构 简单选择排序、堆排序、归并排序的时间性能不随记录序列中关键字的分布而改变
外部排序 外部排序基本概念 构造初始“归并段 第一趟归并 第二趟归并 第三趟归并 对大文件进行排序因为文件中的记录很多、信息量庞大无法将整个文件复制到内存进行排序 需要将待排序的记录存储在外存上排序时再把数据一部分一部分地调入内存进行排序在排序过程中需要多次进行内存和外存的交换
外部排序的方法 基本概念 文件通常是按块存储在磁盘上的操作系统也按块读写 外部排序过程中的时间代价主要考虑访存次数I/O次数 步骤采用归并排序 生成r个初始归并段内部排序 根据内存缓冲区大小将外存文件分为r个子文件依次读入内存并利用内部排序方法进行排序并将内部有序的子文件重新写回外存 进行s躺k路归并 s ⌈logk r⌉ k路归并 将k个归并段的块读入k个输入缓冲区 用归并排序从k个归并段中选出几个最小记录暂存到输出缓冲区中 当输出缓冲区满时写出外存 性质 每趟归并中最多只有k个段归并为一个 若总共有m个归并段参与s趟归并后得⌈m/k⌉新归并段 若要进行k路归并排序内存需要1个输出缓冲区 k个输入 时间开销 读写外存时间内部排序所需时间内部归并所需时间
优化都减少归并趟数s减少磁盘读写次数 增大归并路数k进行多路平衡归并 代价1需要增加相应的输入缓冲区 代价2每次从k个归并段中选一个最小元素需要k-1次关键字比较 减少初始归并段个数r 多路平衡归并与败者树 引入 为了减少优化1代价2减少每次k个归并段找最小关键字的比较次数 思想 k个叶结点分布存放k个归并段在归并过程中当前参加比较的记录非叶结点用了记忆左右子树中“失败者”记录段号让胜者往上继续进行比较直到根结点 性能 k路归并的败者树深度⌈log2 k⌉ 总的比较次数由(n-1)(k-1)减少到(n-1)⌈log2 k⌉ 注意归并路数k过大时虽然趟数减少但读写外存次数仍会增加
置换-选择排序生成初始归并段 引入 即优化2减少初始归并段数量r 实现如图红字 最佳归并树k叉哈夫曼树 引入 为减少磁盘I/O次数归并段读入读出合并先后次序 结构概述 叶结点表示初始归并段权值表示该归并段的长度非叶结点代表归并形成的新归并段 叶结点到根的路径长度表示其参加归并的趟数 归并树的带权路径长度WPL为归并过程中的总读记录数 归并过程中的磁盘I/O次数 归并树的WPL * 2 构造 补充虚段 若(初始归并段数量-1) % (k-1) 0说明刚好可以构成严格k叉树此时无需添加虚段 若(初始归并段数量-1) % (k-1) u ! 0则需要补充(k-1) - u个虚段 构造k叉哈夫曼树 每次选择k个根结点权值最小的树合并并将k个根结点的权值之和作为新的根结点的权值
代码
快排
思路基于分治思想 确定分界点取左边界去中间点随机取 调整区间分x与x两部分分别是[l, j]、[j1, r] 递归左右 void quick_sort(vectorintq, int l, int r){if (l r) return; //注意这里是int i l - 1, j r 1, x q[l r 1];while (i j){while (q[i] x); //注意这里无论结果如何i都会1故初始化时il-1且才能跳出循环while (q[--j] x);if (i j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j 1, r);}归并
思路基于分治思想 确定分界点: 中间点 midlr1 递归分界点左右 归并 void merge_sort(int q[], int l, int r){if (l r) return; //return边界int mid l r 1;merge_sort(q, l, mid); //排序左半merge_sort(q, mid 1, r); //排序右半int k 0, i l, j mid 1; //将ij分别指向两数组第一个元素while (i mid j r) //若两数组都没结束选小的进if (q[i] q[j]) tmp[k ] q[i ];else tmp[k ] q[j ];while (i mid) tmp[k ] q[i ]; //一数组结束另外一数组剩下元素依次进while (j r) tmp[k ] q[j ];for (i l, j 0; i r; i , j ) q[i] tmp[j];}二分查找可用于折半 本质可以划分为满足某种性质与不满足某种性质的两个区间用二分法可以找到两区间边界的左右两个点。 int bsearch_1(int l, int r) //寻找右边界{while (l r){int mid l r 1 1; //右边界需1if (q[mid]k) r mid-1; //mid不满足直接将右边界置mid左边else l mid; //左边界一点点贴近右边界}return l;}int bsearch_2(int l, int r) //寻找左边界同理{while (l r){int mid l r 1;if (q[mid]k) l mid1;else r mid;}return l;}
