外排序

排序之外部排序有时，待排序的⽂件很⼤，计算机内存不能容纳整个⽂件，这时候对⽂件就不能使⽤内部排序了（这⾥做⼀下说明，其实所有的排序都是在内存中做的，这⾥说的内部排序是指待排序的内容在内存中就可以完成，⽽外部排序是指待排序的内容不能在内存中⼀下⼦完成，它需要做内外存的内容交换），外部排序常采⽤的排序⽅法也是归并排序，这种归并⽅法由两个不同的阶段组成：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次数。

第11章外排序1、什么是外排序外排序是指数据存放在外存中，数据排序时涉及内、外存数据交换的排序方法。

内存数据交换文件存储在外存上的数据以文件为基本单位。

（1）生成若干初始归并段（顺串）：这一过程也称为文件预处理。

一种常规的方法如下：❶把含有n 个记录的文件，按内存大小w 分成若干长度为w 的子文件（归并段）；❷分别将各子文件（归并段）调入内存，采用有效的内排序方法排序后送回外存。

产生⎡n /w ⎤个初始归并段。

外排序的基本方法是归并排序法。

它分为以下两个步骤：2、外排序的基本方法内存abc.databc 1.dat abc 2.dat …abc n .dat均有序某内排序算法（2）多路归并：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。

内存abc 1.dat abc 2.dat …abc n .databc.dat有序采用归并算法示例文件abc.dat：5，6，3，4，9，8，1，7，10，2递增排序应用程序可用的内存空间大小w=2。

5，6，3，4，9，8，1，7，10，2外排序过程：w =2内存abc.dat（1）生成5个初始归并段①abc1.dat ：5，6②abc2.dat ：3，4③abc3.dat ：8，9④abc4.dat ：1，7⑤abc5.dat ：2，10外排序过程：k =2内存abc1.dat abc2.databc12.dat ：3，4，5，6（2）多路归并：w =2 2路归并（k =2）abc1.dat ：5，6abc2.dat ：3，4abc1.dat ：abc2.dat ：5634比较abc12.dat ：内存∞ ∞u （u =4）个记录需要进行u -1次操作（不考虑∞ ）k （k =2）路归并每次需要k -1次关键字比较大致分析总的关键字比较次数：(u -1)(k -1)段1记录段2记录结果段内存abc3.databc4.dat abc34.dat：1，7，8，9abc3.dat：8，9abc4.dat：1，7w =2内存abc12.databc34.dat abc1234.dat：1，3，4，5，6，7，8，9abc12.dat：3，4，5，6abc34.dat：1，7，8，9k =2内存abc1234.databc5.dat abc.dat：1，2，3，4，5，6，7，8，9，10abc1234.dat：1，3，4，5，6，7，8，9abc5.dat：2，10k =2归并过程对应的归并树5，6abc1.dat 3，4abc2.dat 3，4，5，6abc12.dat 8，9abc3.dat 1，7abc4.dat 1，7，8，9abc34.dat 1，3，4，5，6，7，8，9abc1234.dat 1，2，3，4，5，6，7，8，9，10abc.dat2，10abc5.dat 归并过程的性能：记录读写次数。

排序算法所用的辅助空间一、引言在计算机科学中，排序算法是数据处理的基本技术之一。

排序算法可以分为内部排序和外部排序两大类。

内部排序是指待排序数据全部加载到内存中进行排序，而外部排序则是针对大规模数据，需要借助外部存储设备进行排序。

本文将重点讨论排序算法中所使用的辅助空间。

二、排序算法概述1.内部排序内部排序算法是指待排序数据可以完全加载到内存中进行排序的算法，如快速排序、归并排序、堆排序等。

这些算法的特点是时间复杂度较低，但在处理大规模数据时，空间复杂度成为瓶颈。

2.外部排序外部排序算法针对的是大规模数据，其特点是数据规模超过内存容量。

外部排序需要借助外部存储设备，如磁盘等，进行排序。

常见的外部排序算法有归并排序、快速排序等。

三、辅助空间的作用1.空间复杂度辅助空间是指在排序过程中，除待排序数据外，还需要使用的额外空间。

辅助空间的大小直接影响到排序算法的性能。

一般来说，我们希望辅助空间尽量小，以提高排序效率。

2.实例分析以归并排序为例，归并排序需要使用额外的空间存储中间结果。

当待排序数据规模较大时，辅助空间的需求也随之增加。

此时，可以考虑使用外部排序算法，将数据分块，依次加载到内存中进行排序，最后合并排序结果。

四、常见排序算法的辅助空间使用1.快速排序快速排序算法采用递归策略，其辅助空间主要用于存储子序列。

在递归过程中，快速排序会创建一个新的序列，将原序列分为两个子序列。

这个过程会递归进行，直到序列长度为1。

快速排序的辅助空间与递归深度成正比。

2.归并排序归并排序算法的辅助空间主要用于存储临时数据。

在归并过程中，需要将两个已排序的序列合并成一个有序序列。

这个过程需要额外的空间存储临时数据，以便进行合并操作。

归并排序的辅助空间与序列数量成正比。

3.堆排序堆排序算法在排序过程中，需要构建最大堆或最小堆。

