为什么 Java 的 Arrays.sort 方法对不同的类型使用两种不同的排序算法? [英] Why does Java's Arrays.sort method use two different sorting algorithms for different types?

问题描述

Java 6 的 Arrays.sort 方法对原始数组使用快速排序，对对象数组使用归并排序.我相信大多数情况下 Quicksort 比合并排序更快，而且消耗的内存更少.我的实验支持这一点，尽管两种算法都是 O(n log(n)).那么为什么不同的算法用于不同的类型?

Java 6's Arrays.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(n log(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.

由于原始类型没有身份(没有办法区分两个具有相同值的整数)，这对他们来说无关紧要.但是对于引用类型，它可能会导致某些应用程序出现问题.因此，对于那些使用稳定的归并排序.

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，不对原始类型使用 (guaranteed n*log(n)) 稳定归并排序的一个原因可能是它需要对数组进行克隆.对于引用类型，被引用的对象通常比引用数组占用更多的内存，这通常无关紧要.但是对于原始类型，完全克隆数组会使内存使用量增加一倍.

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.

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