如何在合并为一个的同时对两个 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 中相同位置的元素，并在 10 和 35 之间放置 24，在 35 和 51 之间放置 46，最后一个是 81）。我有： public static void merge(ArrayList a, ArrayList b) {     a.addAll(b);     Collections.sort(a); }但它不是一个有效的算法（N^2）。有没有更有效的方法？

Answer 1

从文档 List.sort

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

这个实现的复杂度是 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)) 更糟。

Answer 2

正如您所说，这两个列表已排序，然后有一种 O(N) 方法来合并这两个列表。

static List<Integer> merge(List<Integer> a, List<Integer> b) {

    List<Integer> merged = new ArrayList<>(a.size() + b.size());

    int ai = 0, bi = 0;

    while (ai < a.size() && bi < b.size()) {

        if (a.get(ai) < b.get(bi))

            merged.add(a.get(ai++));

        else

            merged.add(b.get(bi++));

    }

    while (ai < a.size())

        merged.add(a.get(ai++));

    while (bi < b.size())

        merged.add(b.get(bi++));

    return merged;

}