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

I found that java.util.Arrays.sort(Object[]) use 2 kinds of sorting algorithms(in JDK 1.6).

伪代码:

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

为什么这里需要两种分类?为了效率?

最佳答案

It's important to note that an algorithm that is O(N log N) is not always faster in practice than an O(N^2) algorithm. It depends on the constants, and the range of N involved. (Remember that asymptotic notation measures relative growth rate, not absolute speed).

For small N, insertion sort in fact does beat merge sort. It's also faster for almost-sorted arrays.

这是一个报价:

Although it is one of the elementary sorting algorithms with O(N^2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

这是最佳排序算法的另一句话,适用于几乎排序的列表纸张:

直插入排序最适用于较小或非常接近排序的列表

实际上,这意味着:

  • Some algorithm A1 with higher asymptotic upper bound may be preferable than another known algorithm A2 with lower asymptotic upper bound
  • Some hybrid algorithms may adapt different algorithms depending on the input size

相关问题

  • 哪种排序算法最适合对几乎完全排序的列表进行重新排序?
  • 是否有充分的理由使用插入排序?

数值示例

让我们考虑以下两个功能:

  • f(x) = 2x^2; this function has a quadratic growth rate, i.e. "O(N^2)"
  • g(x) = 10x; this function has a linear growth rate, i.e. "O(N)"

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

alt text
Source: WolframAlpha: plot 2x^2 and 10x for x from 0 to 10

Note that between x=0..5, f(x) <= g(x), but for any larger x, f(x) quickly outgrows g(x).

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

因此,您可以选择创建混合算法A3,该算法根据输入的大小简单地选择两种算法之一。是否值得为此付出努力取决于所涉及的实际参数。

Many tests and comparisons of sorting algorithms have been made, and it was decided that because insertion sort beats merge sort for small arrays, it was worth it to implement both for Arrays.sort.

    公众号
    关注公众号订阅更多技术干货!