相关疑难解决方法(0)

Arrays使用该方法对原始数据类型进行排序DualPivotQuicksort,并使用merge-sort分别对复杂类型进行排序.(如果输入大小很小,则插入排序).

DualPivotQuicksort 仍然在大输入尺寸上使用合并排序,但是,它在一系列较小的输入尺寸上使用双快速排序.

我想知道的是 - 为什么在对原始类型和非原语类型进行排序时的策略存在差异？

算法的性能很大程度上取决于输入大小 - 而不是数据类型.compareTo()在原语(>,<,==)上调用而不是简单的幅度比较不会在内存中消耗额外的空间(因此不会减慢由于内存空间而导致的绝对时间性能),这在运行期间会很大-时间.

为什么Arrays.sort()方法对原始数据类型和复杂数据类型使用不同的排序策略？

TIA.

在Java中,基本类型的Arrays.sort()使用快速排序.另一方面,对象的Arrays.sort()使用Merge排序.同样适用于Collection.sort(),它也使用Merge排序.集合排序使用下面的Arrays排序实现.所以,简单来说,我可以说基元是使用快速排序排序的,但是对象是使用合并排序进行排序的.

我的猜测是它与自己的排序算法有关.关于快速排序vs合并排序的SO有很多讨论,像这样和这个.似乎存在相互冲突的主张哪个更好,这是可以理解的,因为这取决于数据集.

我的理解是

• 到位:快速排序获胜.可以在链接列表的就地实现合并排序
• 外部存储数据:合并排序获胜.
• 排序列表(由任何形式的链表支持):合并排序获胜.链接

Android API似乎遵循与Java相同的模式.这是我在Arrays.java中找到的

    public static void sort(long[] array) {
    DualPivotQuicksort.sort(array);
}

还有这个,

public static void sort(Object[] array) {
    ComparableTimSort.sort(array);
}

我不明白的是,是什么让Merge排序成为在Java或Android中排序对象的好选择？为什么不把这个决定留给开发者？

在与quicksortvs 相关的答案中mergesort,通常表示quicksort利用缓存局部性(引用的局部性)比mergesort.

由于这两种方法遵循分而治之的方法,我不明白如何quicksort更加缓存友好.任何人都可以提供更多相关的见解吗？

此外,还有关于就地合并排序的注释.如果这是实用的(我不知道是否),合并排序也可以缓存友好吗？

这个问题出现在我的算法课上。这是我的想法：

我认为答案是否定的，具有O（n）的最坏情况时间复杂度的算法并不总是比O（n ^ 2）的最坏情况时间复杂度的算法快。

例如，假设我们有总时间函数S（n）= 99999999n和T（n）= n ^ 2。那么显然S（n）= O（n）和T（n）= O（n ^ 2），但是对于所有n <99999999，T（n）比S（n）更快。

这个推理有效吗？我有点怀疑，尽管这是一个反例，但它可能是错误观念的反例。

非常感谢！