例如,我有两个 ArrayList:
ArrayList a = new ArrayList();
a.add(10);
a.add(35);
a.add(51);
ArrayList b = new ArrayList();
b.add(24);
b.add(46);
b.add(81);
我需要创建一个函数,它将元素从 B 到 A 放入排序查询中。 (在我看来,它必须检查A和B中相同位置的元素,并将24放在10和35之间,将46放在35和51之间,最后一个是81)。 我有:
public static void merge(ArrayList a, ArrayList b)
{
a.addAll(b);
Collections.sort(a);
}
但这不是一个高效的算法(N^2)。 有没有更高效的方法?
最佳答案
来自 List.sort
的文档
This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
此实现的复杂度为 O(n lg(n))。大多数时候甚至更低,特别是当输入几乎已排序时。 Java 版本之间的复杂性可能会有所不同,但 O(n lg(n)) 相当可靠。
回到你的算法,我们可以这样说
a.addAll(b); // requires O(n)
Collections.sort(a); // requires O(n lg(n))
所以它永远不会比 O(n lg(n)) 更糟糕。
关于java - 如何对两个 ArrayList 进行排序,同时合并为一个?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51649017/