外排序

排序之外部排序有时，待排序的⽂件很⼤，计算机内存不能容纳整个⽂件，这时候对⽂件就不能使⽤内部排序了（这⾥做⼀下说明，其实所有的排序都是在内存中做的，这⾥说的内部排序是指待排序的内容在内存中就可以完成，⽽外部排序是指待排序的内容不能在内存中⼀下⼦完成，它需要做内外存的内容交换），外部排序常采⽤的排序⽅法也是归并排序，这种归并⽅法由两个不同的阶段组成：1、采⽤适当的内部排序⽅法对输⼊⽂件的每个⽚段进⾏排序，将排好序的⽚段（成为归并段）写到外部存储器中（通常由⼀个可⽤的磁盘作为临时缓冲区），这样临时缓冲区中的每个归并段的内容是有序的。

2、利⽤归并算法，归并第⼀阶段⽣成的归并段，直到只剩下⼀个归并段为⽌。

例如要对外存中4500个记录进⾏归并，⽽内存⼤⼩只能容纳750个记录，在第⼀阶段，我们可以每次读取750个记录进⾏排序，这样可以分六次读取，进⾏排序，可以得到六个有序的归并段，如下图：每个归并段的⼤⼩是750个记录，记住，这些归并段已经全部写到临时缓冲区（由⼀个可⽤的磁盘充当）内了，这是第⼀步的排序结果。

完成第⼆步该怎么做呢？这时候归并算法就有⽤处了，算法描述如下：1、将内存空间划分为三份，每份⼤⼩250个记录，其中两个⽤作输⼊缓冲区，另外⼀个⽤作输出缓冲区。

⾸先对Segment_1和Segment_2进⾏归并，先从每个归并段中读取250个记录到输⼊缓冲区，对其归并，归并结果放到输出缓冲区，当输出缓冲区满后，将其写道临时缓冲区内，如果某个输⼊缓冲区空了，则从相应的归并段中再读取250个记录进⾏继续归并，反复以上步骤，直⾄Segment_1和Segment_2全都排好序，形成⼀个⼤⼩为1500的记录，然后对Segment_3和Segment_4、Segment_5和Segment_6进⾏同样的操作。

2、对归并好的⼤⼩为1500的记录进⾏如同步骤1⼀样的操作，进⾏继续排序，直⾄最后形成⼤⼩为4500的归并段，⾄此，排序结束。

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

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

当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-路插入排序。

外排序置换选择算法
外排序（External Sorting）是一种处理大量数据的排序算法，当数据量太大，无法一次性装入内存时，就需要使用外排序。

置换-选择排序（Replacement-Selection Sort）是外排序的一种算法。

置换-选择排序的基本思想是：
1. 从待排序的数据中提取一个长度为K的子序列（K为常数），然后利用任何有效的内部排序算法对这个子序列进行排序。

2. 将排序后的子序列与原始数据记录进行比较，找出并输出所有比排序后子序列大的记录。

3. 重复步骤1和2，直到所有记录都排好序为止。

置换-选择排序的时间复杂度为O(n^2)，其中n为待排序的数据量。

这是因为每次提取的子序列长度为常数K，所以需要比较的次数为O(n/K)，而提
取子序列和内部排序的时间复杂度均为O(n)。

因此，总的时间复杂度为
O(n^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. 内部排序对每个小块进行内部排序，常用的内部排序算法包括快速排序、归并排序、堆排序等。

选择合适的内部排序算法，将小块排序后存放在磁盘中。

3. 多路归并将排好序的小块进行多路归并。

多路归并即将多个有序的序列合并为一个有序序列。

在多路归并中，可以借助最小堆等数据结构，每次从多个序列中选择最小的元素，加入到有序序列中。

4. 写出结果将最终得到的有序序列写出到磁盘文件中。

三、多路归并排序算法的优化1. 外部排序的前提是磁盘I/O的次数尽可能少，因此可以采用合适的数据结构来减少读写次数，如B+树等。

2. 利用多线程或多进程进行归并操作可以加快排序速度。

可以将原始数据划分为多个小块，并利用多个线程或进程分别对这些小块进行排序和归并。

3. 预读数据是提高排序效率的一个关键。

可以采用预读技术，提前将数据加载到内存缓冲区中，减少磁盘I/O的次数。

4. 考虑数据的分布情况进行数据划分。

如果数据是有序的，可以将其均匀划分到不同的小块中，以充分利用有序性。

四、总结多路归并排序是一种有效解决大规模数据问题的外部排序算法。

通过将数据划分为多个小块，并采用多路归并的方式进行排序，可以充分利用磁盘空间和减少磁盘I/O次数。