一个很好的排序算法,适用于大部分排序的数据,并不全部适合内存？

Question

如果给你:

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

你会选择哪种排序算法？我在插入和快速排序之间进行辩论.我知道插入排序的最佳情况是O(n),但最坏的情况是O(n ²).另外,考虑到内存有限的事实,我将数据分成两部分,并在每一部分上快速排序,然后将所有内容合并在一起.对于O(n log n)的净运行时间,需要O(n)时间来分割数据,O(n)用于合并数据,O(n log n)用于使用快速排序对数据进行排序.

有没有人对如何改进这个有任何建议？

Answer 1

你的类似mergesort的方法似乎很合理.更一般地,这种类型的排序算法称为外部排序算法.这些算法通常可以像您所描述的那样工作 - 将一些数据子集加载到内存中,对其进行排序,然后将其写回磁盘.最后,使用合并算法将所有内容合并在一起.加载多少以及使用哪种排序算法的选择通常是主要关注点.我将主要关注排序算法的选择.

您对快速排序的最坏情况行为的担忧通常无需担心,因为如果您随机选择枢轴,则运行时非常糟糕的概率很低.即使数据已经排序,随机数据转换策略也可以正常工作,因为它没有最坏情况输入(除非有人知道您的随机数生成器和种子).您也可以使用像introsort这样没有最坏情况行为的快速排序变体作为排序算法,以避免出现这种最坏情况.

也就是说,由于您知道数据已经部分排序,您可能需要查看自适应排序算法以进行排序.你已经提到了插入排序,但是有更好的自适应算法.如果内存不足(如您所述),您可能需要尝试查看smoothsort算法,该算法具有最佳情况运行时O(n),最坏情况运行时O(n log n),并且仅使用O( 1)记忆.它不像其他算法那样具有自适应性(如Python的timsort,自然mergesort或 笛卡尔树排序),但它具有较低的内存使用率.它也不如一个好的快速排序快,但如果数据真的大部分排序,它可以做得很好.

希望这可以帮助!