如何修复 Java 和 return 函数中排序数组中的合并排序算法

Question

我在 Java 中实现合并排序算法时遇到问题：我已经完成了合并排序算法，但无法产生正确的结果。我还 return 函数中的排序列表。我该怎么做？

下面是我定义的归并排序算法。

合并排序方法：

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

合并排序函数：

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

I couldn't get a return value as a list from merge function

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

时用作参数的变量

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

例如，如果您在名为 "list" 的 ArrayList 中有您的人员，您正在对 "list".

进行排序

    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 参数 - 就像您为函数提供输入并通过此参数接收其输出一样。

正如评论中指出的那样，代码还存在其他问题。我怀疑这里有一个错误（<= 而不是 <）

(helperRight <= high)

另一个是您在就地合并排序中使用了临时列表。

这里可以找到一个工作示例： How to sort in-place using the merge sort algorithm?

Answer 2

这是我的答案

我修改了代码

 while(helperLeft < middle && helperRight < high) {

至

 while(helperLeft <= middle && helperRight <= high) {

Answer 3

不需要return排序后的数组：数组就地排序

但是请注意这些问题：

辅助数组的初始大小应等于要排序的数组的大小。这避免了 helper.add(i, list.get(i)); 使插入额外元素在辅助数组中间的问题。这是非常低效的：它需要 O(n*log(n)) 额外的 space 而不是 O(n) 和时间复杂度为O(nnlog(n))，比插入排序差

您将使用
分配辅助数组
```
  ArrayList<Person> helper = new ArrayList<Person>(personList);
```
并且您将使用 helper.set(i, list.get(i)).
保存数组元素

merge 中的 for 循环应该迭代到并包括上限：

  while (helperLeft <= middle && helperRight <= high)

包含上限的约定令人困惑且容易出错，排除上限要简单得多，因为它不需要 -1 / +1 调整。

这是修改后的版本：

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

private static void mergeSort(ArrayList<Person> list, 
                              ArrayList<Person> helper, 
                              int low, 
                              int high, 
                              Comparator<Person> compTr) {
    if (high - low >= 2) {
        int middle = low + (high - low) / 2;
        mergeSort(list, helper, low, middle, compTr); //sort left half
        mergeSort(list, helper, middle, 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) {

    for (int i = low; i < high; i++) {
        helper.set(i, list.get(i));
    }

    int helperLeft = low;
    int helperRight = middle;
    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
    while (helperLeft < middle) {
        list.set(current, helper.get(helperLeft));
        helperLeft++;
        current++;
    }
}

如何修复 Java 和 return 函数中排序数组中的合并排序算法

How can I fix the merge sort algorithm in Java and return sorted array from function

java

sorting

mergesort