使用 ArrayList 时合并排序的问题

Question

我一直在努力了解如何在不使用多个临时数组的情况下进行正确的合并排序，而只是使用一个临时数组。但是，当我测试它时，它排序不正确，并且超出了数组边界。我已经尝试使用各种不同的编码源和想法来多次弄清楚如何做到这一点，但我没有任何运气。这是我的代码：

import java.util.ArrayList;

public class ArrayListSorter{ 
    
    public static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list) {

        ArrayList<T> tempList = generateArrayList(list.size());
        mergesort(list, tempList, 0, list.size()-1);
        }

    
    //helper method for merge sort driver
    public static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list, ArrayList<T> tempList, int start, int end) {
        if(list.get(start + 1).compareTo(list.get(end)) < 0) {
            int mid = (start + end)/2;
            
            mergesort(list, tempList, start, mid);      
            mergesort(list, tempList, mid, end);
            merge(list, tempList, start, mid, end);     
            }
        }
    //For merging two sub arrays together
    private static <T extends Comparable<? super T>> void merge(ArrayList<T> list, ArrayList<T> tempList, int left, int mid, int right) {
        
            int i = left;
            int j = mid;
            int k = left;
            
            while(i <= mid && j <= right)
            {
                if (list.get(i).compareTo(list.get(j)) <= 0)
                {
                    tempList.set(k, list.get(i));
                    i++;
                } else {
                    tempList.set(k, list.get(j));
                    j++;
                }
                k++;
            }
            
            while (i <= mid) {
                tempList.set(k, list.get(i));
                i++;
                k++;
            }
            
            while (j <= right)
            {
                tempList.set(k, list.get(j));
                j++;
                k++;
            }
            int l = 0;
            while(l < list.size())
            {
                list.set(l, tempList.get(i));
                l++;
            }
    }
private static <T> ArrayList<T> generateArrayList(int n){

    ArrayList<T> list = new ArrayList<T>();
    for(int i = 0; i < n; i++) {
        list.add(null);
    }
    return list;
}
}

我想使用单个 arrayList 并简单地维护指针位置，以便将其视为有两个数组。

Answer 1

在方法中

public static <T extends Comparable<? super T>> void mergesort(ArrayList<T> list, ArrayList<T> tempList, int start, int end) {

这条线可能有问题

list.get(start + 1).compareTo(list.get(end)) < 0

在经典实现中，这一行应该比较索引而不是列表元素

// my implementation
    private static void recursiveMergeSort(double[] array, int start, int end) {
        if ((end - start) > 1) {
            int middle = (start + end) / 2;
            recursiveMergeSort(array, start, middle);
            recursiveMergeSort(array, middle, end);
            int left_len = middle - start;
            int right_len = end - middle;
            var left_cache = new double[left_len];
            var right_cache = new double[right_len];
            merge(array, start, left_cache, right_cache);
        }
    }

你遇到的另一个问题是索引包含，你有

mergesort(list, tempList, 0, list.size()-1);

索引是左右包含的，然后看你的代码

mergesort(list, tempList, start, mid);      
mergesort(list, tempList, mid, end);
merge(list, tempList, start, mid, end);

您在“中间”有重叠。我的建议是遵循常规索引包含，即左包含右排除。
最后一个问题在下面的代码块中。完整副本将删除您的原始列表，您应该只在每次“合并”调用时复制列表的一小部分

        int l = 0;
        while(l < list.size())
        {
            list.set(l, tempList.get(i));
            l++;
        }

你的想法是正确的，避免了太多的数组初始化，我没有发现它的实现有任何问题
顺便说一句，我建议您应该使用断点来调试您的程序。在运行程序中间检查变量的状态很容易，无需打印。

使用 ArrayList 时合并排序的问题

Issues with mergesorting when using ArrayList

java

merge

mergesort

arraylist