java - 合并排序错误的输出

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; 的简单版本，它应该可以帮助您了解正在发生的事情)。