algorithm - 有人可以解释递归插入排序是如何工作的吗？

Question

假设A是一个数组，n是A中元素的个数，

recursive_insertion_sort(A, n)
    IF n > 1 THEN
        recursive_insertion_sort(A, n-1)
        key = A[n]
        i = n - 1
        DOWHILE A[i] > key AND i > 0
            A[i+1] = A[i]
            i = i - 1
        ENDDO
        A[i+1] = temp
    ENDIF
END

有人可以解释递归在这种情况下是如何工作的吗？有几件事我不明白:

1. 我不明白为什么我们必须在 n > 1 时再次调用该函数。
2. 为什么再次调用函数时输入的是(n-1)？是不是让我们从n = 2，前2个元素开始整个过程​​？
3. 递归一般是如何工作的？比如，一旦我们再次调用该函数，我们是否会忽略第 4 行之后的代码，直接跳转到第二次调用？还是我们会在第一次通话的同时进行第二次通话？

Answer 1

在讨论实现之前，让我们解释一下这个函数的作用:它不会对整个数组 A 进行排序，而只会对它的初始 n 元素进行排序。您可以传递 n 的数组长度来对整个事物进行排序，但单独传递长度这一事实对于理解其余答案至关重要。

I don't understand why we have to call the function again if n > 1.

也许解释此条件含义的更好方法是当 n 等于或小于 1 时，我们不要再次调用此函数。这称为递归算法的基本情况，即您无需执行任何操作的情况。在排序的情况下，这意味着只有一个元素的数组已经排序。

Why do we input (n-1) when we call the function again?

由于n 是我们需要排序的元素个数，我们通过n-1 对数组的前面进行排序。函数返回后，我们知道 A[1..n-1] 部分已经排序。我们需要做的就是将 A[n] 移动到正确的位置。我们在随后的 DOWHILE 循环中执行此操作:一次向后移动一个元素，将大于 A[n] 的元素向右移动。一旦循环结束，我们将 A[n] 放到它的新位置。现在范围 A[1..n] 已排序。

How does recursion in general work?

该函数有两种情况 - 简单的基本情况，当一切都完成时，以及减少步骤，当您使用递归调用来解决一个更简单的问题，然后使用更简单的解决方案的结果来构建您的最终解决方案时。

once we call the function again, do we ignore the code from line 4 onwards, and jump straight into the second call?

不，一旦函数返回，我们从离开的地方继续。在您的情况下，该函数等待 A[1..n-1] 范围排序，然后再将 A[n] 放置到正确的位置。