快速排序 java.lang.StackOverflowError

Question

我正在尝试计算快速排序算法在三种情况下的执行时间 "Mid pivot, first pivot, random pivot" 数组已经排序。

mid pivot 和 random 在任何大小下都可以正常工作，但如果大小大于 25000，第一个 pivot 情况会产生 Whosebug。

代码如下：

static void q_sort( int left, int right)
{

int pivot;
int l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = array[left];
  while (left < right)
  {
    while ((array[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      array[left] = array[right];
      left++;
    }
    while ((array[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      array[right] = array[left];
      right--;
    }
  }
  array[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(left,(int) pivot-1);
  if (right > pivot)
    q_sort( (int)pivot+1, right);
}

调用代码如下：

double startTime1 = System.currentTimeMillis();
q_sort(0,size -1);
double stopTime1 = System.currentTimeMillis();
double elapsedTime1 = stopTime1 - startTime1;      
System.out.println(elapsedTime1);

Answer 1

你没有说明数组是如何生成的，但我怀疑它已经排序了。

问题如下：如果对已排序的数组进行快速排序，第一个主元会导致以下递归：0..24999、1..24999、2..24999、3..24999、4.. 24999 占用大量堆栈 space 并导致堆栈溢出。这是因为数组是0..24999，pivot是0，那么第二个分区就会变成1..24999.

您应该消除其中一个尾调用。消除哪个尾调用取决于哪个分区较小。您希望递归处理尽可能少的数据。其中一个递归被简单地替换为循环。 Quicksort and tail recursive optimization

已经解释了这个尾递归消除

无论如何，我建议使用现有的快速排序算法而不是自己编写代码，除非这是一道作业题。

快速排序 java.lang.StackOverflowError

QuickSort java.lang.StackOverflowError

java

stack-overflow