为什么要使用两种不同的算法来对数组进行排序？

Question

10

在Arrays类中，使用快速排序算法对原始数据类型进行排序，但对于对象排序，则使用归并排序算法。

我想知道这是为什么？

- user590444

2

你能提供一下你所说的Java实现的链接吗？这并不是JLS所规定的。 - templatetypedef

@templatetypedef 这不是必须的，但它是一个“实现注释”，在 sun 的实现中也是如此。Arrays 的 javadoc 已经将这一点澄清了。 - Bozho

@Bozho- 我同意... 我的问题主要是这是否在Sun的实现中，还是在OpenJDK等中，以便我可以自己查找源代码。 - templatetypedef

2个回答

1

只是猜测，但最坏情况下快排是O（n ^ 2），而归并排序是稳定的（保证O（n log n））。

快速排序的最坏情况是由相等的值触发的...相等的原始类型是相同的，而“相等”的对象可能不是。

- MarcB

3

“stable (guaranteed O(n log n))” - 稳定性与悲观复杂度无关。稳定排序算法会保持被视为相等的元素的顺序。 - Tomasz Nurkiewicz

你说得对。脑抽了，抱歉 :)然而，归并排序比快速排序返回更可预测的执行时间，后者的执行时间可以从O(n log n)变化到O(n^2)。这就是我的意思，我不应该在谈论排序算法时随便使用“稳定”这个词^^ - MarcB

你必须仔细地构建输入数据（尽管这可能是一个问题...但对于DDOS来说是一种有趣的方式），才能接近O（n ^ 2）的快速排序，而快速排序通常比归并排序更快，因为常数确实很重要。不，原因只是没有有效的快速排序实现是稳定的，这是Java库的一个条件。 - Voo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paŭlo Ebermann · Accepted Answer

使用归并排序的原因是要求一个稳定的算法，即相等的对象（通过compareTo()或compare()比较）在排序前后保持相同的相对顺序。

对于原始类型，相等意味着“不可区分性”。当对{5, 3, 5}进行排序以得到{3, 5, 5}时，不管哪个“5”先出现都没有关系。因此，可以在这里使用速度更快但不稳定的快速排序算法。