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

Question

我从另一个应该有效的 Whosebug 问题中实现了这个算法：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。因此在 first if 内部，两个检查都为真，并且将一个项目分配给第一个元素，并且 l 或 r 增加。现在第一个 if 将不再触发，因为 l 或 r 为 1。因此数组的第 2 个元素未更改。

所以我会做以下检查：

        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的最小值。如果两个元素都不是左边的，我们检查元素左边的位置并取左边或右边的元素。

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

I am having an issue with implementing a Mergesort algorithm for String arrays in a separate Class

java

array-merge