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

Question

我有这个函数可以对数组进行递归选择排序:

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 时工作，并且它崩溃导致堆栈溢出。

我搜索了很多话题，他们都告诉我要使用 vector ，我也有。这是一个赋值问题，所以我应该对数组和 vector 进行递归排序。它适用于 vector ，但不适用于数组。此外，我不应该在此作业中使用指针。

Answer 1

你可以尝试使用尾递归，这样编译器会为你优化它作为循环:

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