10_外部排序

外部排序技术之多路归并外部排序技术之多路归并重点：败者树的创建调整函数1.外部排序概述外部排序指的是⼤⽂件的排序，即待排序的记录存储在外存储器上，待排序的⽂件⽆法⼀次装⼊内存，需要在内存和外部存储器之间进⾏多次数据交换，以达到排序整个⽂件的⽬的。

外部排序最常⽤的算法是多路归并排序，即将原⽂件分解成多个能够⼀次性装⼈内存的部分，分别把每⼀部分调⼊内存完成排序。

然后，对已经排序的⼦⽂件进⾏归并排序。

2. 多路归并的实现2.1 胜者树胜者进⼊下⼀轮，直⾄决出本次⽐赛的冠军。

决出冠军之后，充分利⽤上⼀次⽐赛的结果，使得更快地挑出亚军、第三名 …… 。

⽰例：我们这⾥以四路归并为例，假设每个归并段已经在输⼊缓冲区如下图。

每路的第⼀个元素为胜利树的叶⼦节点，（5,7）⽐较出5胜出成为其根节点，（29,9）⽐较9胜出成为其根节点，⼀次向上⽣成⼀棵胜利树，然后我们可以得出5为冠军，将第⼀路归并段的元素5放⼊输出缓冲区，然后将第⼀路第⼆个元素放到胜利树中如下：由第⼀次得到的胜利树知，我们这⾥只改变了第1路的叶⼦节点，所有根节点7的右⼦树不⽤再⽐较，（16,7）⽐较7胜出，然后7和右⼦树的胜利者⽐较7胜出得到亚军，只进⾏了2次⽐较。

所以我们知道：决出第⼀名需⽐较： k - 1 次决出第⼆名需⽐较：次决出第三名需⽐较：次 .............2.2 败者树与胜利树相类似，败者树是在双亲节点中记录下刚刚进⾏完的这场⽐赛的败者，让胜者去参加更⾼⼀层的⽐赛。

⽰例：我们这⾥以四路归并为例，假设每个归并段已经在输⼊缓冲区如下图。

每路的第⼀个元素为胜利树的叶⼦节点，（5,7）⽐较出5胜出7失败成为其根节点，（29,9）⽐较9胜出29失败成为其根节点，胜者（5,9）进⾏下次的⽐赛7失败成为其根节点5胜出输出到输出缓冲区。

由第⼀路归并段输出，所有将第⼀路归并段的第⼆个元素加到叶⼦节点如下图：加⼊叶⼦节点16进⾏第⼆次的⽐较，跟胜利树⼀样，由于右⼦树叶⼦节点没有发⽣变化其右⼦树不⽤再继续⽐较。

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

我们这里说说八大排序就是内部排序。

当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。

