美好的一天!我这里有一个执行快速排序的 Java 程序。它读取一个文件,然后对其中的前 10,000 个单词进行排序。我遵循了 Thomas Cormen 在他的《算法导论》第二版中的伪代码。
import java.io.*;
import java.util.*;
public class SortingAnalysis {
public static int partition(String[] A, int p, int r) {
String x = A[r];
int i = p-1;
for (int j=p; j < r-1; j++) {
int comparison = A[j].compareTo(x);
if (comparison<=0) {
i=i+1;
A[i] = A[j];
}
}
A[i+1] = A[r];
return i+1;
}
public static void quickSort(String[] a, int p, int r) {
if (p < r) {
int q = partition(a, p, r);
quickSort(a, p, q-1);
quickSort(a, q+1, r);
}
}
public static void main(String[] args) {
final int NO_OF_WORDS = 10000;
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();
quickSort(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);
}
}
}
但是,当我运行代码时,控制台显示
线程“main”中出现异常 java.lang.StackOverflowError
在SortingAnalysis.partition和quickSort
我认为错误只是因为尺寸太大(即 10000),所以我将其减少到 100。但是,它仍然不会对文件中的前 100 个单词进行排序,而是将第 100 个单词显示 100 次。
请帮我修复代码。我是 Java 新手,需要你们的帮助。非常感谢!
编辑:我现在编辑了我的代码。即使 NO_OF_WORDS
达到 10000,现在也没有错误。问题是它停止了错误的序列。
最佳答案
您有两个问题:
partition()
中的循环应该运行到j <= r - 1
,你跳得早了。您没有交换元素。尝试以下代码:
public static int partition(String[] A, int p, int r) { String x = A[r]; int i = p - 1; for (int j = p; j <= r - 1; j++) { int comparison = A[j].compareTo(x); if (comparison <= 0) { i = i + 1; swap(A, i, j); } } swap(A, i + 1, r); return i + 1; } public static void swap(String[] a, int i, int j) { String temp = a[i]; a[i] = a[j]; a[j] = temp; }
关于java - 快速排序。线程中出现异常 "main"java.lang.StackOverflowError,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11390536/