java - 如何通过快速排序算法实现避免堆栈溢出错误

Question

//如果像我一样，目标是在其他代码中使用该算法(而不是对算法本身进行编码)，Arrays.sort ( Documentation here) 就可以完成这项工作!//

我一直收到这个错误:

Exception in thread "main" java.lang.StackOverflowError
at language.LanguageDetection.sort(LanguageDetection.java:140)
at language.LanguageDetection.sort(LanguageDetection.java:141)
at language.LanguageDetection.sort(LanguageDetection.java:141)

这一行:

at language.LanguageDetection.sort(LanguageDetection.java:141)

填充控制台输出的其余部分。

我是 Java 的初学者，我正在尝试实现一种快速排序算法，以便对包含所有字典单词的文本文件进行排序，这样我就可以快速搜索它。

我真的不知道这是不是要走的路，或者是否有更适合这个问题的排序算法，但这里是代码:

public static void sort(String[] unsorted, int startIndex, int endIndex)
{
 if(endIndex - startIndex <= 0) return; //Ends the recursion when unsorted array is of size 1
 String temp;

 char pivot = unsorted[endIndex].charAt(0);

 int j = startIndex;
 for(int i = startIndex; i < endIndex; i++)
 {
  if(unsorted[i].charAt(0) < pivot)
  {
   temp = unsorted[j];
   unsorted[j] = unsorted[i];
   unsorted[i] = temp;
   j++;
  }
 }
 temp = unsorted[j];
 unsorted[j] = unsorted[endIndex];
 unsorted[endIndex] = temp;

 sort(unsorted, startIndex, j - 1);
 sort(unsorted, j + 1, endIndex);

}

我不想得到代码的所有更正版本，只是一些关于我编码错误的答案以及是否有更好的方法。

提前致谢。

Answer 1

简单的解决方案:

Quicksort 将输入数组划分为两个子数组，然后对子数组进行排序。要对子数组进行排序，首先要递归对较小的数组进行排序，然后循环对较大的数组进行排序。

由于每个递归调用 <= 其调用者大小的一半，因此递归深度限制为 log(N)。