使用Ruby作为脚本语言，使用具有4gb RAM的计算机对30gb字符串进行排序的最佳方法是什么？
嗨，我看到这是一个面试问题，并认为这是一个有趣的问题，我不确定答案。
什么是最好的方式？
假设* nix：
system("sort output_file") “sort”可以使用临时文件来处理大于内存的输入文件。 如果需要，它具有调整主内存量和将使用的临时文件数量的开关。
如果不是* nix，或者面试官因为横向答案而皱眉，那么我将编码外部合并排序 。 有关外部排序算法的详细摘要，请参阅@ psyho的答案。
一种方法是使用外部排序算法 ：
- 将一大块文件读入内存
- 使用任何常规排序算法（如quicksort）对该块进行排序
- 将排序后的字符串输出到临时文件中
- 重复步骤1-3，直到处理整个文件
- 通过逐行读取临时文件来应用合并排序算法
- 利润！
将它们放在数据库中，让数据库担心它。
嗯，这是一个有趣的采访问题……几乎所有这类问题都是为了测试你的技能而不是，幸运的是，它们直接适用于现实生活中的例子。 这看起来像一个，所以让我们进入这个难题
当你的面试官要求“最好”时，我相信他/她只谈论表现。
答案1
30GB的字符串是很多数据。 所有比较交换算法都是Omega(n logn) ，因此需要很长时间。 虽然有O(n)算法，例如计数排序，它们不到位，所以你将乘以30GB并且你只有4GB的RAM（考虑交换量……），所以我会选择quicksort
答案2（部分）
开始考虑计算排序。 您可能希望首先将字符串分组（使用基数排序方法），每个字母一个。 您可能希望扫描文件，并且对于每个首字母， 将字符串（因此复制和删除，没有空间浪费）移动到临时文件中。 您可能希望重复每个字符串的前2,3或4个字符的过程。 然后，为了减少分类大量文件的复杂性，您可以单独对每个文件中的字符串进行排序（现在使用quicksort），最后按顺序合并所有文件。 这样你仍然会有一个O(n logn)但是在公平的O(n logn) n
数据库系统已经很好地处理了这个特定问题。
一个好的答案是使用合并排序算法，根据合并步骤的需要使其适应磁盘数据和磁盘数据。 这可以通过对内存的最低要求来完成。