java中集合#排序方法的时间复杂度是多少?[英] What is the time complexity of Collections#sort method in java?

问题描述

java中Collections#sort方法的时间复杂度是多少?使用哪种算法?

Collection#sort 是对 10^6 的 ArrayList 进行排序的好方法吗?

推荐答案

这取决于你使用的Java版本. 但是最终Big-O时间复杂度仍然是O(N*log(N)).

对于 Java 6,它是合并排序的修改版本.检查这里的描述:Collections#sort 用于 Java 6

<块引用>

排序算法是经过修改的合并排序(如果低位子列表中的最高元素小于高位子列表中的最低元素,则忽略合并).该算法提供有保证的 n log(n) 性能.指定的列表必须是可修改的,但不必调整大小.这个实现将指定的列表转储到一个数组中,对数组进行排序,并遍历列表,从数组中的相应位置重置每个元素.这避免了由于尝试对链表进行就地排序而导致的 n2 log(n) 性能.

对于 Java 7,它进行了改进:Collections#sort for Java 7 由于 增强.请注意,TimSort 具有 O(N) 的最佳情况,并且证明比之前的实现更快.

<块引用>

实现说明:此实现是一种稳定的、自适应的、迭代的归并排序,当输入数组部分排序时,它需要远少于 n 次 lg(n) 比较,而在输入数组随机排序时提供传统归并排序的性能.如果输入数组接近排序,则实现需要大约 n 次比较.临时存储要求从几乎排序的输入数组的小常数到随机排序的输入数组的 n/2 对象引用不等.

该实现在其输入数组中同等地利用升序和降序,并且可以在同一输入数组的不同部分利用升序和降序.它非常适合合并两个或多个排序数组:只需连接数组并对结果数组进行排序.

该实现改编自 Tim Peters 的 Python 列表排序(TimSort).它使用了 Peter McIlroy 在 1993 年 1 月的第四届 ACM-SIAM 离散算法研讨会论文集上的"乐观排序和信息论复杂性"中的技术.

这个实现将指定的列表转储到一个数组中,对数组进行排序,然后遍历列表,从数组中的相应位置重置每个元素.这避免了由于尝试对链表进行就地排序而导致的 n2 log(n) 性能.

<小时><块引用>

这是对 10^6 的 ArrayList 进行排序的好方法吗?

理论上,用起来就够了.但这让我想知道为什么你必须对内存中的数据进行排序.如果数据来自数据库,则使用索引列/字段对其进行排序,否则检查您是否知道将用于排序的字段的某些特征以及是否可以使用 O(N) 时间复杂度算法,例如 桶排序 或 基数排序.如果没有其他办法,请使用 Collections#sort.

本文地址:https://www.itbaoku.cn/post/978641.html