网站软件下载安装免费版wordpress右侧空白

网站软件下载安装免费版,wordpress右侧空白,怎样在网站做转向连接,优购物官方网站直播#x1f3e0; 个人主页: EXtreme35 #x1f4da; 个人专栏: 专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践 目录 一、双向选择排序1.1 为什么要“双向”#xf… 个人主页:EXtreme35 个人专栏:专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践目录一、双向选择排序1.1 为什么要“双向”1.2 核心思想温水煮青蛙1.3 实现代码1.4 详解致命的Bug二、堆排序2.1 什么是堆2.2 核心武器向下调整建堆2.3 第一阶段建堆2.4 第二阶段排序逻辑2.5 实现代码三、算法对比与深度总结3.1 复杂度与性能的“降维打击”3.2 写作感悟写代码就是“画地图”在排序算法的学习之路上选择排序和堆排序是两座必须翻越的大山。前者是直觉的延伸后者是数据结构的精妙运用。选择排序是一种非常简单直观的排序算法工作原理可以概括为“每次从未排序的队伍中选出最优者让它归位”。具体来说算法在每一轮都会遍历所有还未排序的元素从中找出最小或最大的一个然后将其与未排序部分的第一个元素交换位置。这个操作能确保每一轮过后都有一个元素被精准地放在它最终的正确位置上。接着算法会缩小范围在剩下的元素中重复这个“选择与交换”的过程直到整个序列完全有序。一、双向选择排序1.1 为什么要“双向”传统的选择排序每次遍历只找一个最小值效率较低。既然无论如何都要遍历一遍为什么不顺便把最大值也找出来呢于是便有了双向选择排序的思想左边放最小值右边放最大值向中间靠拢效率直接提升一倍。1.2 核心思想温水煮青蛙想象你在排队你站在队首begin你的同伴站在队尾end。在begin到end之间扫视一遍记住最高的人max_pos和最矮的人min_pos。把最矮的人换到begin。把最高的人换到end。begin往右走一步end往左走一步重复上述步骤。1.3 实现代码依据上述核心思想将它转化为可执行代码如下voidSelectSort(int*a,intn){// 定义当前待排序区间的左右边界intbegin0;intendn-1;// 当左右边界重合或越过时排序完成while(beginend){// 初始时假设当前区间的第一个元素既是最大值也是最小值intmin_posbegin;intmax_posbegin;// 遍历当前区间 [begin1, end]寻找真正的最大值和最小值的下标for(intibegin1;iend;i){// 如果发现更大的数更新最大值下标if(a[i]a[max_pos])max_posi;// 如果发现更小的数更新最小值下标if(a[i]a[min_pos])min_posi;}// --- 核心交换逻辑 ---// 1. 先将找到的最小值换到区间的起始位置beginSwap((a[min_pos]),a[begin]);// 2. 将找到的最大值换到区间的末尾位置endSwap((a[max_pos]),a[end]);// --- 收缩区间 ---// 已经排好了两个数左边界向右移右边界向左移begin;--end;}}本以为到这里这个排序就算结束了但是在某次使用时发现了一个小bug。1.4 详解致命的Buginta[]{9,1,2,5,7,4,6,3};SelectSort(a,sizeof(a)/sizeof(a[0]));依据调试结果可以明显看出代码有误于是一步一步去调试有了这么个发现假设数组是[9, 1, 2, 5, 7, 4, 2, 3]。此刻begin指向 9max_pos也是 0指向 9。我们先交换最小值把 1 和 9 交换。数组变成了[1, 9, 2, 5, 7, 4, 2, 3]。危机出现此时max_pos依然记录的是下标 0但下标 0 现在存的是 1如果你直接执行交换最大值的逻辑你会把 1 换到末尾也就是一开始调试出1在数组末尾的原因。解决方案如果最大值刚好在begin位置而begin刚才被换走了那么最大值现在一定在刚才min_pos所在的位置所以必须先把max_pos更新再进行更换。即在两次交换中间插入这个修正即可。/* * 2. 关键修正处理最大值位置被“误挪”的情况 * 如果原先的最大值下标 max_pos 恰好就是 begin * 那么在执行完上面的 Swap 后最大值已经被换到了 min_pos 的位置。 * 此时如果不修正 max_pos接下来的交换会把最小值重新换回后面。 */if(beginmax_pos){max_posmin_pos;}二、堆排序如果说选择排序是“肉眼观察”那么堆排序就是利用“严密的组织架构”。2.1 什么是堆堆在物理上是一个数组但在逻辑上是一棵完全二叉树。大根堆任一父节点都大于等于子节点用于升序排列。下标关系左孩子 parent * 2 1右孩子 parent * 2 2。2.2 核心武器向下调整建堆这是堆排序的灵魂。它的前提是左右子树已经是堆了只有根节点不老实。比较左右孩子找出最大的那个。如果孩子比父亲大交换并顺着孩子往下走继续比较。如果孩子比父亲小说明已经符合堆要求停止。选择向下调整建堆的核心原因在于其效率极高时间复杂度为O ( N ) O(N)O(N)它利用了完全二叉树“底层节点多、顶层节点少”的特性让节点数量最庞大的底层叶子节点完全不参与调整而让节点数量最少的顶层节点承担较多的调整层数这种“多对少”的策略在累加总调整次数时远优于向上调整的O ( N log ⁡ N ) O(N \log N)O(NlogN)。这部分参考我的建堆操作向上调整与向下调整的数学推导与性能对比博客。2.3 第一阶段建堆// 计算最后一个非叶子节点的下标最后一个元素下标是 n-1其父节点是 (n-1-1)/2intparent(n-2)/2;for(intiparent;i0;i--){// 从下往上依次将每棵子树调整为大堆AdjustDown(a,n,i);}为什么从( n − 1 ) / 2 (n-1)/2(n−1)/2开始因为叶子节点没有孩子不需要调整。我们要从最后一个“有孩子的家长”开始由下而上把每一棵子树都调成堆最终整棵树就成了大根堆。2.4 第二阶段排序逻辑建好大根堆后根节点a[0]一定是最大的。将a[0]与最后一个元素交换。缩减规模把最后一个元素排除在堆之外。对剩下的元素重新进行一次AdjustDown。intendn-1;// 始终指向当前待排序区间的最后一个位置while(end0){// 1. 将堆顶当前最大值交换到数组末尾Swap((a[0]),(a[end]));// 2. 重新调整将剩下的 end 个元素再次调成大堆AdjustDown(a,end,0);// 3. 缩小区间处理下一个最大值--end;}关键点为什么传end而不是end - 1Swap((a[0]),(a[end]));AdjustDown(a,end,0);// 这里 end 代表剩余待排序个数当end是 10 时Swap后我们还剩 10 个元素需要调整下标 0 到 9。AdjustDown的第二个参数是“个数”所以传入end正好覆盖了前面的所有元素。2.5 实现代码voidAdjustDown(int*a,intn,intparent){// 根据完全二叉树性质先定位到左孩子下标intchildparent*21;// 只要孩子下标还在有效个数内就继续向下比较while(childn){// 1. 在左、右孩子中挑选“最强”的一个// 确认有右孩子child 1 n且右孩子比左孩子大if(child1na[child1]a[child])child;// 此时 child 指向右孩子// 2. 将最强孩子与父节点比较if(a[parent]a[child]){// 如果孩子比父亲大不符合大堆定义执行交换Swap((a[parent]),(a[child]));// 3. 迭代父亲下沉到孩子的位置继续向下检查parentchild;childparent*21;}else// 如果父亲已经比最大的孩子还大说明此时该子树已符合堆性质跳出break;}}voidHeapSort(int*a,intn){// 计算最后一个非叶子节点的下标最后一个元素下标是 n-1其父节点是 (n-1-1)/2intparent(n-2)/2;for(intiparent;i0;i--)// 从下往上依次将每棵子树调整为大堆AdjustDown(a,n,i);intendn-1;// 始终指向当前待排序区间的最后一个位置while(end0){// 1. 将堆顶当前最大值交换到数组末尾Swap((a[0]),(a[end]));// 2. 重新调整将剩下的 end 个元素再次调成大堆AdjustDown(a,end,0);// 3. 缩小区间处理下一个最大值--end;}}三、算法对比与深度总结在掌握了双向选择排序的“修正细节”和堆排序的“架构思维”后我们需要跳出代码本身去思考更深层的问题为什么在现代软件工程中堆排序被广泛应用而选择排序往往只存在于教科书中3.1 复杂度与性能的“降维打击”虽然两者在逻辑上都属于“选择类”排序即每轮选出一个最值但它们获取最值的方式有着天壤之别。维度双向选择排序堆排序平均时间复杂度O ( N 2 ) O(N^2)O(N2)O ( N log ⁡ N ) O(N \log N)O(NlogN)最坏时间复杂度O ( N 2 ) O(N^2)O(N2)O ( N log ⁡ N ) O(N \log N)O(NlogN)空间复杂度O ( 1 ) O(1)O(1)O ( 1 ) O(1)O(1)深度解析选择排序的“笨”它像是一个没有记忆的人。每一轮为了找最值它必须盲目地遍历剩余的所有元素。即便前面已经比较过某些数字的关系它也无法利用这些信息。堆排序的“灵”堆结构本质上是一种有记忆的选择。在建堆之后元素间的父子关系已经帮我们过滤了大量的无效比较。每次“向下调整”只需O ( log ⁡ N ) O(\log N)O(logN)的代价这种对数级增长与O ( N ) O(N)O(N)的线性增长在数据量达到万级以上时效率差距会达到成百上千倍。3.2 写作感悟写代码就是“画地图”在完成这两个算法的实现后我最大的感悟是写好排序算法的关键不在于背诵代码而在于脑海中有一张动态的图。选择排序它的图是“两支箭”。begin和end是两支对向射击的箭它们不断收缩阵地直到在中间相遇。堆排序它的图是“搭架子与拆架子”。建堆是给凌乱的数据搭建起一套严密的官僚体系父管子子管孙排序则是拆除这个体系的过程每拆掉一个最高层就通过向下调整选拔出新的继任者。掌握了这两种思想你就不仅学会了如何给数字排序更学会了如何管理和组织数据。算法之美莫过于此。