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

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

谁能解释一下递归在这种情况下是如何工作的？有几件事我不明白：

我不明白为什么我们必须在 n > 1 时再次调用该函数。
为什么再次调用函数时输入的是(n-1)？是不是让我们整个过程从n=2，前2个元素开始？
递归一般是如何工作的？比如，一旦我们再次调用该函数，我们是否会忽略第 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对数组的前面进行排序。一旦函数 returns，我们就知道 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?

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

Answer 2

了解其工作原理的小示例：

recursive_insertion_sort([1, 7, 5, 2], 4)
    | recursive_insertion_sort([1, 7, 5, 2], 3)
    |    | recursive_insertion_sort([1, 7, 5, 2], 2)
    |    |    | recursive_insertion_sort([1, 7, 5, 2], 1) 
    |    | puts 7 in the right position between it's ORDERED left values [1] -> [1,7]
    | puts 5 in the right position between it's ORDERED left values [1,7] -> [1,5,7]
puts 2 in the right position between it's ORDERED left values [1,5,7] -> [1,2,5,7]

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

Can someone explain how recursive insertion sort works?

algorithm

sorting

recursion

insertion-sort