java - 如何为 ArrayList 实现归并排序？

Question

我有 ArrayList 的 mergesort java 代码，但它没有正确排序 ArrayList。但我没有发现错误。

代码是:

public void mergeSort(ArrayList<Integer> list, int beg, int fin) {
    if (beg < fin) {
        int mid= (beg + fin) / 2;
        mergeSort(list, beg, mid);
        mergeSort(list, mid + 1, fin);
        Merge(list, beg, mid, fin);
    }
}


public void Merge(ArrayList<Integer> list, int beg, int mid, int fin) {
    ArrayList<Integer> left = new ArrayList<>(list.subList(beg, mid));
    ArrayList<Integer> right = new ArrayList<>(list.subList(mid, fin));
    
    int i = 0;
    int j = 0;
    int k = beg;
    
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(i)) {
            list.set(k, left.get(i));
            i++;
        } else {
            list.set(k, right.get(j));
            j++;
        }
        k++;
    }
    
    while (i < left.size()) {
        list.set(k, left.get(i));
        i++;
        k++;
    }

    while (j < right.size()) {
        try {
            list.set(k, right.get(j));
            j++;
            k++;
        }
    }
}

当我从其他类(class)调用它时...

jpanel4.mergeSort(jpanel4.lista, 0, jpanel4.lista.size() - 1);

(合并在 jpanel4 类中)。

我将数组的合并排序代码转换为该代码，因为它可以与我拥有的其他代码一起正常工作。

谢谢。

Answer 1

让我们使用半闭区间 [beg, fin) 因为这种方法被用于大多数 Java、C++ 等的内置方法。

那么调用应该是:

jpanel4.mergeSort(jpanel4.lista, 0, jpanel4.lista.size());
//                                                      ^ no -1

现在让我们看看如何划分给定的区间。让我们使用 [beg, mid) 和 [mid, end) 间隔。如果 l >= r，则区间为空。

但如果给定区间的长度为 1，它将被分成长度为 0 和 1 的两个区间，并且 mergeSort 将被递归调用以对完全相同的区间进行排序。您不需要对单元素数组进行排序，它已经排序了。

所以 mergeSort 应该是这样的:

    public void mergeSort(ArrayList<Integer> list, int beg, int fin){
        if(beg + 1 < fin){
        //     ^^^ added +1 to ensure we sort only intervals with length >= 2
            int mid = (beg+fin)/2;
            mergeSort(list, beg, mid);
            mergeSort(list, mid, fin);
            //                 ^ no +1
            Merge(list, beg, mid, fin);
        }
    }

Merge 也有错误:

    public void Merge(ArrayList<Integer> list, int beg, int mid, int fin){

        // ...

        while (i < left.size() && j < right.size()) {
            if (left.get(i) <= right.get(j)) {
            //                           ^ you should compare left[i] and right[j]
                list.set(k, left.get(i));
                i++;
                
            } else {
                list.set(k, right.get(j));
                j++;
            }
            
            k++;
        }

        // ...

     }