blocks|key|4434072|text|最可能的原因是:快速排序不稳定，即相等的条目在排序过程中可能会改变它们的相对位置；此外，这意味着如果您对已经排序的数组进行排序，它可能不会保持不变。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4434073|由于原语类型没有标识(无法区分具有相同值的两个int)，因此这对它们无关紧要。但是对于引用类型，这可能会给某些应用程序带来问题。因此，对这些数据使用稳定的合并排序。|4434074|OTOH，不对原始类型使用(保证n*log(n))稳定合并排序的一个原因可能是它需要克隆数组。对于引用类型，引用的对象通常比引用数组占用更多的内存，这通常无关紧要。但是对于原语类型，直接克隆数组会使内存使用量加倍。|4434075|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

The most likely reason: quicksort is not stable, i.e. equal entries can change their relative position during the sort; among other things, this means that if you sort an already sorted array, it may not stay unchanged.

Since primitive types have no identity (there is no way to distinguish two ints with the same value), this does not matter for them. But for reference types, it could cause problems for some applications. Therefore, a stable merge sort is used for those.

OTOH, a reason not to use the (guaranteed n*log(n)) stable merge sort for primitive types might be that it requires making a clone of the array. For reference types, where the referred objects usually take up far more memory than the array of references, this generally does not matter. But for primitive types, cloning the array outright doubles the memory usage.

blocks|key|1777731|text|根据this+answer中引用的Java7API文档，用于对象阵列的Arrays#Sort()现在使用TimSort，它是MergeSort和InsertionSort的混合体。另一方面，原语数组的Arrays#sort()现在使用Dual-Pivot+QuickSort。这些更改是从Java+SE+7开始实现的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1777732|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort|1|http://en.wikipedia.org/wiki/Timsort|2|http://epubs.siam.org/doi/abs/10.1137/1.9781611972931.5^0|Z|D|2S|D|2|B|0|1G|7|1|39|K|2|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]|$9|U|A|V|B|C]]|D|@$9|W|A|X|1|Y]|$9|Z|A|10|1|11]|$9|12|A|13|1|14]]|E|$]]|$1|F|3|-4|5|6|7|15|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]|N|$5|I|J|K|E|$L|O]]|P|$5|I|J|K|E|$L|Q]]]]

According to Java 7 API docs cited in <a href="https://stackoverflow.com/questions/4018332/is-java-7-using-tim-sort-for-the-method-arrays-sort">this answer</a>, <code>Arrays#Sort()</code> for object arrays now uses <a href="http://en.wikipedia.org/wiki/Timsort" rel="noreferrer">TimSort</a>, which is a hybrid of MergeSort and InsertionSort. On the other hand, <code>Arrays#sort()</code> for primitive arrays now uses <a href="http://epubs.siam.org/doi/abs/10.1137/1.9781611972931.5" rel="noreferrer">Dual-Pivot QuickSort</a>. These changes were implemented starting in Java SE 7.

blocks|key|1777708|text|我能想到的一个原因是，快速排序的最坏情况时间复杂度为O(n%5E2)，而合并排序的最坏情况时间复杂度为O(n+log+n)。对于对象数组，有一个合理的预期是会有多个重复的对象引用，这是快速排序效果最差的一种情况。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1777709|有一个不错的visual+comparison+of+various+algorithms，特别要注意最右边的图，用于不同的算法。|offset|length|1777710|entityMap|0|LINK|mutability|MUTABLE|url|http://www.sorting-algorithms.com/quick-sort^0|0|6|13|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

One reason I can think of is that quicksort has a worst case time complexity of O(n^2) while mergesort retains worst case time of O(n log n). For object arrays there is a fair expectation that there will be multiple duplicate object references which is one case where quicksort does worst.

There is a decent <a href="http://www.sorting-algorithms.com/quick-sort" rel="nofollow noreferrer">visual comparison of various algorithms</a>, pay particular attention to the right-most graph for different algorithms.

blocks|key|1029409|text|我正在上Coursera的算法课程，在一次讲座中，Bob+Sedgewick教授提到了对Java+system+sort的评估：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1029410|1029411|“如果程序员使用的是对象，也许空间不是最重要的考虑因素，合并排序使用的额外空间可能不是问题。如果程序员使用原语类型，性能可能是最重要的，所以他们使用快速排序。”|blockquote|1029412|1029413|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|J|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|K|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|L|8|@]|9|@]|A|$]]|$1|G|3|-4|5|6|7|M|8|@]|9|@]|A|$]]]|H|$]]

I was taking Coursera class on Algorithms and in one of the lectures Professor Bob Sedgewick mentioning the assessment for Java system sort:

<blockquote>
 "If a programmer is using objects, maybe space is not a critically
 important consideration and the extra space used by a merge sort maybe
 not a problem. And if a programmer is using primitive types, maybe
 the performance is the most important thing so they use quick sort."
