为什么java.util.Arrays.sort（对象[]）使用2种排序算法？

问题描述：

我发现， java.util.Arrays.sort（对象[]）使用2种排序算法（在JDK 1.6）的。

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

伪code：

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

为什么它需要2种这里的排序？为了提高效率？

Why does it need 2 kinds of sorting here? for efficiency?

答

要注意，算法是 O（N日志N），这一点很重要并不总是快于实践比 O（N ^ 2）算法。这取决于常数，范围 N 参与。（请记住，渐近记法衡量相对生长率，没有绝对速度）。

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).

有关小 N ，其实插入排序并击败归并排序。它也快了近排序的数组。

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

下面的报价：

虽然它是基本的排序算法，一个O（N ^ 2）最坏情况下的时间，插入排序是首选的算法或者当数据是近排序（因为它是自适应的），或者当问题尺寸小（因为它具有低的开销）。

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.

下面是从的最适合近排序列表排序算法的纸另一个报价

Here's another quote from Best sorting algorithm for nearly sorted lists paper:

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

straight insertion sort is best for small or very nearly sorted lists

这句话的意思是，在实践中：

What this means is that, in practice:

在一些算法的 A 1 的具有较高渐近上限可能是preferable比其他已知算法的 A ₂低渐近上限
- 也许 A ₂的是太复杂，执行
- 也许它并不在 N 考虑范围无所谓
  - 见例如铜匠，威诺格拉德算法
  - Some algorithm A₁ with higher asymptotic upper bound may be preferable than another known algorithm A₂ with lower asymptotic upper bound
    - Perhaps A₂ is just too complicated to implement
    - Or perhaps it doesn't matter in the range of N considered
      - See e.g. Coppersmith–Winograd algorithm
      - Which排序算法是最适合进行重新排序几乎完全排序列表？
      - Is有过一个很好的理由来使用插入排序？
      - Which sorting algorithm is best suited to re-sort an almost fully sorted list?
      - Is there ever a good reason to use Insertion Sort?
      让我们考虑这两个功能：
      
      Let's consider these two functions:
      - F（X）= 2X ^ 2 ;这个功能有一个二次的增长速度，即 O（N ^ 2）
      - G（X）= 10倍;这个功能有一个线性的增长速度，即 O（N）
      - 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)"
      现在我们绘制两种功能于一体：
      
      Now let's plot the two functions together:
      
      ^{的来源：的的 WolframAlpha的：剧情2X ^ 2和10倍的x在0至10}
      
      ^{Source: WolframAlpha: plot 2x^2 and 10x for x from 0 to 10}
      
      注意的 X = 0..5 ， F（X）＆LT; = G（x） ，但对于任何较大 X ，函数f（x）快速发展超越 G（x）。
      
      Note that between x=0..5, f(x) <= g(x), but for any larger x, f(x) quickly outgrows g(x).
      
      类似地，如果的 A 1 的是一个二次算法具有低开销，而 A ₂的是具有较高的开销，对于较小的输入线性算法的 A 1 的可能比的 A ₂的速度更快。
      
      Analogously, if A₁ is a quadratic algorithm with a low overhead, and A₂ is a linear algorithm with a high overhead, for smaller input, A₁ may be faster than A₂.
      
      因此，你可以，你应该选择这样做，创建一个混合算法的 A 3 的，它简单地选择根据输入的大小两种算法中的一个。不管这是值得的取决于所涉及的实际参数。
      
      Thus, you can, should you choose to do so, create a hybrid algorithm A₃ which simply selects one of the two algorithms depending on the size of the input. Whether or not this is worth the effort depends on the actual parameters involved.
      
      许多测试和排序算法比较做了，并决定，由于插入排序次归并排序为小数组，它是值得的，以实施Arrays.sort$c$c>.
      
      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.

为什么java.util.Arrays.sort（对象[]）使用2种排序算法？

相关推荐