java - 对于不能全部放入内存的大多数排序数据的良好排序算法？

Question

<分区>

Answer 1

您的类似归并排序的方法似乎非常合理。更一般地说，这种类型的排序算法称为 external sorting algorithm。 .这些算法通常按照您所描述的那样工作——将数据的某些子集加载到内存中，对其进行排序，然后将其写回磁盘。最后，使用合并算法将所有内容重新合并在一起。选择加载多少和使用哪种排序算法通常是主要问题。我将主要关注排序算法的选择。

您对快速排序的最坏情况行为的担忧一般来说无需担心，因为如果您随机选择主元，则运行时间非常糟糕的可能性很低。即使数据已经排序，随机枢轴策略也能很好地工作，因为它没有最坏情况的输入(除非有人知道你的随机数生成器和种子)。您还可以使用像 introsort 这样的快速排序变体。 ，它没有最坏情况的行为，作为您的排序算法以避免这种最坏情况。

也就是说，既然您知道数据已经部分排序，您可能想要查看 adaptive sorting algorithm为您的排序步骤。您为此提到了插入排序，但那里有更好的自适应算法。如果内存不足(如您所述)，您可能想尝试查看 smoothsort 算法，其最佳情况运行时间为 O(n)，最坏情况运行时间为 O(n log n)，并且仅使用 O(1) 内存。它不像其他一些算法(如 Python 的 timsort 、 natural mergesort 或 Cartesian tree sort )那样自适应，但它的内存使用率较低。它也没有快速排序那么快，但如果数据确实大部分是排序的，它可以做得很好。

希望这对您有所帮助!