C++ 递归字符串归并排序

Question

这是一个家庭作业问题，所以虽然我想要可用的代码，但我真正想要的是如何解决这个问题。我有两个按升序排列的排序数组，我需要在递归函数中组合它们。看来我需要建立合并排序算法的排序部分。要求是递归函数只能将排序后的两个字符串作为参数，不能使用全局或静态变量。

我认为伪代码是:

• 如果两个字符串的大小== 0则返回结果字符串。
• 比较每个字符串的 substr(0,1) 以查看哪个较小，并将其附加到结果字符串
• 递归调用函数，新参数是附加字符串的子字符串

我的问题是:如果不能使用静态变量，如何保存结果字符串？我见过在递归调用的返回语句中将字符串定义为 = 的代码。这在这种情况下行得通吗？

第二个问题是函数如何自增。我需要在第一次迭代后调用 substr(1,size-1)，然后在不使用静态变量的情况下递增它。

这是我尝试使用静态变量(这是不允许的)求解方程式:

static string result="";
static int vv=0;
static int ww=0;

if(v.size()==0 && w.size()==0)
    return result;
if(w.size()==0 || v.substr(0,1) <= w.substr(0,1)){ 
    result+=v.substr(0,1);
    vv++;
    return spliceSortedStrings( v.substr(vv,v.size()-vv) , w); 
    }
else if(v.size()==0 || w.substr(0,1) > v.substr(0,1)){
    result+=w.substr(0,1);
    ww++;
    return spliceSortedStrings( v , w.substr(ww,w.size()-ww));
    }

我将不胜感激任何指导。

Answer 1

这个怎么样:

std::string merge(std::string a, std::string b) {
    if (a.size() == 0) return b;
    if (b.size() == 0) return a;

    if (a.back() < b.back()) {
        std::string m = merge(a, b.substr(0, b.size()-1));
        return m + b.back();
    }
    else {
        std::string m = merge(a.substr(0, a.size()-1), b);
        return m + a.back();
    }
}

正确性和终止应该是显而易见的，我认为它应该符合给定的约束条件。但我想知道哪位老师会在 C++ 中提出这样的任务，因为上面的代码几乎是低效的。