Java Collections.sort（nodes）使用什么类型？ [英] What sort does Java Collections.sort(nodes) use?

问题描述

我认为是MergeSort，它是O（n log n）。

I think it is MergeSort, which is O(n log n).

但是，以下输出不同意：

However, the following output disagrees:

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

我正在排序一个节点4个节点按顺序号，而排序是做6个比较。
我很困惑，因为6>（4 log（4））。有人可以向我解释这个问题吗？

I am sorting a nodelist of 4 nodes by sequence number, and the sort is doing 6 comparisons. I am puzzled because 6 > (4 log(4)). Can someone explain this to me?

PS这是mergesort，但我还是不明白我的结果。

感谢大家的回答。感谢Tom纠正我的数学。

Thanks for the answers everyone. Thank you Tom for correcting my math.

推荐答案

O（n log n）并不意味着比较的数量等于或小于n log n，只是所用的时间将与n log n成比例地缩放。尝试使用8个节点，16个节点或32个节点进行测试，并检查时间。

O(n log n) doesn't mean that the number of comparisons will be equal to or less than n log n, just that the time taken will scale proportionally to n log n. Try doing tests with 8 nodes, or 16 nodes, or 32 nodes, and checking out the timing.

这篇关于Java Collections.sort（nodes）使用什么类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！