Java自然归并排序实现

Question

我也算是Java新手了。我一直在努力解决我们学校的教授向我们提出的一个问题。我应该制作一个自然的合并排序算法，每次都必须找到两个已排序的子数组并将它们合并。(这是自下而上合并排序的一个版本)。但我被困在这里是我的代码

public class NaturalMergeMine {
  private static Comparable[] aux;

  public static void sort(Comparable[] a) {
    aux = new Comparable[a.length];
    sort(a, 0, a.length - 1);
  }

  public static boolean isSorted(Comparable[] a) {
    for (int i = 1; i < a.length; i += 1) {
      if (a[i - 1].compareTo(a[i]) < 0) {
        return false;
      }
    }
    return true;
  }

  private static void sort(Comparable[] a, int lo, int hi) {
    int i = lo;
    int j = 0;
    int mid = 0;
    int az = 0;

    while (true) {
      i = 0;
      System.out.println("outter");
      while (i < a.length) {
        System.out.println("inner 1");
        if (i == a.length - 1) {
          break;
        } else if (a[i].compareTo(a[i + 1]) < 0) {
          break;
        }
        i++;
      }

      j = i + 1;

      while (j < a.length) {
        System.out.println("inner 2");
        if (j == a.length - 1) {
          break;
        } else if (a[j].compareTo(a[j + 1]) < 0) {
          break;
        }
        j++;
      }
      mid = lo + (j - lo) / 2;
      Merge(a, lo, mid, j);
      lo = 0;

      if (isSorted(a)) {
        break;
      }
    }
  }

  public static void Merge(Comparable[] a, int lo, int mid, int hi) {
    int i = lo;
    int j = mid + 1;

    for (int k = lo; k <= hi; k++) {
      aux[k] = a[k];
    }

    for (int k = lo; k <= hi; k++) {
      if (i > mid) {
        a[k] = aux[j++];
      } else if (j > hi) {
        a[k] = aux[i++];
      } else if (aux[i].compareTo(aux[j]) < 0) {
        a[k] = aux[j++];
      } else {
        a[k] = aux[i++];
      }
    }
  }

  public static void show(Comparable[] a) {
    for (int i = 0; i < a.length; i++) {
      System.out.print(a[i] + " ");
    }
  }

  public static void main(String[] args) {
    Integer[] arr = {6, 4, 5, 7, 8, 3, 2, 1};
    sort(arr);
    show(arr);
  }
}

发生的情况是它没有正确合并，并且在外循环中进入无限循环，这是因为它没有正确排序。有谁可以建议我更好的方法或者可以告诉我我在这里犯的错误。提前致谢。

Answer 1

问题出在中间计算中，我不太确定为什么要这样做，但是如果合并方法中的中间小于 i，您将无法达到故障情况，因此您将陷入发现它而不解决的情况，对于每个run 您需要选取两个数组进行排序，因此您可以将 i 插入到 merge 方法中，而不是 mid ，这样您就可以从错误开始合并。

 public class NaturalMergeMine {
private static Comparable[] aux;

 public static void sort(Comparable[] a) {
  aux = new Comparable[a.length];
  sort(a, 0, a.length - 1);
}

 public static boolean isSorted(Comparable[] a) {
   for (int i = 1; i < a.length; i += 1) {
     if (a[i - 1].compareTo(a[i]) > 0) {//changed operator to greater than
      return false;
    }
  }
  return true;
}

private static void sort(Comparable[] a, int lo, int hi) {
  int i = lo;
  int j = 0;
  int mid = 0;
  int az = 0;

  while (true) {
   i = 0;
    System.out.println("outter");
    while (i < a.length) {
     System.out.println("inner 1");
     if (i == a.length - 1) {
       break;
      } else if (a[i].compareTo(a[i + 1]) > 0) {//changed operator to greater than
       break;
      }
      i++;
    }

    j = i + 1;

    while (j < a.length) {
    System.out.println("inner 2");
    if (j == a.length - 1) {
      break;
    } else if (a[j].compareTo(a[j + 1]) > 0) {//changed operator to greater than
      break;
    }
    j++;
  }
 //      mid = lo + (j - lo) / 2;
  Merge(a, lo, i, j);
  lo = 0;

  if (isSorted(a)) {
    break;
  }
 }
}

public static void Merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo;
int j = mid + 1;

for (int k = lo; k <= hi; k++) {
  aux[k] = a[k];
}

for (int k = lo; k <= hi; k++) {
  if (i > mid) {
    a[k] = aux[j++];
  } else if (j > hi) {
    a[k] = aux[i++];
  } else if (aux[i].compareTo(aux[j]) > 0) {//changed the operator to greater than
    a[k] = aux[j++];
  } else {
    a[k] = aux[i++];
  }
 }
 }

  public static void show(Comparable[] a) {
   for (int i = 0; i < a.length; i++) {
    System.out.print(a[i] + " ");
   }
  }

 public static void main(String[] args) {
  Integer[] arr = {6, 4, 5, 7, 8, 3, 2, 1};
  sort(arr);
  show(arr);
  }
 }