3

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

我的代码似乎有点不对劲，因为有时它会给我一个 java.lang.ArrayIndexOutOfBoundsException ，有时它不会。

对于一些背景说明：

我有一种方法可以随机生成奥运国家和他们在记分牌中获得的奖牌。以以下形式返回结果的 String[] 数组：

可以 1 1 1

美国 1 1 2

英国 0 0 1

中国 0 0 2

然而，记分牌需要按金、银、铜牌的递减顺序排列。所以它必须是这样的：

美国 1 1 2

可以 1 1 1

中国 0 0 2

英国 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++;
    }
  }
}

知道为什么这段代码不能正常工作吗？谢谢！

4

2 回答 2

0

两大错误：

  1. 您保留两个名称相似但用途不同的变量。结果，while循环测试该lo值，尽管从未更改它（循环与low变量一起使用）。

  2. 内部应该比较两个排序后的系列的初始项目以选择其中一个if。while您的系列从lowand开始start_high，因此您应该与 进行比较array[low]，array[start_high]但您将其与 进行比较array[high]。如果array[high]数据恰好是正在排序的子区间中的最小值，则该low值将增加超过数组大小（并且while条件不会捕获它，因为它会进行测试lo）。

于 2014-03-28T09:30:53.190 回答
0

我认为您在将数组划分为多个部分时过于深入：

if (low >= high) {
    return;
    }

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

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

顺便说一句，如果长度为 2，那么您可以比较适当的值并立即返回它们已经排序。

UPD

您似乎添加了太多具有相似名称的变量并迷失在其中:)..

这看起来不正确：

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

于 2013-04-09T11:47:00.037 回答