java - 快速排序。线程中出现异常 "main"java.lang.StackOverflowError

Question

美好的一天!我这里有一个执行快速排序的 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，现在也没有错误。问题是它停止了错误的序列。

Answer 1

您有两个问题:

• 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;    
  }