为什么java.util.Arrays.sort(Object[])使用2种排序算法?

2022-09-01 11:44:47

我发现使用2种排序算法(在JDK 1.6中)。java.util.Arrays.sort(Object[])

伪代码:

if(array.length<7)
   insertionSort(array);
else
   mergeSort(array);

为什么这里需要2种排序?为了效率?


答案 1

重要的是要注意,在实践中,算法并不总是比算法快。这取决于常量和所涉及的范围。(请记住,渐近表示法测量的是相对增长率,而不是绝对速度)。O(N log N)O(N^2)N

对于小的,插入排序实际上确实击败了合并排序。对于几乎排序的数组,它也更快。N

这里有一句话

尽管它是具有最坏情况时间的基本排序算法之一,但插入排序是首选算法,无论是在数据几乎排序时(因为它是自适应的),还是在问题大小较小(因为它的开销较低)时。O(N^2)

由于这些原因,并且由于插入排序也很稳定,因此插入排序通常用作较高开销的分而治之的排序算法(如合并排序或快速排序)的递归基例(当问题大小较小时)。

以下是最佳排序算法对几乎排序列表论文的另一句话:

直接插入排序最适合小型或非常接近排序的列表

这意味着,在实践中:

  • 某些具有较高渐近上限的算法 A1 可能比具有较低渐近上限的另一种已知算法 A2 更可取
  • 某些混合算法可能会根据输入大小调整不同的算法

相关问题


数值示例

让我们考虑以下两个函数:

  • f(x) = 2x^2;这个函数有一个二次增长率,即”O(N^2)"
  • g(x) = 10x;这个函数具有线性增长率,即”O(N)"

现在,让我们将两个函数绘制在一起:

alt text
来源:WolframAlpha:图 2x^2 和 10x 从 0 到 10 的 x

请注意,在 、 之间,但对于任何较大的 ,很快就会长出来。x=0..5f(x) <= g(x)xf(x)g(x)

类似地,如果 A1 是开销较低的二次算法,而 A2 是开销较高的线性算法,则对于较小的输入,A1 可能比 A2 快。

因此,如果您选择这样做,您可以创建一个混合算法A3,该算法仅根据输入的大小选择两种算法中的一种。这是否值得付出努力取决于所涉及的实际参数。

已经对排序算法进行了许多测试和比较,并且决定由于插入排序胜过小数组的合并排序,因此对于Arrays.sort实现两者都是值得的。


答案 2

这是为了速度。mergeSort 的开销足够高,对于短数组,它比插入排序慢。