c++ - C++中的堆栈溢出错误

我有这个功能，它对数组进行递归选择排序：

void  SelectionSort::RecursiveSort(int ar[] , int flag, int first, int last){
    // first - index of first element and last - index of last element
    if (flag == 1)
    {
        if (first < last)               //ascending
        {
            for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]);

            RecursiveSort(ar, flag, first + 1, last);
        }
        if (first == last) return;

    }
    else
    {
        if (first < last)                   //desc
        {
            for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]);

            RecursiveSort(ar,flag, (first + 1), last);
        }
        if (first == last) return;

    }
}

如果数组大小为3000，它可以正常工作，但是我应该使它的大小大于5000，并且崩溃会导致堆栈溢出。

我搜索了很多线程，它们都告诉我要使用向量。这是一个分配问题，因此我应该对数组和向量都进行递归排序。它适用于向量，但不适用于数组。另外，我不应该在此作业中使用指针。

最佳答案

您可以尝试使用尾部递归，因此编译器将为您优化它作为循环：

void AscRecursiveSort(int ar[], int first, int last) {
    if (first >= last) return;
    for (int i = first; i <= last; i++) if (ar[i] < ar[first]) swap(ar[i], ar[first]);
    AscRecursiveSort(ar, first + 1, last);

}

void DescRecursiveSort(int ar[], int first, int last) {
    if (first >= last) return;
    for (int i = first; i <= last; i++) if (ar[i] > ar[first]) swap(ar[i], ar[first]);
    DescRecursiveSort(ar, first + 1, last);
}

void RecursiveSort(int ar[], int flag, int first, int last) {
    // first - index of first element and last - index of last element
    if (flag == 1)
        AscRecursiveSort(ar, first, last);              //ascending
    else
        DescRecursiveSort(ar, first, last);
}

关于c++ - C++中的堆栈溢出错误，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33201093/