Java Collections.sort（nodes）使用什么排序？

time-complexity sorting collections java mergesort

2022-09-04 23:49:21

我认为它是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））。有人可以向我解释一下吗？

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

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

答案 1

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

答案 2

你排序了四个节点，所以你没有得到合并排序;排序切换到插入排序。

在Java中，Arrays.sort（）方法根据数据类型使用合并排序或调整的快速排序，并且为了实现效率，当排序的数组元素少于七个时，切换到插入排序。

Arrays.sort 由 Collections 类间接使用。

最近接受的一份错误报告表明，Java的Sun实现将在未来使用Python的timsort：http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124

（上面链接的timsort专著非常值得一读。