Java 字符串合并排序仅适用于最多四个元素的数组列表

Question

我正在尝试使用合并排序来按字母顺序对从命令提示符输入的单词列表进行排序。当我对大小为 4 个单词的数组列表进行排序时，它会起作用，但是当我尝试使用五个或更多单词时:它会以错误的顺序或按照原来的顺序返回数组。

当我调试它时，我意识到它一直正确排序，直到合并最后两半。前任。如果它是大小为 7 的数组列表，它会正确排序位置 0 - 4 中的单词和位置 5 - 7 中的单词，但以错误的顺序合并它们。

因此，我认为错误出在 mergeSort 函数中，因为合并函数正在工作，考虑到它能够正确对较小的数组进行排序。但是，我不明白那里怎么会出现错误，因为它只是将数组分成两半并调用其他函数。

将它与我在网上和此处找到的其他合并排序函数进行比较，代码非常相似，因此我很难发现我的错误。

从cmd输入单词并调用mergesort如下:

    public static void main(String[] args) {
        List<String> List = new ArrayList<String>();
        Scanner input = new Scanner(System.in); 
        while(input.hasNextLine()){ 
            String word = input.nextLine().trim();
            if (word.equals("")) break;
            List.add(word); 
        }
        input.close();
        System.out.println("unsorted: " + ListA);
        mergeSort(List, 0, List.size()-1);
        System.out.println("sorted: " + ListA);
    }

我的 mergeSort 函数和合并函数是:

    public static void mergeSort(List<String> wordArray, int lower, int upper) {
        if ((upper-lower) >= 1 ) {//if arraylist size is greater than 1
            int halfPt = (upper + lower)/2; //dividing the arraylist
            int s1 = lower;
            int f1 = halfPt;
            int s2 = halfPt +1;
            int f2 = upper;
            mergeSort(wordArray, s1, f1); //mergesort on first half
            mergeSort(wordArray, s2, f2); //mergesort on second half
            merge(wordArray, s1, f1, s2, f2); //merge first and second half
        }
    }

    public static void merge(List<String> wordArray, int s1, int f1, int s2, int f2) {
        List<String> finalArray = new ArrayList<String>();
        while (s1<=f1 && s2<=f2) { //alphabetically sorting both half arrays
            if(wordArray.get(s1).compareTo(wordArray.get(s2))<0) {//placing smallest element first
                finalArray.add(wordArray.get(s1));
                s1++;
            } else {
                finalArray.add(wordArray.get(s2));
                s2++;
            }
        }
        //add leftovers in half-arraylists
        while (s1 <= f1) {
            finalArray.add(wordArray.get(s1));
            s1++;
        }   
        while (s2 <= f2) {
            finalArray.add(wordArray.get(s2));
            s2++;
        }
        for (int i = 0; i < wordArray.size(); i++) { //copy sorted array into original array
            if (wordArray.size()!=finalArray.size()) break;
            wordArray.set(i, finalArray.get(i));
        }
    }

我哪里可能出错了？非常感谢任何帮助，并提前感谢您!

Answer 1

您的问题在于 merge 方法的最后一个 for 循环。

for (int i = 0; i < wordArray.size(); i++) { //copy sorted array into original array
      // This if is source of problem, size of your final array will only match that of
      // wordArray in the last call to merge.
      // In all the other invocations it will not match, hence the copying never occurs in those cases
      if (wordArray.size()!=finalArray.size()) break;
      wordArray.set(i, finalArray.get(i));
}

要修复此问题，请修改最后一个 for 循环，如下所示。

// In the beggining of merge method store values of s1 and f2
// so that we know the start and end index of the merge operation
int start = s1;
int end = f2;

// Now modify the last for loop as
for(int i=0; i<finalArray.size() && start <= end; i++, start++){
   wordArray.set(start, finalArray.get(i));
}