</blockquote>

blocks|key|4434342|text|java.util.Arrays将quicksort用于基本类型，如int和mergesort，用于实现可比较或使用比较器的对象。使用两种不同方法的想法是，如果程序员使用对象，那么空间可能不是最重要的考虑因素，所以合并排序使用的额外空间可能不是问题，如果程序员使用原语类型，性能可能是最重要的，所以使用quicksort。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|4434343|例如:这就是排序稳定性很重要的例子。|4434344|​|4434345|📷|atomic|4434346|4434347|这就是为什么稳定的排序对于对象类型是有意义的，特别是可变对象类型和具有比排序键更多数据的对象类型，mergesort就是这样一种排序。但是对于原始类型来说，稳定性不仅仅是无关紧要的。这毫无意义。|4434348|来源：INFO|4434349|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/83352e2df61c66d2da7fdf37ee7ceca9.png|imageAlt|1|LINK|MUTABLE|url|http://cafe.elharo.com/programming/java-programming/why-java-util-arrays-uses-two-sorting-algorithms/^0|H|9|12|9|1G|3|1M|3|2Z|4|47|9|0|0|0|0|1|0|0|0|0|3|4|1|0^^$0|@$1|2|3|4|5|6|7|15|8|@$9|16|A|17|B|C]|$9|18|A|19|B|C]|$9|1A|A|1B|B|C]|$9|1C|A|1D|B|C]|$9|1E|A|1F|B|C]|$9|1G|A|1H|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1I|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|1J|8|@]|D|@]|E|$]]|$1|J|3|K|5|L|7|1K|8|@]|D|@$9|1L|A|1M|1|1N]]|E|$]]|$1|M|3|I|5|6|7|1O|8|@]|D|@]|E|$]]|$1|N|3|O|5|6|7|1P|8|@]|D|@]|E|$]]|$1|P|3|Q|5|6|7|1Q|8|@]|D|@$9|1R|A|1S|1|1T]]|E|$]]|$1|R|3|-4|5|6|7|1U|8|@]|D|@]|E|$]]]|S|$T|$5|U|V|W|E|$X|Y|Z|-4]]|10|$5|11|V|12|E|$13|14]]]]

java.util.Arrays uses quicksort for primitive types such as int and mergesort for objects that implement Comparable or use a Comparator. The idea of using two different methods is that if a programmer’s using objects maybe space is not a critically important consideration and so the extra space used by mergesort maybe’s not a problem and if the programmer’s using primitive types maybe performance is the most important thing so use the quicksort.

For Example: 
This is the example when sorting stability matters.

<a href="https://i.stack.imgur.com/7hC6u.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/7hC6u.png" alt="enter image description here"></a>

That’s why stable sorts make sense for object types, especially mutable object types and object types with more data than just the sort key, and mergesort is such a sort. But for primitive types stability is not only irrelevant. It’s meaningless.

Source: <a href="http://cafe.elharo.com/programming/java-programming/why-java-util-arrays-uses-two-sorting-algorithms/" rel="nofollow noreferrer">INFO</a>

blocks|key|1774734|text|Java的Arrays.sort方法使用快速排序、插入排序和合并排序。甚至在OpenJDK代码中实现了单轴和双轴快速排序。最快的排序算法取决于具体情况，优胜者是:小数组的插入排序(当前选择了47个)，排序最多的数组的合并排序，以及剩余数组的快速排序，因此Java的Array.sort()会尝试根据这些条件选择要应用的最佳算法。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1774735|entityMap^0|5|B|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

Java's <code>Arrays.sort</code> method uses quicksort, insertion sort and mergesort. There is even both a single and dual pivot quicksort implemented in the OpenJDK code. The fastest sorting algorithm depends on the circumstances and the winners are: insertion sort for small arrays (47 currently chosen), mergesort for mostly sorted arrays, and quicksort for the remaining arrays so Java's Array.sort() tries to choose the best algorithm to apply based on those criteria.

Java 6's <code>Arrays.sort</code> method uses Quicksort for arrays of primitives and merge sort for arrays of objects. I believe that most of time Quicksort is faster than merge sort and costs less memory. My experiments support that, although both algorithms are O(n log(n)). So why are different algorithms used for different types?

Why does Java's Arrays.sort method use two different sorting algorithms for different types?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

Java6的Arrays.sort方法对基元数组使用快速排序，对对象数组使用合并排序。我相信在大多数情况下，快速排序比合并排序更快，而且占用的内存更少。我的实验支持这一点，尽管这两个算法都是O(n log(n))。那么为什么不同的类型使用不同的算法呢？

问为什么Java的Arrays.sort方法对不同的类型使用两种不同的排序算法？
EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么Java的Arrays.sort方法对不同的类型使用两种不同的排序算法？EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么Java的Arrays.sort方法对不同的类型使用两种不同的排序算法？
EN