java - 合并两个数组列表的最快方法

Question

我正在尝试按排序顺序合并两个列表，我想知道合并它们的最快方法是什么。目前，我的算法基本上是(忽略语法):

merge(a, b){
    newlist = new Arraylist()
    while(!a.isEmpty() && !b.isEmpty()){
        if(a.get(0) > b.get(0))
            newlist.add(a.remove(0))
        else 
            newlist.add(b.remove(0))
    }
    newlist.addAll(a)
    newlist.addAll(b)
    return newlist
}

有没有更快的方法来进行这种合并？我正在尝试尽可能减少我的运行时间，因为这个函数被调用了数千次非常大的 ArrayLists。

Answer 1

从 ArrayList 的前面移除具有 O(N) 时间复杂度，因为所有其他元素都需要移动。相反，您可以存储两个 List 的当前索引，并每次比较索引处的元素以合并 O(N) 总体时间复杂度(利用两个 List 都已经排序的事实)。请注意，这通常是合并排序中使用的方法。此外，如果您知道最后的大小，最好将初始容量传递给 ArrayList 构造函数。

public static List<Integer> merge(List<Integer> a, List<Integer> b){
    List<Integer> result = new ArrayList<>(a.size() + b.size());
    int left = 0, right = 0;
    while(left < a.size() || right < b.size()){
        if(right == b.size() || left < a.size() && a.get(left) <= b.get(right)){
            result.add(a.get(left++));
        } else {
            result.add(b.get(right++));
        }
    }
    return result;
}