0

再会！我这里有一个执行快速排序的 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);
        }
    }
}

但是，当我运行代码时，控制台说
Exception in thread "main" java.lang.StackOverflowError at SortingAnalysis.partition and quickSort

我认为错误只是因为大尺寸（即 10000），所以我将其减少到 100。但是，它仍然不会对文件中的前 100 个单词进行排序，而是将第 100 个单词显示 100 次。
请帮我修复代码。我是 Java 新手，需要你们的帮助。非常感谢你！

编辑：我现在编辑了我的代码。即使达到10000，它现在也没有错误 NO_OF_WORDS 。问题是它停止了错误的序列。

4

2 回答 2

2

你有两个问题：

  • 循环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;    
}
于 2012-07-09T07:57:03.623 回答
1

查看维基百科的快速排序算法，分区算法如下：

// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
//   number of elements in subarray = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
  'pivotValue' := array['pivotIndex']
  swap array['pivotIndex'] and array['right']  // Move pivot to end
  'storeIndex' := 'left'
  for 'i' from 'left' to 'right' - 1  // left ≤ i < right
      if array['i'] < 'pivotValue'
          swap array['i'] and array['storeIndex']
          'storeIndex' := 'storeIndex' + 1
  swap array['storeIndex'] and array['right']  // Move pivot to its final place
  return 'storeIndex'

在您的方法中，您不使用该pivotIndex值，而是基于pivotValue索引right。您需要将此参数添加到您的方法中。

按照 wiki 算法，它应该是这样的：

public static int partition(String[] A, int p, int r, int pivotIdx) {
    String x = A[pivotIdx];
    String tmp = A[pivotIdx];
    A[pivotIdx] = A[r];
    A[r]=tmp;
    int i = p;
    for (int j=p; j < r; j++) {
        int comparison = A[j].compareTo(x);
        if (comparison<=0) {
            tmp=A[i];
            A[i] = A[j];
            A[j]=tmp;
            i++;
        }       
    }
    tmp=A[i];
    A[i] = A[r];
    A[r]=tmp;
    return i;
}
于 2012-07-09T07:54:40.590 回答