堆排序的辅助空间主要用于存储堆结构的数据。

堆排序的辅助空间与堆的大小成正比。

4.计数排序计数排序是一种非比较排序算法，其原理是根据键值统计每个键值出现的次数，然后将计数结果存储在辅助空间中。

使用sort命令对大型数据文件进行外部排序在处理大型数据文件时，外部排序是一种常用的技术。

它允许我们将数据文件分割为可以适应内存大小的块，并在磁盘上进行排序操作。

在Linux系统中，sort命令是一个强大的工具，可以用于对大型数据文件进行外部排序。

sort命令的基本用法是：sort [选项] 文件名选项：-r：以降序排序（默认为升序）-n：按照数字的大小进行排序-k n：以第n列作为排序依据-t 分隔符：指定分隔符，默认是制表符以下是对sort命令进行更详细说明的一些示例：1. 对文本文件进行排序假设有一个名为"data.txt"的文本文件，其中包含了一系列整数，每行一个。

我们可以使用sort命令对其进行排序：sort data.txt该命令将按照默认的升序方式对文件进行排序，并将结果打印到控制台。

2. 对文本文件进行降序排序如果我们希望按降序进行排序，可以使用选项"-r"：sort -r data.txt这将按照降序对文件进行排序，并将结果打印到控制台。

3. 对包含其他分隔符的文本文件进行排序如果数据文件的列之间是由其他分隔符（如逗号或空格）分隔的，我们可以使用选项"-t"指定分隔符：sort -t, -k 2 data.txt这将按照第二列的值进行排序，并将结果按默认方式（升序）打印出来。

在这个例子中，我们假设数据文件的列之间是用逗号分隔的。

4. 对数字文件进行排序假设数据文件的内容是一系列的数字，而不是文本。

我们可以使用选项"-n"以数字的形式进行排序：sort -n data.txt这将按照数字的大小进行排序，并将结果打印到控制台。

5. 对大型数据文件进行外部排序当我们需要对大型数据文件进行排序时，我们可以使用sort命令的管道功能，将排序结果写入到另一个文件中：sort -n data.txt | sort -T ./tmp -k 1 -m -o sorted_data.txt这个命令将按照数字的大小对文件进行排序，并将结果保存在名为"sorted_data.txt"的文件中。

第11章外排序教材中练习题及参考答案1. 外排序中两个相对独立的阶段是什么？答：外排序中两个相对独立的阶段是产生初始归并段和多路归并排序。

2.给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18），设内存工作区可容纳4个记录，给出用置换-选择排序算法得到的全部初始归并段。

答：置换-选择排序算法的执行过程如表11.1所示。

共产生两个初始归并段，归并段1为（2，8，12，16，28，30），归并段2为（4，6，10，18，20）。

表11.1 初始归并段的生成过程3. 设输入的关键字满足k1>k2>…>k n，缓冲区大小为m，用置换-选择排序方法可产生多少个初始归并段？答：可产生⎡n/m⎤个初始归并段。

设记录R i的关键字为k i（1≤i≤n），先读入m个记录R1、R2、…、R m，采用败者树选择最小记录R m，将其输出到到归并段1，R min=k m，在该位置上读入R m+1，采用败者树选择最小记录R m-1，将其输出到到归并段1，R min=k m-1，在该位置上读入R m+2，采用败者树选择最小记录R m－2，将其输出到到归并段1，R min=k m-2，…，以此类推，产生归并段1：（R m，R m-1，…，R1）。

同样产生其他归并段（R2m，R2m-1，…，R m+1），（R3m，R3m-1，…，R2m+1），…，一共有⎡n/m⎤个初始归并段。

4. 什么是多路平衡归并，多路平衡归并的目的是什么？答：归并过程可以用一棵归并树来表示。

多路平衡归并对应的归并树中，每个结点都是平衡的，即每个结点的所有子树的高度相差不超过1。

k路平衡归并的过程是：第一趟归并将m个初始归并段归并为⎡m/k⎤个归并段，以后每一趟归并将l个初始归并段归并为⎡l/k⎤个归并段，直到最后形成一个大的归并段为止。

m个归并段采用k路平衡归并，总的归并趟数s=⎡log k m⎤。

其趟数是所有归并方案中最少的，所以多路平衡归并的目的是减少归并趟数。

内部和外部排序排序
内排序：指在排序期间数据对象所有存放在内存的排序。

外排序：指在排序期间所有对象太多，不能同⼀时候存放在内存中，必须依据排序过程的要求，不断在内，外存间移动的排序。

依据排序元素所在位置的不同,排序分: 内排序和外排序。

内排序：在排序过程中，全部元素调到内存中进⾏的排序，称为内排序。

内排序是排序的基础。

内排序效率⽤⽐較次数来衡量。

按所⽤策略不同，内排序⼜可分为插⼊排序、选择排序、交换排序、归并排序及基数排序等⼏⼤类。

外排序：在数据量⼤的情况下。

仅仅能分块排序。

但块与块国⽶不能确保有序。

与读取外部排序/写的外部存储器中的数以测量其效率。

版权声明：本⽂博客原创⽂章。

博客，未经同意，不得转载。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其次是内存的使用。

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

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

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

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

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