(递归)插入排序中递归结尾处的程序

Question

我试图在C++中递归地实现插入排序。

#include <iostream>
#include <vector>
using namespace std;

vector<int> insertionSort(vector<int>& A,int p,int r)
{ 
    for(auto x=p;x<=r;++x) cout<<A[x]<<' ';
    cout<<endl;  
    if(p<r-1) insertionSort(A,p,r-1);
    cout<<"flag";
    int key=A[r];
    int i=r-1;
    while(i>p)
    {
        if(key<=A[i])
        {
            A[i+1]=A[i];
            i=i-1;
        }
        A[i+1]=key;
    }
    return A;
}

int main()
{
    vector<int> A {22,2,31,41,59,90,11,26,41,58};
    insertionSort(A,0,A.size()-1);
    for(auto x:A) cout<<x<<' ';
    cout<<endl;
}

输出：

22 2 31 41 59 90 11 26 41 58

22 2 31 41 59 90 11 26 41

22 2 31 41 59 90 11 26

22 2 31 41 59 90 11

22 2 31 41 59 90

22 2 31 41 59

22 2 31 41

22 2 31

22 2

^C⏎

如您所见，它会在递归结束时被卡住(它不会超过标志语句)，我不得不手动退出执行。如果我的理解是正确的，当递归到达其结束时，下一个语句将在每个调用堆栈中执行。请帮我解决这个问题。任何帮助都将不胜感激。

Answer 1

谢谢大家的有益评论。就像他们说的那样，程序似乎被卡住了，因为当if块没有被执行时，出现了一个无限循环。因此，我添加了一个break，并将插入语句放在while块之外。以下是修正后的代码：

vector<int> insertionSort(vector<int>& A,int p,int r)
{   
    if(p<r-1) insertionSort(A,p,r-1);
    int key=A[r];
    int i=r-1;
    while(i>=p)
    {
        if(key<A[i])
        {
            A[i+1]=A[i];
            i=i-1;
        }
        else break;
    }
    A[i+1]=key;
    return A;
}