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这是归并排序，但我还是不明白我的结果.

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

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

推荐答案

O(n log n) 并不意味着比较次数将等于或小于 n log n，只是所花费的时间将 scale 与 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屋！