如何为 ArrayList 实现归并排序？

Question

我有 ArrayList 的 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 class）。

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

谢谢。

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++;
        }

        // ...

     }

Answer 2

主要错误是一个简单的错字：if (left.get(i) <= right.get(i)) { 应该是：

    if (left.get(i) <= right.get(j)) {

数组索引值和边界也有问题：应该包括 beg 和 mid 索引，而应该排除 fin（结尾？）。这也消除了 +1 / -1 调整的需要。

int mid = (beg + fin) / 2; 中有一个更微妙的错误：对于非常大的数组，计算此总和可能会溢出。最好写成：

    int mid = beg + (fin - beg) / 2;

纠正这些问题后，您可以删除 try 块。

这是修改后的版本：

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

public void Merge(ArrayList<Integer> list, int beg, int mid, int fin) {
    ArrayList<Integer> left = new ArrayList<Integer>(list.subList(beg, mid));
    ArrayList<Integer> right = new ArrayList<Integer>(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(j)) {
            list.set(k, left.get(i++));
        } else {
            list.set(k, right.get(j++));
        }
        k++;
    }
    
    while (i < left.size()) {
        list.set(k, left.get(i++));
        k++;
    }

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

您可以使用 jpanel4.mergeSort(jpanel4.lista, 0, jpanel4.lista.size());

调用此方法

注意 Merge 可以简化，因为最后一个循环是多余的，right 的剩余元素已经在 list 的末尾。事实上，没有必要保存右边部分的元素，因为它们总是被复制到较低或相等的索引值。

这是一个简化版本：

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

Answer 3

Check my version of merge sort using array list hope it help you    : https://github.com/murari99732/solutionleetcode-adventofcode/blob/master/PracticeAlgo/src/LeetCode/MergeSort.java

public static void mergeSort(List<Integer> arr, int start, int end) {
        if (start != end) {
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    private static void merge(List<Integer> arr, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int k = 0;

        int[] temp = new int[end - start + 1];

        while ((i <= mid) && (j <= end)) {
            if (arr.get(i) < arr.get(j))
                temp[k++] = arr.get(i++);
            else
                temp[k++] = arr.get(j++);
        }

        while (i <= mid) {
            temp[k++] = arr.get(i++);
        }

        while (j <= end) {
            temp[k++] = arr.get(j++);
        }

        for (i = start; i <= end; i++) {
            arr.remove(i);
            int e = temp[i - start];
            arr.add(i, e);
        }
    }

如何为 ArrayList 实现归并排序？

How can I implement mergesort for a ArrayList?

java

sorting

algorithm

mergesort

arraylist