使用QSORT对大型、二进制、固定长度的记录进行排序

Question

我想在qsort的帮助下对一个包含20字节（不是结构）二进制记录的大文件进行排序。文件中有80万条记录。

我有两个问题：

• 在qsort的比较函数中，对20字节记录进行排序的最佳方法是什么？

  int compare(const void *a, const void *b)
  

• 简单地说，如何对80万条记录进行排序？我不能把这一切都记在记忆里。。

Answer 1

正如许多评论者所提到的，这对于外部排序算法来说是一项很好的工作，这种排序算法是为无法同时将所有对象放入内存进行排序而设计的。许多排序算法可以适用于此设置，例如快速排序、桶排序和合并排序。如果你想要一个相对简单的选项，可以考虑使用k路外部合并：将数据拆分为多个范围，使每个范围都适合内存，对内存中的每个范围进行排序，然后将结果写回磁盘。然后，对这些范围进行k路合并：打开每个文件进行读取，一次读取每个文件的一大块，并对这些块使用普通的k路合并操作。任何时候，只要用尽一个块中的所有元素，就可以从文件中读取另一个块。