java - 快速排序算法 "StackOverFlowError"

Question

我正在实现通过 GeeksForGeeks 提供的“QuickSort”算法。我正在对 50K 随机数的输入大小进行排序，收到一条错误消息“StackOverFlowError”。这是递归调用不知道何时到达其基本情况的情况吗？崩溃发生在第 58 行。

int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low-1); // index of smaller element
    for (int j=low; j<high; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;

            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

    return i+1;
}


/* The main function that implements QuickSort()
  arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
void sort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is
          now at right place */
        int pi = partition(arr, low, high);

        // Recursively sort elements before
        // partition and after partition
        sort(arr, low, pi-1); // Line 58, on my IDE
        sort(arr, pi+1, high);
    }
}

Answer 1

Is this a case where the recursive call doesn't know when to reach its base case?

此方法适用于较小的数组。如果达不到基本情况，它根本就不起作用。所以，不。

堆栈大小即将耗尽，因为每次进入递归时都会在内存中保留数组的副本。