Quicksort (Java) causes StackOverFlow at array.len

问题:

My code works properly (to my knowledge) up until my input array size (a.length) is around 62,000 at which time I consistently get a StackOverFlowError. I previously had used 2 recursive calls to quicksort (less than, and greater than the pivot q) and then I switched to tail recursion. As you can see, I'm selecting the pivot to be the value at the end of the array. I know this isn't the best way to choose a pivot, but I still shouldn't be seeing StackOverFlowErrors with an array size this small, right? What could be causing this? Thanks in advance! Here's my code:

    public static void quicksort(int[] a, int p, int r)
    {
        int q;
        while (p < r)
        {
            q = partition(a, p, r);
            quicksort(a, p, q - 1);
            p = q + 1;
        }
    }

    public static int partition(int[] a, int p, int r)
    {
        int j = p - 1;
        int x = a[r];
        for (int i = p; i < r; i++)
        {
            if (a[i] <= x)
            {
                j++;
                swap(a, i, j);
            }
        }
        j++;
        swap(a, j, r);
        return j;
    }

    private static void swap(int[] a, int i, int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

回答1:

The worst-case input (sorted order) makes quicksort Θ(n^2). Partition always puts a single element on one side of the partition (Cormen et al.). By randomizing the sort (choosing a random pivot) no particular input elicits its worst-case behavior.

import java.util.Random;

public class Quicksort
{
     private static Random rand = new Random();

     public static void quicksort(int[] arr, int left, int right)
     {
          if (left < right)
          {
               int pivot = randomizedPartition(arr, left, right);
               quicksort(arr, left, pivot);
               quicksort(arr, pivot + 1, right);
          }
     }

     private static int randomizedPartition(int[] arr, int left, int right)
     {
          int swapIndex = left + rand.nextInt(right - left) + 1;
          swap(arr, left, swapIndex);
          return partition(arr, left, right);
     }

     private static int partition(int[] arr, int left, int right)
     {
          int pivot = arr[left];
          int i = left - 1;
          int j = right + 1;
          while (true)
          {
               do
                    j--;
               while (arr[j] > pivot);

               do
                    i++;
               while (arr[i] < pivot);

               if (i < j)
                    swap(arr, i, j);
               else
                    return j;
          }
     }

     private static void swap(int[] arr, int i, int j)
     {
          int tmp = arr[i];
          arr[i] = arr[j];
          arr[j] = tmp;
     }

     // Sort 100k elements that are in reversed sorted order
     public static void main(String[] args)
     {
          int arr[] = new int[100000];
          for (int i = 0; i < arr.length; i++)
               arr[i] = arr.length - i;

          System.out.println("First 20 elements");
          System.out.print("Before sort: ");
          for (int i = 0; i < 20; i++)
               System.out.print(arr[i] + " ");
          System.out.println();

          quicksort(arr, 0, arr.length - 1);
          System.out.print("After sort: ");
          for (int i = 0; i < 20; i++)
               System.out.print(arr[i] + " ");
          System.out.println();
     }

}

回答2:

Given the right input, your implementation will recurse once for every single element of the array. 60,000 recursive calls could easily be enough to overflow the stack in Java in the default configuration.