java - ArrayList 上的 MergeSort 仅适用于 ArrayList(Collection c) 而不是 ArrayList(int initialCapacity)？

Question

我正在处理排序 interval存在于 ArrayList 上及其 start属性，完整定义 interval将在示例代码中显示为私有(private)类。

我使用的实现是 MergeSort , 与 Princeton's stuff 非常相似我指的是，但问题是我发现此实现仅适用于创建辅助 ArrayList aux与 ArrayList(Collection<? extends E> c)并用 aux.set(i, intervals.get(i)); 初始化它尝试填写 aux与 interval 的订单相同原始列表中的项目

我尝试通过创建 aux 来解决这个问题与 ArrayList(int initialCapacity)并用 aux.add(intervals.get(i)) 初始化它，但失败了。而且我仍然无法弄清楚为什么这种方法不起作用？

可直接用于调试的完整代码:

public class Test {
    private class Interval {
        // Will use start property to sort
        int start;
        int end;
        Interval() { 
            start = 0; 
            end = 0; 
        }
        Interval(int s, int e) { 
            start = s; 
            end = e; 
        }
        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }
    }

    public void sortHelper(List<Interval> intervals) {
        int len = intervals.size();
        // Only this way works
        List<Interval> aux = new ArrayList<Interval>(intervals);
        // This way NOT work ?
        //List<Interval> aux = new ArrayList<Interval>(len);
        sort(intervals, aux, 0, len - 1);
    }

    public void sort(List<Interval> intervals, List<Interval> aux, int lo, int hi) {
        if(hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(intervals, aux, lo, mid);
        sort(intervals, aux, mid + 1, hi);
        mergeHelper(intervals, aux, lo, mid, hi);
    }

    public void mergeHelper(List<Interval> intervals, List<Interval> aux, int lo, int mid, int hi) {
        // Only this way works
        for(int i = lo; i <= hi; i++) {
            aux.set(i, intervals.get(i));
        }
        // Combine with List<Interval> aux = new ArrayList<Interval>(len);
        // this way NOT work ?
        //for(int i = lo; i <= hi; i++) {
        //    aux.add(intervals.get(i));
        //}
        int left = lo;
        int right = mid + 1;
        for(int k = lo; k <= hi; k++) {
            if(left > mid) {
                intervals.set(k, aux.get(right++));
            } else if(right > hi) {
                intervals.set(k, aux.get(left++));
            } else if(less(aux.get(right), aux.get(left))) {
                intervals.set(k, aux.get(right++));
            } else {
                intervals.set(k, aux.get(left++));
            }
        }
    }

    public boolean less(Interval a, Interval b) {
        return a.start - b.start < 0;
    }

    public static void main(String[] args) {
        Test m = new Test();
        Interval one = m.new Interval(1, 3);
        Interval two = m.new Interval(2, 6);
        Interval three = m.new Interval(8, 10);
        Interval four = m.new Interval(15, 18);
        List<Interval> intervals = new ArrayList<Interval>();
        // Adding order as [2,6],[1,3],[8,10],[15,18]
        intervals.add(two);
        intervals.add(one);
        intervals.add(three);
        intervals.add(four);
        m.sortHelper(intervals);
        // Expected sort result should be
        // [1,3],[2,6],[8,10],[15,18]
        for(Interval i : intervals) {
            System.out.println(i);
        }
    }    
}

谁能帮我理解为什么必须创建辅助 ArrayList aux与 ArrayList<Collection<? extends E> c>并用 aux.set(i, intervals.get(i)); 初始化它？还是我的理解走错了路？谢谢

Answer 1

感谢@maraca 和@Dukeling 的重要提示，经过一些工作，以下是我对这里问题的看法:

Q1:为什么使用 List<Interval> aux = new ArrayList<Interval>(len);与 aux.add(intervals.get(i));不工作？

A1:这里有两个主要问题，我应该承认我在以前与 array 的工作中遇到了一些习惯性的想法。实现MergeSort ，这里的影响是 (1) new ArrayList<Interval>(len)等于 new Interval[len]或不 ？ (2) aux[i] = intervals[i] (仅供说明，实际代码中不使用=)等于aux.add(intervals.get(i)) ？

对于问题(1)，这里的真实案例是使用new ArrayList<Interval>(len)将只定义 ArrayList 的初始限制大小，但没有真正的项目像空间持有人一样填充到初始化列表中，例如如果我们设置 len = 4 , 初始化列表实际上是 [] , 不是 [interval obj, interval obj, interval obj, interval obj] .假设使用 new ArrayList<Interval>(len)与 aux.set(i, intervals.get(i)) , IDE 会抛出 java.lang.IndexOutOfBoundsException: Index: 0, Size: 0 ，那是因为没有真正的对象作为初始化填充到这个列表中，并且 set 方法不能在空列表上工作。此问题的解决方案是创建 len假人数量 interval初始化时要填充列表的对象，例如 List<Interval> aux = new ArrayList<Interval>((Arrays.asList(new Interval(), new Interval(), new Interval(), new Interval()))); , 但由于我们不关心辅助列表上首先初始化的是什么，只是用作占位符并且在对象太多的情况下，上面的代码可以替换为 List<Interval> aux = new ArrayList<Interval>(intervals);这返回到我们正确的解决方案。

对于问题(2)，这里的真实案例是使用aux.add(intervals.get(i))不等于 aux[i] = intervals[i] , 至少我们应该使用 set()而不是 add() ，因为 add()将不断追加 aux , 这不是 MergeSort假设，因为MergeSort需要完全相同大小的辅助集合副本来帮助排序。仍然使用相同的示例来解释使用 add() 时发生的情况

请注意，在第 3 次合并后，aux大小增加到原始列表的两倍大小，这将在复制回原始列表时导致索引问题。但是如果我们使用 set()不会造成这种麻烦。

Q2:如果还想用add()什么是正确的方法？

A2:如@Dukeling 所述，我们需要 clear() aux在从原始列表到辅助列表的最后一轮复制之前，例如在上面的示例中发生第 3 次合并之前。

add() 的工作代码和 clear()下面:

public void mergeHelper(List<Interval> intervals, List<Interval> aux, int lo, int mid, int hi) {
    aux.clear();
    for(int i = 0; i < lo; i++) {
        aux.add(null);
    }
    for(int i = lo; i <= hi; i++) {
        aux.add(intervals.get(i));
    }
    int left = lo;
    int right = mid + 1;
    for(int k = lo; k <= hi; k++) {
        if(left > mid) {
            intervals.set(k, aux.get(right++));
        } else if(right > hi) {
            intervals.set(k, aux.get(left++));
        } else if(less(aux.get(right), aux.get(left))) {
            intervals.set(k, aux.get(right++));
        } else {
            intervals.set(k, aux.get(left++));
        }
    }
}