Java Collections.sort(nodes) 使用什么排序？

Question

我认为是MergeSort，即O(n log n)。

但是，以下输出不同意：

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

我正在按序列号对 4 个节点的节点列表进行排序，并且排序正在进行 6 次比较。我很困惑，因为 6 > (4 log(4))。谁可以给我解释一下这个？

附：它是合并排序，但我仍然不明白我的结果。

谢谢大家的回答。谢谢汤姆纠正我的数学。

Answer 1

为O（n log n）的，并不意味着比较的数量将等于或小于n登录N，只是时间采取将的尺度比例为n为log N。尝试做试验用8个节点，或16个节点，或32个节点，并检查出的定时。

Answer 2

您整理四个节点，所以你没有得到归并排序;排序切换到插入排序。

  

在Java中，Arrays.sort（）方法使用合并排序或取决于数据类型和执行效率的切换到插入排序时少于七个阵列元素被排序的调谐快速排序。（适用维基百科，强调）

Arrays.sort由Collections类间接使用。

这是近日在接受bug报告表示将Sun的Java实现将使用Python的 timsort在未来： http://bugs.sun.com /bugdatabase/view_bug.do?bug_id=6804124

（该专着timsort，上面链接，是非常值得的读数。）

Answer 3

处理数据量 n 的算法 A(n) 的时间复杂度为 O(f(n))，对于某个函数 f，如果存在两个严格正的常数 C_inf 和 C_sup，使得：

C_inf 。f(n) < ExpectedValue(OperationCount(A(n))) < C_sup 。f(n)

有两点需要注意：

• 实际常数 C 可以是任何值，并且 做 取决于操作的相对成本（取决于语言、VM、体系结构或操作的实际定义）。例如，在某些平台上，+ 和 * 具有相同的成本，而在其他平台上，后者的成本要慢一个数量级。

• 被称为“O(f(n))”的量是 预期的 操作计数，基于您正在处理的数据的某些可能任意模型。例如，如果您的数据几乎完全排序，则合并排序算法将主要是 O(n)，而不是 O(n 。对数(n))。

Answer 4

我已经写了一些东西，你可能有兴趣在有关Java排序算法和采取的 Collections.sort（）的一些性能测量。目前该算法是一种归并排序与插入排序一旦你到子列表具有一定规模（ NB这个算法很可能会在Java 7中修改）。

您真的应该走大O符号作为如何算法将总规模的指示;对于特定类型的，精确的时间将通过该计算预测（您将在我的图中看到的时间偏离，即相互结合两种排序算法有不同的性能特点，所以对于一个排序的总时间是位更复杂）。

这是说，作为一个粗略的指导，每次增加一倍的元素数量，如果由2.2乘以预期的时间，你就不会远。 （它没有多大意义真的几个要素非常小的名单做到这一点，虽然。）