败者树属于外部排序吗(最佳归并树和败者树),本文通过数据整理汇集了败者树属于外部排序吗(最佳归并树和败者树)相关信息，下面一起看看。

编程朱基的第一个案例，讲的是一个巧妙的解决外部排序问题的方法。巧妙的解决了问题，但是开头提到的合并排序外排序的算法还是值得仔细探索的。毕竟本科的时候学的不是很深。

我们先来看看内部排序中最简单的2路归并排序算法。

该算法的核心操作是将一维数组中相邻的两个有序序列合并成一个有序序列。给定数组中的序列边界I，m，n，用两个下标变量从I，j=m ^ 1开始逐个处理，先进行比较，将较小的写入结果序列的当前遍历下标k，然后继续比较对应的下标，直到一个序列的下标到达边界，再将另一个序列的剩余元素复制到结果序列中。

该算法可以通过递归或递归实现，从相邻的两两元素中不断调用上述核心运算，形成一个长有序序列，直到整个序列完成。

该算法可以在一次合并后得到一个完整的具有局部顺序的新序列。总共需要在log2n次中合并n个元素。每次完成n次比较操作(一次获得序列的一个值)，将获得的新序列写入结果序列空间。下一个之前要把结果序列复制到临时空间，下一个在临时空间合并。因此，时间复杂度nlog2n在空间上除了原始序列空间N和结果序列空间N之外，还需要一个辅助临时空间N。

接下来，看看外部排序。外排序是指大文件的排序，即将要排序的记录存储在外存储器中，要排序的文件无法一次性加载到存储器中，需要在内存储器和外存储器之间多次交换数据才能对整个文件进行排序。外部排序最常用的算法是多路归并排序，即把原始文件分解成几个可以一次性装入内存的部分，每个部分转入内存完成排序。然后，对排序后的子文件进行合并，并以多种方式进行排序。

多向归并排序算法在常见的数据结构书籍中都有涉及。从两条路径到多条路径(k条路径)，增加k可以减少外部存储信息的读写时间，但是在k个合并段中选择最小的记录需要k-1次，总共需要(u-1)(k-1)次才能得到一个u条记录的有序段。如果合并遍数为s次，则内部合并过程中的总比较次数为s (n即(上舍入)(logkm)(k-1)(n-1)=(上舍入)(log2m/log2k)(k-1)(n-1)，而(k-1)/log2k随着k的增加而增加，所以内部合并时间随着k的增加而增加，抵消了外部存储器读写时间的减少。在内部合并过程中，利用失败者树将k个合并段中选择最小记录的次数减少到(round up) (log2k)次，这样比较的总次数为(round up) (log2m)(n-1)，与k无关。

失败者树是完全二叉树，所以数据结构可以是一维数组。元素个数为K个叶子节点，k-1个比较节点和1个冠军节点，共2k个。Ls[0]是冠军节点，ls [1]-ls [k-1]是比较节点，ls [k]-ls [2k-1]是叶子节点(由另一个指针索引B [0]-B [k-1]指向)。另外，bk是一个额外的辅助空间，不属于失败者树，初始化时存储MINKEY的值。

多通道归并排序算法的过程大致如下：首先将k个归并段中的第一个元素关键字依次存储在B [0]-B [k-1]的叶节点空间中，然后调用CreateLoserTree创建失败者树。创建后，最小的关键字下标(即合并段的序列号)存储在ls[0]中。然后不断循环：获取ls[0]中存储的最小关键字来自的合并段的序号作为Q，将合并段的第一个元素输出到有序的合并段中，然后将下一个元素关键字放入前一个元素原来所属的叶节点b[q]中，调用Adjust沿叶节点b[q]向上调整loser树，直到新的最小关键字被选中，其下标也存在于ls[0]中。重复该过程，直到所有元素都被写入有序合并段。

伪代码如下：

Void Adjust(LoserTree ls，int s)/*将失败者树从叶节点b[s]调整到根节点的父节点ls[0]*/{ int t，tempt=(s K)/2；/*t是失败者树中b[s]的父节点下标，k是合并段数*/while(t 0) /*如果没有到达根，继续*/{ if(b[s] b[ls[t]]) /*与父节点指示的数据进行比较*/{* ls [t]。s=ls[t]；ls[t]=temp；} t=t/2；/*返回一层到树的根，找到父节点*/} ls[0]=s；/*ls[0]记录该行最小关键字所在的段号*/}

void k _ merge(int ls[k])/* ls[0]~ ls[k-1]是失败者树的内部比较节点。B[0]~b[k-1]分别存储K个初始合并段的当前记录*/* Get _ next(I)函数用于从第I个合并段读取并返回当前记录*/{ int b[K 1]，I，q；for(I=0；I I){ b[I]=Get _ next(I)；/*分别读取K个合并段的第一个关键字*/} b[K]=MINKEY；/*创建一个失败者树*/for(I=0；I)/*在ls */ls[i]=K中设置失败者的初始值；for(I=K-1；I-)/*从b[K-1]……b[0]依次调整失败者*/Adjust(ls，I)；/*失败者树创建后，最小关键字序号存储在ls[0] while(b[ls[0]]！=MAXKEY){ q=ls[0]；/*q是当前最小值关键字所在的合并段*/prinftf('%d '，b[q])；b[q]=Get _ next(q)；Adjust(ls，q)；/*q要调整失败者树，选择一个新的最小值关键字*/}}

最后，粗略描述了多路归并排序的外部排序过程：根据有限的内存资源，将一个大文件分成L个段，然后将这L个段依次读入内存，利用高效的内部排序算法对每个段进行排序。排序后的结果是初始有序合并段，直接写入外部存储文件。在进行内部排序时，要选择合适的排序算法，并考虑内部排序所需的辅助空间和有限的内存空间来决定是否将一个大文件分成若干段。接下来，选择适当的路号K，以多种方式对这L个合并的段进行排序。每次合并将K个合并段变成一个更大的合并段，并将其写入一个文件。经过反复合并，得到整个有序文件。在多通道合并过程中，内存空间只需要维护一棵大小为2k的loser树，数据检索和释放都是从外部存储器读写。这样一来，把一大块数据读入内存，把内存中排列的一大块数据一次写入一个文件，就比较省时了。不知道这个需要程序员编程安排还是OS可以通过虚拟页面文件直接帮忙做。回头看看那些找出计算机组成原理的教材，发现我以为用虚拟页面文件管理来解决这个问题是完全不相干的。分段虚拟存储是以分段的方式管理程序的逻辑空间，而要排序的文件不属于程序本身的逻辑空间。其实这个问题要从磁盘本身提供的缓存来考虑。目前磁盘一般都有几米到十几米的缓存。通过使用数据访问的空间局部性和时间局部性规则，使用预读策略将一块数据一次性读入缓存。再次读写时，需要检查缓存是否能命中。如果能命中，就没必要在盘上读了。如果缓存空间不足以提高读写速度，程序员需要编写程序来读写大块数据。

这个网站是个人知识管理的网络存储空间。所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请一键举报。

更多败者树属于外部排序吗(最佳归并树和败者树)相关信息请关注本站，本文仅仅做为展示！