文章/答案/技术大牛

发布

社区首页 >问答首页 >为什么java.util.Arrays.sort(Object[])使用两种排序算法？

问为什么java.util.Arrays.sort(Object[])使用两种排序算法？
EN

Stack Overflow用户

提问于 2010-08-25 22:23:59

回答 3查看 9.1K关注 0票数 30

我发现java.util.Arrays.sort(Object[])使用了两种排序算法(在JDK1.6中)。

伪代码：

if(array.length<7)
   insertionSort(array);
else
   mergeSort(array);

为什么这里需要两种排序？为了提高效率？

java

algorithm

sorting

collections

回答 3

Stack Overflow用户

发布于 2010-08-25 22:26:25

这是为了速度。mergeSort的开销足够高，对于短数组，它将比插入排序慢。

票数 5

Stack Overflow用户

发布于 2010-08-25 22:59:23

引用自：http://en.wikipedia.org/wiki/Insertion_sort

Some divide-and-conquer algorithms such as quicksort and mergesort sort by 
recursively dividing the list into smaller sublists which are then sorted. 
A useful optimization in practice for these algorithms is to use insertion 
sort for sorting small sublists, where insertion sort outperforms these more 
complex algorithms. The size of list for which insertion sort has the advantage 
varies by environment and implementation, but is typically between eight and 
twenty elements.

票数 3

Stack Overflow用户

发布于 2010-08-25 22:26:58

似乎他们认为对于短数组，mergeSort(array)速度更慢。希望他们真的测试过了。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/3566843

复制

相似问题

问为什么java.util.Arrays.sort(Object[])使用两种排序算法？
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么java.util.Arrays.sort(Object[])使用两种排序算法？EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么java.util.Arrays.sort(Object[])使用两种排序算法？
EN