归并排序错误输出

Question

我在Java中合并排序代码有两个问题。

1. 当我输入数组[3,4,2,1,0,6,8]时，我得到的输出[0,1,2,3,4,6,0]，这显然是错误的。

2. 我怀疑我写代码的方式并不是最优的。如果你能找到任何改进，请让我知道。我知道网络上已经有大量的归并排序算法，但我特别要问的是我编写代码的方式。谢谢!

   import java.util.Arrays;
   public class Main {
       static int[] mergeSort(int[] arr) {
           if (arr == null)
               return null;
           if (arr.length <= 1)
               return arr;
           int length = arr.length;
           int mid = arr.length / 2;
           int[] left = Arrays.copyOfRange(arr, 0, mid);
           int[] right = Arrays.copyOfRange(arr, mid, length);
           int[] sortedLeft = mergeSort(left);
           int[] sortedRight = mergeSort(right);
           int leftSmallestIndex = 0;
           int rightSmallestIndex = 0;
           int leftLength = left.length;
           int rightLength = right.length;
           int[] sortedArr = new int[length];
           outer: for (int i = 0; i < length; i++) {
               if (leftSmallestIndex >= leftLength) {
                   while (rightSmallestIndex < rightLength) {
                       sortedArr[i] = sortedRight[rightSmallestIndex];
                       rightSmallestIndex++;
                       break outer;
                   }
               }
               if (rightSmallestIndex >= rightLength) {
                   while (leftSmallestIndex < leftLength) {
                       sortedArr[i] = sortedLeft[leftSmallestIndex];
                       leftSmallestIndex++;
                       break outer;
                   }
               }
               if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) {
                   sortedArr[i] = sortedLeft[leftSmallestIndex];
                   leftSmallestIndex++;
               }
               else {
                   sortedArr[i] = sortedRight[rightSmallestIndex];
                   rightSmallestIndex++;
               }
           }
           return sortedArr;
       }
       public static void main(String[] args) {
       // write your code here
           int[] a = new int[] {3,4,2,1,0,6,8};
           System.out.println(Arrays.toString(mergeSort(a)));
       }
   }
   

Answer 1

您的语句break outer;实际上导致控制退出for循环，它不会继续for循环(我猜您正在尝试继续for循环，使用该break outer;语句)。

这导致循环只更新sortedRight或sortedLeft中的一个剩余元素以进入排序数组，而其他元素则错过，这导致循环结束时出现0。

你实际上不需要这样做，你可以循环到- leftSmallestIndex < leftLength && rightSmallestIndex < rightLength，然后执行你在for循环中定义的while循环，在它外面。

,

import java.util.*;
import java.math.*;
class a {
    static int[] mergeSort(int[] arr) {
        if (arr == null)
            return null;
        if (arr.length <= 1)
            return arr;
        int length = arr.length;
        int mid = length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, length);
        int[] sortedLeft = mergeSort(left);
        int[] sortedRight = mergeSort(right);
        int leftSmallestIndex = 0;
        int rightSmallestIndex = 0;
        int leftLength = left.length;
        int rightLength = right.length;
        int[] sortedArr = new int[length];
        int i = 0;
        for (; leftSmallestIndex < leftLength && rightSmallestIndex < rightLength;i++) {
            if (sortedLeft[leftSmallestIndex] < sortedRight[rightSmallestIndex]) {
                sortedArr[i] = sortedLeft[leftSmallestIndex];
                leftSmallestIndex++;
            }
            else {
                sortedArr[i] = sortedRight[rightSmallestIndex];
                rightSmallestIndex++;
            }
        }
        while (rightSmallestIndex < rightLength) {
            sortedArr[i] = sortedRight[rightSmallestIndex];
            rightSmallestIndex++;
            i++;
        }
        while (leftSmallestIndex < leftLength) {
           sortedArr[i] = sortedLeft[leftSmallestIndex];
           leftSmallestIndex++;
           i++;
        }
        return sortedArr;
    }
    public static void main(String[] args) {
     int[] a = new int[] {3,4,2,1,0,6,8};
        System.out.println(Arrays.toString(mergeSort(a)));
        outer : for(int i = 0;i < 10 ; i++) {
        while(true) {
            System.out.println(i);
            break outer;
        }
    }
    }
}

最后，我添加了示例(您正在尝试使用break outer;的简单版本，它应该有助于您了解正在发生的事情)。

Answer 2

你的问题在while循环:

while (rightSmallestIndex < rightLength) {
                sortedArr[i] = sortedRight[rightSmallestIndex];
                rightSmallestIndex++;
                break outer;
            }

永远不会循环，因为break语句在while语句内。同时，你不能在while语句中增加i所以即使循环，它也会覆盖当前索引处的值而不是填充数组的其余部分

将它们改为

       if (leftSmallestIndex >= leftLength) {
            while (rightSmallestIndex < rightLength) {
                sortedArr[i] = sortedRight[rightSmallestIndex];
                rightSmallestIndex++;
                i++;
            }
                break outer;
        }
        if (rightSmallestIndex >= rightLength) {
            while (leftSmallestIndex < leftLength) {
                sortedArr[i] = sortedLeft[leftSmallestIndex];
                i++;
                leftSmallestIndex++;
            }
                break outer;
        }
      ..rest is the same

应该会给你正确的结果

至于改进……

1. 不要使用标签和break LABEL语句，这很容易混淆，可能更清楚的是将这些部分重构成自己的方法，并使用fillInRemainingArray()

这样的意图揭示方法名称。

2. 我不认为你需要复制数组，你应该能够在只有一个数组的地方合并