即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：1.void print(int a[], int n ,int i){2. cout<<i <<":";3.for(int j= 0; j<8; j++){4. cout<<a[j] <<" ";5. }6. cout<<endl;7.}8.9.10.void InsertSort(int a[], int n)11.{12.for(int i= 1; i<n; i++){13.if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。

小于的话，移动有序表后插入14.int j= i-1;15.int x = a[i]; //复制为哨兵，即存储待排序元素16. a[i] = a[i-1]; //先后移一个元素17.while(x < a[j]){ //查找在有序表的插入位置18. a[j+1] = a[j];19. j--; //元素后移20. }21. a[j+1] = x; //插入到正确位置22. }23. print(a,n,i); //打印每趟排序的结果24. }25.26.}27.28.int main(){29.int a[8] = {3,1,5,7,2,4,9,6};30. InsertSort(a,8);31. print(a,8,8);32.}效率：时间复杂度：O（n^2）.其他的插入排序有二分插入排序，2-路插入排序。

外部排序分析当对数据记录量巨⼤的数据⽂件进⾏排序时，由于受到内存容量的限制，⽆法将所有数据记录⼀次全部读⼊到内存进⾏。

排序过程中需要多次进⾏内、外存之间的数据交换。

利⽤外存对数据⽂件进⾏排序称为外部排序。

外部排序最基本的⽅法是归并。

这种⽅法是由两个相对独⽴的阶段组成：①按内存(缓冲区)的⼤⼩，将n个记录的数据⽂件分成若⼲个长度为l的段或⼦⽂件，依次读⼊内存并选择有效的内部排序⽅法进⾏排序；然后将排好序的有序⼦⽂件重新写⼊到外存。

⼦⽂件称为归并段或顺串。

②采⽤归并的办法对归并段进⾏逐趟归并，使归并段的长度逐渐增⼤，直到最后合并成只有⼀个归并段的⽂件—排好序的⽂件。

1 外部排序的简单⽅法归并排序有多种⽅法，最简单的就是2-路归并。

设有⼀个磁盘上的数据⽂件，共有100,000个记录(A1， A2，…，A100000)，页块长为200个记录，供排序使⽤的缓冲区可提供容纳1000个记录的空间，现要对该⽂件进⾏排序，排序过程可按如下步骤进⾏：第⼀步：每次将5个页块(1000个记录)由外存读到内存，进⾏内排序，整个⽂件共得到10个初始顺串R1~R10 (每⼀个顺串占5个页块)，然后把它们写回到磁盘上去。

第⼆步：然后两两归并，直到成为⼀个有序⽂件为⽌。

由图可知，每趟归并由m个归并段得到┌m/2┐个归并段。

2 外排序的时间分析外排序的时间消耗⽐内排序⼤得多，原因是：●外排序的数据量(记录)⼀般很⼤；●外排序涉及到内、外存之间的数据交换操作；●外存的操作速度远远⽐内存中的操作慢。

外排序的总时间由三部分组成：外排序的时间=产⽣初始归并段的时间(内排序)m×tis+I/O操作的时间d×tio+内部归并的时间s×utmg其中：m：初始归并段数⽬；tis：得到⼀个归并段的内排序时间；d：总的读、写次数；tio：⼀次读、写的时间；s：归并的趟数；utmg：对u个记录进⾏⼀趟内部归并排序的时间。

⼀般地，tio>>tis，tio>>tmg，tio⽽取决于所⽤外存,因此，影响外排序效率的主要原因是内、外存之间数据交换(读、写外存)。

【数据结构】排序——外部排序【数据结构】排序——外部排序外部排序是指⼤⽂件的排序，即排序的记录存储在外存储器上，在排序过程中需进⾏多次的内、外存之间的交换。

外部排序⽅法通常采⽤归并排序有外部排序基本上由两个相对独⽴的阶段组成。

按可⽤内存⼤⼩，将外存上含有n个记录的⽂件分成若⼲长度为l的字⽂件或段。

依次读⼊内存并利⽤有效的内部排序⽅法排序，将排序后得到的有序⼦⽂件（称为归并段或顺串），进⾏逐趟归并，直⾄得到整个有序⽂件为⽌。

在外部排序中实现两两归并，由于不可能将两个有序段及归并结果段同时存放在内存中的缘故，所以不仅要调⽤归并过程，还需要进⾏外存的读_写（对外存上信息的读_写是以“物理块”为单位的）。

耗费时间总时间=内部排序时间(产⽣初始归并段)+外存读写时间+内部归并时间内部排序时间=经过内部排序后得到的初始归并段的个数r * 得到⼀个初始归并段进⾏内部排序多需时间的均值外存读写时间=总的读写次数 * 进⾏⼀次外存读写时间的均值内部归并时间=归并的趟数s * n个记录进⾏内部归并排序的时间优化⽅法增⼤归并路数k减少初始归并段个数r以上两个⽅法都可以减少归并的趟数，进⽽减少读写磁盘的次数，提⾼外部排序速度多路平衡归并与败者树已知增加k可以减少s，从⽽减少总的读写次数。

如果只单纯的增加k⼜会导致内部归并时间增加。

为了使内部归并不受k的增⼤⽽影响，提出了败者树。

败者树的基本思想败者树是树形选择排序的⼀种变型，可视为⼀棵完全⼆叉树。

k个叶⼦节点分别存放k个归并段在归并过程中当前参加⽐较的记录，内部节点⽤来记忆左右⼦树中的“失败者”，⽽让胜者往上继续进⾏⽐较，⼀直到根结点。

若⽐较两个数，⼤的为败者、⼩的为胜利者，则根结点指向的数为最⼩数。

eg、设初始归并段为(10,15,31),(9,20),(6,15,42),(12,37),(84,95),利⽤败者树进⾏m路归并，⼿⼯执⾏选择最⼩的5个关键字的过程。

性能分析k-路归并的败者树的深度为[log2k]+1注意⚠ 在多路平衡归并中采⽤简单⽐较时，k越⼤，关键字的⽐较次数会越⼤。

第一部分：数据结构六、排序1、增加了：（十）外部排序2、后面的修改：（十一）各种内部排序算法的比较；（十二）内部排序算法的应用【外部排序不是数据结构的重点，考生无需在这个知识点上花过多的时间，只需要做概念的理解和记忆就行，这个知识点笔者预测会单独以选择题的形式下面，或者结合其他内部排序算法以选择题形式一起考查。

】6.7.1一、问题的提出1．待排序的记录数量很大，不能一次装入内存，则无法利用前几节讨的排序方法。

2．定义：外排序就是把待排序记录先存储在外存上，再分别部分地调入内存排序，在排序过程中多次进行内、外存的数据交换的排序过程。

二、外部排序特点1．文件大，内存放不下2．需要在内外存之间进行多次交换（1）文件在外存中的组织两种基本外存设备：磁带和磁盘；・磁带：典型的顺序设备；・磁盘：典型的随机设备。

（2）文件在内存中的排序・逻辑上信息按字符组（记录）存放；・物理上读写（I/O操作）按块顺序或随机进行；・逻辑记录和物理块之间的对应关系；（3）文件在内外存之间的交换读取一个记录（字符组）检查内存缓冲区有无此记录：若有，则可读；若无，则启动I/O从外存读相应的物理块到缓冲区，再从缓冲区内读取相应的记录。

写回一个记录：在缓冲区拼装成为一个物理块；启动I/O写回到外存。

三、外部排序的基本过程由相对独立的两个步骤组成：１．按可用内存大小，利用内部排序的方法，构造若干(记录的)有序子序列，通常称外存中这些记录有序子序列为“归并段”；２．通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。

例如：假设有一个含10000个记录的磁盘文件，而当前所用的计算机一次只能对1000个记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并。

假设进行2路归并(即两两归并)，则第一趟由10个归并段得到5个归并段；第二趟由5个归并段得到3个归并段；第三趟由 3 个归并段得到2个归并段；最后一趟归并得到整个记录的有序序列。

外部排序---数据结构外部排序数据结构在计算机科学中，数据的排序是一项非常基础且重要的操作。

当数据量过大，无法一次性全部放入内存进行排序时，就需要用到外部排序这种技术。

想象一下，你有一个巨大的数据集，大到内存根本装不下。

这时候，内部排序算法，比如快速排序、冒泡排序等等，就显得无能为力了。

外部排序就像是一位超级英雄，专门来解决这种内存装不下的大问题。

外部排序的基本思路其实并不复杂，但实现起来却需要一些巧妙的策略。

它通常会将数据分成多个较小的部分，先在内存中对这些小部分进行排序，然后将排序好的小部分逐次合并，最终得到完全有序的数据。

为了更好地理解外部排序，让我们先来看看它的工作流程。

假设我们有一个非常大的文件需要排序，由于内存限制，我们不能一次性把整个文件读入内存。

所以，第一步就是将这个大文件分割成若干个大小适中的子文件，这些子文件能够被轻松地读入内存。

然后，我们在内存中使用一种内部排序算法，比如快速排序，对每个子文件进行单独排序。

接下来就是关键的合并步骤。

我们会从已经排序好的子文件中依次读取数据，然后将它们合并到一个新的文件中。

这个合并的过程就像是把几堆已经排好序的扑克牌重新整理成一整堆有序的扑克牌。

在合并的过程中，我们需要不断地比较来自不同子文件的数据，将较小的数据先放入新文件中。

那么，在这个过程中，有哪些关键的技术和要点呢？首先是数据的分割策略。

我们要确保分割出来的子文件大小合适，既能在内存中高效处理，又不会导致分割次数过多而增加额外的开销。

如果子文件分得太小，那么合并的次数就会增多，效率就会降低；如果分得太大，又无法在内存中进行排序。

其次是内存的使用。

在外部排序中，内存的使用需要非常精细地管理。

我们不仅要为读取和写入数据留出空间，还要为中间的比较和合并操作保留足够的缓冲区。

如果内存使用不当，可能会导致频繁的磁盘读写，大大降低排序的速度。

还有就是合并算法的选择。

常见的合并算法有二路归并和多路归并。