一个适用于大部分已排序数据且数据无法全部载入内存的好的排序算法是什么？

Question

如果给你以下条件：

• 一定数量的数据
• 内存大小为数据大小的一半
• 部分数据已排序
• 你不知道已排序数据的大小。

你会选择哪种排序算法呢？我在插入排序和快速排序之间犹豫。我知道插入排序的最佳情况是O(n)，但最坏情况是O(n²)。另外，考虑到内存有限，我会将数据分成两部分，并在每个部分上进行快速排序，然后将所有内容合并在一起。这需要O(n)时间来拆分数据，O(n)时间来合并数据，并使用快速排序对数据进行O(n log n)的排序，总运行时间为O(n log n)。

有没有人有改进意见？

- FranXh

---

这是作业吗？它有点像作业的味道。 - Cameron Skinner

你应该考虑将这个放到程序员部分。 - Rudy

不需要修改数据结构。我在YouTube上找到了一些很棒的UCBerkley课程，现在正在尝试用排序算法来练习自己。 - FranXh

@Rudy只是数据结构。 - FranXh

但是堆排序需要一个数组，这意味着我拥有的所有数据的数组将超出我的内存大小？还是应该仍然分割数据，然后使用堆排序进行排序？无论如何时间复杂度都会是一样的吗？@Mohamed - FranXh

鉴于如今内存价格如此便宜，我会确保自己拥有足够的内存。你可以以合理的价格购买一台带有32GB内存的机器，而对于那些需要更多内存的人来说，也可以购买高达1TB内存的机器。 - Peter Lawrey

Answer 1

你的归并排序思路非常合理。更普遍地说，这种类型的排序算法称为外部排序算法。这些算法通常按照你所描述的方式运作 - 将一些数据的子集加载到内存中，进行排序，然后将其写回磁盘。最后使用合并算法将所有东西合并在一起。选择加载多少数据以及使用哪种排序算法通常是主要关注点。我将主要关注排序算法的选择。

一般来说，你对快速排序的最坏情况行为的担忧并没有什么好担心的，因为如果你随机选择枢轴，则得到非常糟糕的运行时间的概率很低。即使数据已经排序，随机选择策略也能很好地工作，因为它没有最坏情况的输入（除非有人知道你的随机数生成器和种子）。你还可以使用类似introsort的快速排序变体作为你的排序算法，以避免这种最坏情况。

话虽如此，既然您已经知道数据已经部分排序，您可能需要考虑使用自适应排序算法来进行排序。 您已经提到了插入排序，但还有更好的自适应算法可用。 如果内存稀缺（如您所述），您可以尝试查看 smoothsort 算法，其最佳情况运行时间为O(n)，最坏情况运行时间为O(n log n)，并且仅使用O(1)内存。 它不像一些其他算法那样自适应（如Python的timsort，自然合并排序或笛卡尔树排序），但它具有较低的内存使用率。 它也不像快速排序那样快，但如果数据确实大多已排序，则表现很好。

希望这能有所帮助！

- templatetypedef

Answer 2

表面上看，我会用快速排序来进行分治，然后就可以收工了。许多算法问题都被过度思考了。

现在，如果你有测试数据可以使用，并且真的想掌握它，请将一个抽象类放在中间并进行基准测试。我们可以整天关注这些事情，但是知道数据已经部分排序，你需要进行测试。大多数快速排序实现在已排序数据下表现最差。

请考虑存在 许多排序算法，其中一些适合于已排序的集合。此外，当您知道集合已排序时，您可以在n时间内将其与另一个集合合并。因此，首先识别排序数据块可能会节省大量时间，与添加单个(n)传递进行比较，大大降低快速排序进入（n²）时间的概率。

- Jeff Ferland

---

是的，完全忘记了快速排序在处理已排序数据时表现不佳。 - FranXh

@Joel- 你可以对那些能够适应内存的数据块进行快速排序，然后再将它们合并在一起。这是一个完全合理的方法。 - templatetypedef

@Joel：“分而治之”……在结尾处合并的并行快速排序块对于提高速度和节省内存来说非常常见。 - Jeff Ferland

处理外部排序时，内存中的排序无关紧要，因为它仅占用极少量时间。在原始解决方案中，答案没有提到合并。鉴于快速排序也是一种分治算法（围绕分区进行划分），你可能会理解我的困惑。 - Joel

@Joel 不，我不理解你的困惑。相反，我被你所困惑......你在最后的评论中认识到这是一个外部排序，因此可用的总内存不是主要限制，但是你之前告诉我它不能适合内存，因此快速排序是一个糟糕的选择。 - Jeff Ferland