有人可以解释递归插入排序的工作原理吗？

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以对整个事物进行排序,但是您分别传递长度这一事实对于理解答案的其余部分至关重要.

我不明白为什么我们必须再次调用该函数n > 1.

或许解释这种情况意义的更好方法是,当一个或更少时,我们不会再次调用此函数n.这被称为递归算法的基本情况,即您不必做任何事情的情况.在排序的情况下,它意味着只有一个元素的数组已经被排序.

(n-1)当我们再次调用函数时,为什么要输入？

由于n是我们需要排序的元素数量,我们传递n-1给数组的前面排序.函数返回后,我们知道该部分A[1..n-1]已经排序.我们所要做的就是搬到A[n]正确的地方.我们在DOWHILE接下来的循环中执行此操作:我们一次向后移动一个元素,移动大于A[n]右边的元素.循环结束后,我们将A[n]其置于新的位置.现在范围A[1..n]已经排序.

一般如何递归递归？

该函数有两种情况 - 简单的基本情况,当一切都完成时,还原步骤,当你使用递归调用来解决一个更简单的问题,然后使用更简单的解决方案的结果来构建你的最终解决方案.

一旦我们再次调用该函数,我们是否会忽略第4行以后的代码,并直接跳转到第二个调用？

不,一旦函数返回,我们继续我们离开的地方.在您的情况下,该函数A[1..n-1]在放置A[n]到正确的位置之前等待范围进行排序.