2

嘿，我将此 C# 代码转换为 c++

void bubbleSort(int *inputArray, int passStartIndex, int currentIndex,int length)
{
    if(passStartIndex == length - 1) return;
    if(currentIndex == length - 1) return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1,length);

    //compare items at current index and current index + 1 and swap if required
    int nextIndex = currentIndex + 1;
    if(inputArray[currentIndex]>inputArray[nextIndex])
    {
        int temp = inputArray[nextIndex];
        inputArray[nextIndex] = inputArray[currentIndex];
        inputArray[currentIndex] = temp;
    }

    return bubbleSort(inputArray, passStartIndex, currentIndex + 1,length);
}

但是当我在长度为 50100 的输入数组上执行它时，它显示了我的期望

System.StackOverflowException 未处理消息：example.exe 中发生了“System.StackOverflowException”类型的未处理异常

我究竟做错了什么？如何解决？

4

2 回答 2

3

“我究竟做错了什么？”

每次递归函数调用自身，调用帧（激活记录）被存储到堆栈内存中。因此，当递归变得太深时，即达到堆栈的最大大小时，执行将终止。

另请查看：C++ 是否限制递归深度？

“怎么修？”

避免这个问题的最简单方法是从一开始就永远不要将算法设计为递归。但是一旦你已经有了这样的递归解决方案，在大多数情况下，可以将其重写为循环形式或（通常更容易）：尾递归。

基本上，如果您可以以一种从不直接将任何参数传递给下一次调用的方式重写您的函数，那么您就赢了。如果你看看你的递归，有两个地方，它调用自己和调用之前，只有currentIndex和passStartIndex正在被改变。想象一下，您将这些索引存储在一边，当前的函数调用只会发出信号“我已经完成了，这些是应该有人继续使用的值：......现在你可以继续！” ，这意味着不需要存储函数所在的状态。通过这样做，您最终会得到一个 Tail 调用（尤其参见第一个示例程序）。

这是如何使用您的代码完成的完整示例：Step 1 , Step 2

于 2013-02-12T19:00:40.227 回答
3

它不会解决您的问题（请参阅递归限制），但您使用的算法存在错误。你应该更换

if (currentIndex == length - 1)
    return bubbleSort(inputArray, passStartIndex+1, passStartIndex+1, length);

经过

if (currentIndex == length - 1)
    return bubbleSort(inputArray, passStartIndex+1, 0,length - 1);

冒泡排序应该重新开始到 0，因为第一项不在正确的位置，但最后一项是。

于 2013-02-12T19:14:07.953 回答