可能是重复的问题:
为什么Java数组使用两种不同的排序算法来处理不同类型的数据？
我在阅读关于各种排序实现的Arrays doc时，注意到有些实现使用了调整后的快速排序，而另一些则使用了修改后的归并排序。为什么会存在这样的差异呢？
谢谢！
1个回答
26
在对原始类型的数组进行排序时，使用快速排序（Quicksort）；而对于Object[]类型的数组，则使用归并排序（mergesort）。
使用归并排序来处理对象的主要原因是它是稳定的——它不会重新排列相等的元素：http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
对于原始类型的排序来说，排序的稳定性是无意义的，因为你无法区分两个相等的值。因此，使用快速排序（除非是对一个对象数组进行排序，这时会使用归并排序）。此外，快速排序可以就地完成，因此无需分配另一个数组。
- Eugene Retunsky
5
在今天的世界中，归并排序已成为主导排序算法，因为它可以实现使用多个核心。 - ControlAltDel
好的观点，但JDK目前还没有使用这个。 - Eugene Retunsky
5JDK 7不再使用归并排序，而是使用传说中的TimSort！ - Louis Wasserman
@LouisWasserman 很酷，谢谢你提供这个信息。你为什么称它为“神话”呢？ - OckhamsRazor
“神话般”的是因为它非常复杂，不多人理解或会自己实现它，但它仍然异常聪明和快速。 - Louis Wasserman
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接