如何从Java的Merge Sort中的merge方法中以列表形式返回结果

Question

我有一个关于从Java中的合并功能返回列表的问题。

我已经完成了合并排序算法，但无法从合并函数获得返回值作为列表。

这是我在下面定义的合并排序算法。

mergeSort方法

public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr) {
            ArrayList<Person> helper = new ArrayList<Person>();
            mergeSort(personList, helper, 0, personList.size() - 1, compTr);
}

mergeSort函数

private static void mergeSort(ArrayList<Person> list, 
                                      ArrayList<Person> helper, 
                                      int low, 
                                      int high, 
                                      Comparator<Person> compTr) {
            if(low < high) {
                int middle = (low+high)/2;
                mergeSort(list, helper, low, middle, compTr); //sort left half
                mergeSort(list, helper, middle+1, high , compTr); //sort right half
                merge(list, helper, low, middle, high , compTr); // merge
            }
        }

合并算法

private static void merge(ArrayList<Person> list, 
                                               ArrayList<Person> helper, 
                                               int low, 
                                               int middle, 
                                               int high , 
                                               Comparator<Person> compTr) {
            //This loop throws Exception
            for(int i=low; i< high + 1; i++) {
                helper.add(i, list.get(i));
            }

            int helperLeft = low;
            int helperRight = middle + 1;
            int current = low;

            while(helperLeft < middle && helperRight < high) {
                if(isGreaterThan(helper.get(helperLeft), helper.get(helperRight), compTr)) {
                    list.set(current, helper.get(helperLeft));
                    helperLeft++;
                } else {
                    list.set(current, helper.get(helperRight));
                    helperRight++;
                }
                current++;
            }

            //Copy remaining elements
            int remaining = middle - helperLeft;
            for(int j=0; j <= remaining; j++) {
                list.set(current+j, helper.get(helperLeft+j));
            }

          // RETURN LIST(list) _-> TO DO 
        }

实施比较器功能

public static boolean isGreaterThan(Person helperLeft,Person helperRight,Comparator<Person> compTr) {
            return greaterThan(compTr, helperLeft, helperRight);
 }

 private static boolean greaterThan(Comparator comp, Person x, Person y) {
    return comp.compare(x, y) > 0;
 }

我该怎么办？

Answer 1

我无法从合并功能获得返回值作为列表

如果我对您的理解正确，您正在寻找一种返回排序列表的方法。但是在您的实现中，您正在尝试对原始列表进行排序。这意味着您在调用合并功能时已经有一个指向结果排序列表的变量：在调用

时用作参数的变量

public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr)

例如，如果您的人员在一个名为“列表”的ArrayList中，则您正在对该“列表”进行排序。

    ArrayList<Person> list = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        list.add(new Person());
    }
    System.out.println(list);
    mergeSort(list, Comparator.<Person>naturalOrder());
    System.out.println(list);

有关更多信息，您所使用的称为inout参数-如在函数中输入您的内容并通过该参数接收其输出。