java - 如何对两个 ArrayList 进行排序，同时合并为一个？

Question

例如，我有两个 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)。有没有更高效的方法？

Answer 1

来自 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)) 更糟糕。