为什么Java数组使用两个不同的排序算法对不同类型的？ [英] Why java Arrays use two different sort algorithms for different types?

问题描述

Arrays.java 的排序方法采用快速排序的基本类型数组和对象数组归并排序。我相信，大部分时间快速排序比归并排序速度更快，成本更低的内存。我的实验支持，虽然两种算法为O（n日志（N））。那么，为什么是用于不同类型不同的算法？

Arrays.java's sort 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(nlog(n)). So why are different algorithms used for different types?

推荐答案

最可能的原因：快速排序是没有的稳定的，即相等的条目可以在排序过程中改变它们的相对位置;除其他事项外，这意味着如果你整理一个已排序的数组，它可能不会保持不变。

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.

由于原始类型没有身份（没有办法区分两个int具有相同的值），这没有关系他们。但对于引用类型，它可能会导致一些应用程序出现问题。因此，稳定的合并排序用于那些

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，理由不使用（保证的n * log（n））的合并排序基本类型可能是因为它需要使阵列的克隆。引用类型，其中提到的对象通常占用比引用的数组得多存储器，这通常并不重要。但对于基本类型，克隆阵列直接加倍的内存使用量。

OTOH, a reason not to use the (guaranteed n*log(n)) 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.

这篇关于为什么Java数组使用两个不同的排序算法对不同类型的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！