0

我正在尝试使用合并排序来实现（在 C 中）用于大学作业的数据库的外部排序算法。可用内存是buffSize块。我发现这个链接很有帮助：

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

但我的问题是关于这行伪代码，在算法的第一阶段：

sort array a using an in-memory algorithm like quicksort

如果我无权使用我的buffSize空间以外的任何内存，所以我无法分配a链接的数组，我如何对包含在这些块中的记录进行排序（然后将它们存储在临时运行文件中） ，使用内存中的排序过程（例如快速排序）。在那种情况下，我的记录不会位于连续数组中，而是位于非连续内存块中，我无法直接应用 qsort。有什么提示吗？

4

1 回答 1

2

外部排序的一般方法是：

  1. 读取尽可能多的数据以适合阵列内存。
  2. 解决。
  3. 将其写入临时文件（跟踪名称和大小以及最大记录等）。
  4. 返回第 1 步，直到到达数据的末尾。
  5. 为写入的文件设置合并树，以便进行最少的合并。
  6. 从每个第一个（仅？）合并阶段输入文件中读取一行。
  7. 将最小的（用于升序排序）写入下一个临时文件（或最终文件）。
  8. 获取一条新记录来替换刚刚写入的记录。
  9. 返回第 7 步，直到没有更多数据要读取。
  10. 返回第 6 步继续合并，直到完成。

您没有详细说明内存块的含义，但是有一个可以在内存中排序buffSize的数组。a因此，您将数据读入数组。您使用快速排序对数组进行排序。然后将阵列写入磁盘。重复读取、排序、写入，直到没有更多输入数据。然后进行合并...

于 2012-10-13T02:22:24.967 回答