外排序之文件归并排序实现

目录

1. 外排序介绍

2. 文件归并排序思路分析

3. 代码

---

1. 外排序介绍

外排序(External sorting)是指能够处理极大量数据的排序算法。通常来说,外排序处理的数据不能依次装入内存,只能放在读写较慢的外存储器上(通常是硬盘)。外排序通常采用的是一种"排序 - 归并"的策略。在排序阶段,先读入能放在内存中的数据量,将其排序输出到一个临时文件,依次进行,将待排序数据组织为多个有序的临时文件。然后再归并阶段将这些临时文件组合为一个大的有序文件,也就是排序结果。

跟外排序对应的就是内排序,我们之前的常见的排序都是内排序,他们排序思想适应的是数据在内存中,支持随机访问。归并排序的思想不需要随机访问数据,只需要依次按序列读取数据,所以归并排序既是一个内排序,又是一个外排序。

2. 文件归并排序思路分析

1.  读取n个值排序后写道file1,再读取n个值排序后写道file2。

2. file1和file2利用归并排序的思想,依次读取比较,取小的尾插到mfile,mfile归并为一个有序文件。

3. 将file1和file2删除,mfile重命名为file1。

4. 再次读取n个数据排序后写道file2。

5. 继续file1和file2归并,重复步骤2,直到文件中无法读出数据。最后归并出的有序数据放到了file1中。

3. 代码

Elementary data structure: Data structure code and blackboard writing - Gitee.comhttps://gitee.com/Axurea/elementary-data-structure/tree/master/2024_9_8_Project