c++ - 几乎大 n 的递归插入排序崩溃

Question

我写了一个工作正常的递归插入排序，但问题是如果我设置 n = 10000 或大约 5000 或更大，无论数组的值是什么，应用程序都会停止工作。 (例如 vector 数组(10000,0))

代码如下:

void RecursiveInsertionSort(int i, vector<int> &arr)
{
    if (i <= 0)
        return;

    RecursiveInsertionSort(i - 1, arr);

    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key)
    {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = key;

}

我在 ma​​in 中这样调用它:

vector<int> arr (10000,1);
RecursiveInsertionSort(arr.size() - 1, sorted);

我不明白问题出在哪里。

Answer 1

我认为您的问题与您的环境中允许的最大递归级别有关。可以找到更多详细信息here和 here .

[编辑]

如果您不控制最大递归级别(例如在输入可能非常大的情况下)，最好避免递归并使用迭代算法(即使用 while、for 等)。这个问题解释here this article 中很好地介绍了如何将递归算法实际转换为非递归算法。 .