建设网站方案ppt,网站建设项目方案ppt,网站建设的中期检查表,网页设计公司的调研#xfeff;从之前的学习可以看到#xff0c;对大型vectory要求的排序#xff0c;选择排序算法显然不符合要求#xff0c;因为运行时间与输入问题规模大小的平方成比例增加#xff0c;对于以线性顺序处理向量的元素的大多数排序算法也是如此。 所以要采用不同的方法来开发…从之前的学习可以看到对大型vectory要求的排序选择排序算法显然不符合要求因为运行时间与输入问题规模大小的平方成比例增加对于以线性顺序处理向量的元素的大多数排序算法也是如此。 所以要采用不同的方法来开发更好的排序算法。我们可以试着反过来思考。强大的分治法divide-and-conquer分治法的具体详见 C抽象编程——递归简介1——递归范式 我们先来看看排序算法的性能为什么在问题规模增大后变得如此糟糕我们之前分析过二次复杂度即ON^2类的基本特征是随着问题的大小增加运行时间增加了问题规模的两倍比如问题规模增加2倍那么运行时间要增加4倍。 然而反过来我们可以这样想。 如果将二次问题的大小除以2则可以将运行时间减少相同的四倍。 也就是说我们可以将vector除以一半然后应用递归的方法继续将问题的规模拆分就可以成倍的减少所需的排序时间。举个例子假设你有一个很大的vector需要排序。如果将vector分成两半然后使用选择排序算法对这些片段进行排序会发生什么 因为选择排序是的复杂度是二次的每个较小的vector需要原始时间的四分之一问题规模减少了2倍时间就提高4倍。 当然你需要对这两半分别进行排序但是排序两个较小vector所需的总时间仍然是排序原始vector所需的时间的一半。如果分开一个vector的两半可以简化整个vector排序的问题我们将能够大大减少排序需要的总时间。更重要的是一旦发现如何在一个地方提高性能就可以使用相同的算法递归地对每一个进行排序。 为了确定分治法是否适用于这个排序问题我们需要确定一个问题即将vector分为两个较小的vector然后对每个vector进行排序是否有助于解决一般问题也就是拿一个实例来分析一下。假设你从一个包含以下八个元素的vector开始排序 如果将8个元素的vector划分为长度为4的两个vector然后对每个较小的vector进行排序就会得到下图 现在我们需要从这些较小的vector中取出值并将它们以正确的顺序放回到原始vector中。合并两个vector从较小的排序vector重组成完整的vector比排序本身要简单得多。这个过程我们称为合并merging。即完整排序中的第一个元素必须是v1中的第一个元素或v2中的第一个元素以较小者为准。回到这个例子当中 1. 我们新组成的的vector中的第一个元素是第二个vectorv2中的第一个元素。然后将该元素添加到空的向量vec此时我们把v2的19叉掉表示已经取出我们下图的结果 2. 再来一次下一个元素只能是两个较小向量之一中的第一个未取出的元素。比较v1中的25与v2中的30并选择前者 3. 重复此过程从v1或v2中选择较小的值直到重构整个vector合并排序算法合并操作与递归分解相结合产生了一种称为合并排序的新的排序算法可以直接实现。 算法的基本思想可以概括如下 1. 检查vector是否为空或只有一个元素。如果是这样它肯定已经被排序。此条件用于定义递归的simple case。 2. 将vector分成两个较小的vector每个vector的大小是前者的一半意味着不是值分成两个vector而是每个分开的vector还可以继续分重复这个过程 3. 递归地对每个较小的vector进行排序。 4. 清除原始的vector使其再次为空。用来储存新的排序好的数字 5. 将两个排序好的vector合并回原来的vector。合并排序的C代码合并排序思路简单但是实现起来并不那么容易下面是本人写的C代码在VS2015中编译通过/*
运行效果如图 合并排序算法的代码可以整齐地分为两个函数排序和合并。 排序代码直接来自算法的步骤。在检查特殊情况后算法将原始vector分为两个较小的v1和v2。一旦sort代码将所有元素复制到v1或v2中v1V2就已经被创建其余的函数会递归地排序这些vector最后清除原始vector然后调用merge来重新组合vector从而实现合并排序。 实际上大部分的工作是通过合并函数完成的该函数采用目标vec以及较小的向量v1和v2。指标p1和p2标记跟踪每一个vector的下标。 在循环的每个循环中该函数从v1或v2选择一个元素取较小者并将该值添加到vec的末尾。一旦两个较小的vector中的任何一个的元素被取尽该函数可以简单地从另一个vector中直接复制元素而再比较它们。实际上因为这些向vector中的其中一个已经在第一个while循环退出时已经耗尽所以该函数可以将vector的其余部分复制到vec。 其中一个vector为空相应的while循环将完全不执行。这里说一下v1[p1]其实我们都知道 i返回的 i的值是自增1的。但是这个运算符返回的是自增前的值。也就是说比如 i 2执行i;之后就是 i 3但是 (i)这个整体的值就还是 2可以写个程序试试。 所以说v1[p1]这句代码等价于 v1[p1]; p1 ;下一篇的文章我们就去分析一下这个算法的复杂度
