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

标签： javastack-overflowquicksort

Answer 1

我没有看到你的代码有任何问题。它必须是堆栈大小，尝试使用增加它

将其设置为 2 MB。

java -Xss2m QuickSort

如果您在 IDE 上，请在 IntelliJ/Ecllipse 的运行配置中更改/添加它。