java - Quicksort (Java) 在 array.length > 60k 处导致 StackOverFlow

Question

我的代码正常工作(据我所知)直到我的输入数组大小 (a.length) 大约为 62,000，此时我一直收到 StackOverFlowError。我之前对 quicksort 使用了 2 个递归调用(小于和大于基准 q)，然后我切换到尾递归。如您所见，我选择了枢轴作为数组末尾的值。我知道这不是选择枢轴的最佳方式，但我仍然不应该看到数组大小这么小的 StackOverFlowError，对吗？是什么原因造成的？提前致谢!这是我的代码:

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

Answer 1

最坏情况下的输入(排序顺序)使得快速排序为 Θ(n^2)。 分区总是将单个元素放在分区的一侧(Cormen 等人)。通过随机排序(选择一个随机基准)没有特定的输入会引发其最坏情况的行为。

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();
     }

}