Roa*_*oam 7 java arrays sorting data-structures
Arrays使用该方法对原始数据类型进行排序DualPivotQuicksort,并使用merge-sort分别对复杂类型进行排序.(如果输入大小很小,则插入排序).
DualPivotQuicksort 仍然在大输入尺寸上使用合并排序,但是,它在一系列较小的输入尺寸上使用双快速排序.
我想知道的是 - 为什么在对原始类型和非原语类型进行排序时的策略存在差异？
算法的性能很大程度上取决于输入大小 - 而不是数据类型.compareTo()在原语(>,<,==)上调用而不是简单的幅度比较不会在内存中消耗额外的空间(因此不会减慢由于内存空间而导致的绝对时间性能),这在运行期间会很大-时间.
为什么Arrays.sort()方法对原始数据类型和复杂数据类型使用不同的排序策略？
TIA.
因为排序引用类型保证是稳定的,而排序原语不需要(如此快速排序,可以使用非稳定排序算法;另一方面合并排序实际上是稳定的).还要注意的是快速排序是一般比归并更优化的(见本为好),这可以解释为什么它采取排序元时的优势.
来自Arrays.sort:
这种类型保证是稳定的:相同的元素不会因排序而重新排序.
| 归档时间： |
|
| 查看次数： |
735 次 |
| 最近记录： |