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

标签 java algorithm sorting data-structures space-complexity

<分区>

如果给你:

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

你会选择哪种排序算法? 我在插入和快速排序之间争论不休。我知道插入排序的最佳情况是 O(n),但最坏情况是 O(n2)。另外,考虑到内存有限,我会把数据分成两部分,对每一部分进行快速排序,然后将所有内容合并在一起。拆分数据需要 O(n) 时间,合并数据需要 O(n) 时间,使用快速排序对数据进行排序需要 O(n log n) 时间,净运行时间为 O(n log n)。

有人对如何改进这个有什么建议吗?

最佳答案

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

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

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

希望这对您有所帮助!

关于java - 对于不能全部放入内存的大多数排序数据的良好排序算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9493190/

相关文章:

java - 将参数传递给在单独线程中调用的函数

以比较函数作为参数调用快速排序函数

java - Runtime.getRuntime().exec ("C:\cygwin\bin\bash.exe") 没有可读取的输入

java - libgdx 游戏崩溃 : "A L lib: (EE) alc_cleanup: 1 device not closed" on Desktop and "Fatal signal 11 (SIGSEGV)" on android

java - 从字符串打印偶数字符 - 错误非静态方法无法从静态上下文引用

jquery - 使用 jQuery 对 Select 字段进行排序

python - 循环将列表拆分为不同的子列表

algorithm - 有人可以用简单的英语向我解释 Daniel Page 的 Restricted Weak Composition 算法吗?

image - 从 3 个静态摄像机的角度来看如何恢复其在 3d 空间中的位置?

string - 从给定的单词最大化交叉点生成填字游戏