java - 我在单独的类中为字符串数组实现合并排序算法时遇到问题

Question

我从另一个 Stackoverflow 问题中实现了这个算法，该问题应该有效:Sorting (names) using Merge Sort

到目前为止，这是我得到的输出:Apfel Apfel Banane 柠檬香蕉

public class TestMergesort {
    public static void main(String[] args) {
        String[] fruechte = new String[]{"Orange","Apfel","Zitrone","Limone","Banane"};
        Mergesorttwo.mergeSort(fruechte);

        for (int i = 0;i<fruechte.length;i++)
            System.out.print(fruechte[i]+"\t");
    }
}

public class Mergesorttwo {
    public static void mergeSort(String[] arr) {
        if (arr.length > 1) {
            String[] left = new String[arr.length / 2];
            String[] right = new String[arr.length - arr.length / 2];

            for (int i = 0; i < left.length; i++) {
                left[i] = arr[i];
            }
            for (int i = 0; i < right.length; i++) {
                right[i] = arr[i + arr.length / 2];
            }

            mergeSort(left);
            mergeSort(right);
            merge(arr, left, right);

        }
    }

        public static void merge(String[] arr, String[] left, String[] right){
            int l = 0;
            int r = 0;
            for (int i = 0; i < arr.length; i++) {
                if (l < right.length && r < left.length) {
                    if (r>= right.length || (l < left.length &&left[l].compareTo(right[r]) <= 0)) arr[i] = left[l++];
                    else arr[i] = right[r++];;
                }
            }
        }
    }

Answer 1

只需检查您的合并算法。这不可能是正确的。想象一下，它是在一个有 2 个元素的数组上调用的，所以 left 和 right 都是只有 1 个元素的数组。l 和 r 为 0。因此，在第一个 if 内，两个检查都为 true，并且将一个项目分配给第一个元素，并且 l 或 r 增加。现在第一个 if 将不再被触发，因为 l 或 r 为 1。因此数组的第二个元素不变。

所以我会做以下检查:

        public static void merge(String[] arr, String[] left, String[] right){
        int l = 0;
        int r = 0;
        for (int i = 0; i < arr.length; i++) {
            if (l < left.length && r < right.length) {
                if (left[l].compareTo(right[r]) <= 0)
                    arr[i] = left[l++];
                else
                    arr[i] = right[r++];;
            } else if (l < left.length) {
                arr[i] = left[l++];
            } else {
                arr[i] = right[r++];
            }
        }
    }

所以检查主要是:left和right中的元素是否为left？然后取left和right的最小值。如果两个元素都没有剩下，我们检查元素在哪里，并取左侧或右侧的元素。