大家好!我这里有一个程序,可以使用合并排序对文件中的 50,000 个单词进行排序。我遵循了 Thomas Cormen 在他的《算法简介》中的伪代码,当我手动“调试”它时,它似乎是正确的。但是,当我运行该程序时,它显示 Exception in thread "main"java.lang.ArrayIndexOutOfBoundsException: 2
。是的,我认为这是由于 NO_OF_WORDS
(即 50,000)较大,但即使我将其减少到 10,它仍然显示相同的错误。
import java.io.*;
import java.util.*;
public class SortingAnalysis {
public static void merge(String[] A, int p, int q, int r) {
int n1 = q-p+1;
int n2 = r-q;
String[] L = new String[n1+1];
String[] R = new String[n2+1];
for (int i=1; i<n1; i++) {
L[i] = A[p+i-1];
}
for (int j=1; j<n2; j++) {
R[j] = A[q+j];
}
L[n1+1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
R[n2+1] = "zzzzz";
int i=1;
int j=1;
for (int k=p; k<=r; k++) {
int comparison = L[i].compareTo(R[j]);
if (comparison <= 0){
A[k] = L[i];
i++;
}
else {
A[k] = R[j];
j++;
}
}
}
public static void mergeSort (String[] A, int p, int r) {
if (p<r) {
int q = (p+r)/2;
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
public static void main(String[] args) {
final int NO_OF_WORDS = 50000;
try {
Scanner file = new Scanner(new File(args[0]));
String[] words = new String[NO_OF_WORDS];
int i = 0;
while(file.hasNext() && i < NO_OF_WORDS) {
words[i] = file.next();
i++;
}
long start = System.currentTimeMillis();
mergeSort(words, 0, words.length-1);
long end = System.currentTimeMillis();
System.out.println("Sorted Words: ");
for(int j = 0; j < words.length; j++) {
System.out.println(words[j]);
}
System.out.print("Running time: " + (end - start) + "ms");
}
catch(SecurityException securityException) {
System.err.println("Error");
System.exit(1);
}
catch(FileNotFoundException fileNotFoundException) {
System.err.println("Error");
System.exit(1);
}
}
}
我认为这是因为 String[] L 和 R 的声明。或者不是。请帮我看看有什么问题。非常感谢!
编辑
Cormen 的伪代码
MERGE(A, p, q, r )
n1 ← q − p + 1
n2 ←r − q
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 to n1
do L[i ] ← A[p + i − 1]
for j ← 1 to n2
do R[ j ] ← A[q + j ]
L[n1 + 1]←∞
R[n2 + 1]←∞
i ← 1
j ← 1
for k ← p to r
do if L[i ] ≤ R[ j ]
then A[k] ← L[i ]
i ←i + 1
else A[k] ← R[ j ]
j ← j + 1
最佳答案
我不知道你的伪代码是什么,但你的实现似乎是错误的。我查看了维基百科的合并排序,发现它完全不同。
所以我不会在这里给你完整的工作算法。我只会为您提供解决 indexOutOfBounds 问题的解决方案,但您仍然需要在实现上做更多工作。
在 Java 中,当你这样做时:
String[] L = new String[5];
您声明一个字符串数组,其中可以包含 5
个字符串。
对这些字符串的访问是这样进行的:L[anIndex]
。
第一个元素位于索引 0
处。
因此,如果您有一个大小为 5
的数组,那么最后一个元素位于索引 4
处(因为我们从 0 开始)。
在您的代码中执行以下操作:
String[] L = new String[n1+1];
String[] R = new String[n2+1];
然后:
L[n1+1] = "zzzzz";
R[n2+1] = "zzzzz";
所以在这里你总是尝试访问一个不存在的索引处的字符串。
每个数组中的最后一个元素分别为 n1
和 n2
(因为数组大小为 n1+1
和 n2+1
> ).
我希望通过这个解释您能更好地理解数组在 Java 中的工作原理。现在您必须改进您的实现,因为它仍然不起作用。如果您不太理解,也许可以给我们您使用的伪代码。
编辑:
好的,我做了一些修正。
这是工作算法。我不得不更改几个索引以适应 Java“based-0 arrays”,请看一下:
import java.io.*;
import java.util.*;
public class SortingAnalysis {
public static void merge(String[] A, int p, int q, int r) {
int n1 = q-p+1;
int n2 = r-q;
if(A[p]==null || A[q]==null)return;
String[] L = new String[n1+1];
String[] R = new String[n2+1];
for (int i=0; i<n1; i++) {
L[i] = A[p+i];
}
for (int j=0; j<n2; j++) {
R[j] = A[q+j +1];
}
L[n1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
R[n2] = "zzzzz";
int i=0;
int j=0;
for (int k=p; k<=r; k++) {
int comparison = L[i].compareTo(R[j]);
if (comparison <= 0){
A[k] = L[i];
i++;
}
else {
A[k] = R[j];
j++;
}
}
}
public static void mergeSort (String[] A, int p, int r) {
if (p<r) {
int q = (p+r)/2;
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}
public static void main(String[] args) {
final int NO_OF_WORDS = 50000;
try {
Scanner file = new Scanner("bla blya blay byla ybla");
ArrayList<String> words = new ArrayList<String>();
while(file.hasNext() && words.size() < NO_OF_WORDS) {
words.add(file.next());
}
String [] wordsArray = new String[words.size()];
words.toArray(wordsArray);
long start = System.currentTimeMillis();
mergeSort(wordsArray, 0, wordsArray.length-1);
long end = System.currentTimeMillis();
System.out.println("Sorted Words: ");
for(int j = 0; j < wordsArray.length; j++) {
System.out.println(wordsArray[j]);
}
System.out.print("Running time: " + (end - start) + "ms");
}
catch(SecurityException securityException) {
System.err.println("Error");
System.exit(1);
}
}
}
请注意,如果您的文本包含的单词少于原始数组大小,我已经更改了您的 Main,现在我使用 arrayList 来避免空值。在你的解决方案中,如果你没有填充 50000 个单词,你会在数组中得到 null,然后在合并算法中得到 nullPointerException。
关于java - 归并排序。错误 - 线程 "main"java.lang.ArrayIndexOutOfBoundsException 中出现异常 : 2,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11414783/