Java - 使用字符串进行归并排序

Question

在这个程序中，我使用归并排序来对奥运奖牌进行排序。

我的代码似乎有些问题，因为有时会给我一个java.lang.ArrayIndexOutOfBoundsException错误，而有时则不会。

简单介绍一下背景：

我有一个方法来随机生成奥运国家和他们在积分榜上赢得的奖牌。它以以下形式返回包含结果的String[]数组：

CAN 1 1 1

USA 1 1 2

GBR 0 0 1

CHN 0 0 2

然而，积分榜需要按金牌、银牌和铜牌的顺序排列。所以它应该像这样：

USA 1 1 2

CAN 1 1 1

CHN 0 0 2

GBR 0 0 1

使用冒泡排序和快速排序对积分榜进行排序没有问题，但是归并排序不行。有时它可以正常工作，但更多的时候它会给我一个ArrayIndexOutOfBoundsException错误。

public static void main(String[] args) {    

  Olympic_Results score = new Olympic_Results();

  //print a return value of an array    

  String[] countries = score.OlympicResult(7); //input how many game results
  mergeSort(countries, 0, countries.length - 1);
  for (String value:countries)
  System.out.println(value);
}

public static void mergeSort(String array[], int lo, int n) {
  int low = lo;
  int high = n;
  if (low >= high) {
    return;
  }

  int middle = (low + high) / 2;
  mergeSort(array, low, middle);
  mergeSort(array, middle + 1, high);
  int end_low = middle;
  int start_high = middle + 1;
  while ((lo <= end_low) && (start_high <= high)) {
    if ((array[low].substring(4,8)).compareTo(array[high].substring(4,8)) > 0) {
      low++;
    } 

    else {
      String Temp = array[start_high];
      for (int k = start_high - 1; k >= low; k--) {
        array[k + 1] = array[k];
      }
      array[low] = Temp;
      low++;
      end_low++;
      start_high++;
    }
  }
}  

任何想法为什么这段代码没有正常工作？谢谢！

- n00b

---

堆栈跟踪指向哪一行？ - CodeChimp

一些侧面的注释：在Java中，方法和变量通常使用camelCase。类通常使用TitleCase而不使用下划线。 - Duncan Jones

你为什么要重新发明轮子？你为什么想要合并排序？最重要的不是它已经排序了吗？我会使用Array.sort()。 - Bohemian

@CodeChimp 我相信这是堆栈跟踪：主线程中的异常 "main" java.lang.ArrayIndexOutOfBoundsException: 9（每次此数字都会更改） 在 main.java 的第58行中的 mergeSort 在 main.java 的第54行中的 mergeSort 在 main.java 的第33行中的 main函数 - n00b

@Bohemian 我现在正在学习排序算法，所以我必须逐个学习每个算法。 - n00b

Answer 1

我认为你在将数组分成部分时深入得太深了：

if (low >= high) {
    return;
    }

尝试在长度为1时停止并开始修复它。

if (high - low <=1) {
    return;
    }

顺便提一下，如果长度为2，则可以直接比较值并立即返回已排序的值。

更新

你似乎添加了太多类似名称的变量，并迷失在其中 :)..

这看起来不正确：

while ((lo <= end_low) && (start_high <= high)) {

- Vitaly

Answer 2

两个主要的错误：

1. 你使用了两个变量名相似但用途不同的变量。结果是尽管lo的值从未改变（循环使用的是low变量），while循环仍然测试lo的值。

2. while内部的if语句应该比较两个已排序序列的初始项，以便选择其中之一。你的序列从low和start_high开始，所以你应该比较array[low]和array[start_high]，但你却将其与array[high]进行比较。如果array[high]的数据恰好是子区间中最小的数据，那么low的值将超过数组大小（而while条件并没有捕获它，因为它测试的是lo）。

- CiaPan