c - 如何在不使用数组存储原始文件内容的情况下对文件中的一百万个整数进行排序并保存在另一个文件中？

Question

我正在编写一个程序，它创建一个包含 100 万个随机输入的文件，对它们进行排序，然后将排序后的列表写入一个新文件。

有没有一种有效的方法可以对元素进行排序，而不必将整个输入文件复制到数组中->排序->写回输出文件？

Answer 1

我建议阅读关于 Programming Pearls，第 2 版的第 1 列。作者 Jon Bentley 使用位向量准确地解决了这个问题，仅使用 1MB 内存对大约 1000 万个整数进行排序。但这仅在输入中的整数绑定到已知范围时才有效。

Answer 2

“简单”的解决方案是遍历列表，找到“尚未存储在输出文件中的最低 [1] 数字”，直到您再也找不到低数字。但是，这将非常缓慢，因为这可能意味着对整个未排序文件进行 1M 次读取。但是不会占用太多内存...

不幸的是，任何其他方法都将涉及将文件（或某些部分）读入内存。当有足够的内存可以读入内存时，磁盘排序是一种非常垃圾的方法——如果你说在一台 16GB 的机器上对 40GB 的数字列表进行排序，那么你当然别无选择。但是如果有足够的内存，将其全部读入内存并再次写回始终是最佳选择。

[1] 或最高，如果您想按“从高到低”排序。

Answer 3

好吧，您可以使用二叉搜索树并将它们写回输出文件，您可以使用此算法：

void output_to_file(FILE* file , struct* binTree)
{
     if(binTree != NULL)
     {
         output_to_file(binTree->left);
         fprintf(file , "%d/n" , binTree->num); //num is the member of the structure that carrys the number
     output_to_file(binTree->right);
     }
}