algorithm - Quicksort 算法中的递归如何工作？

Question

我在 Google 中看到一些代码实现了这样的快速排序算法。

static public void QuickSort_Recursive(int [] arr, int left, int right)
{
    // For Recusrion
    if(left < right)
    {
        int pivot = Partition(arr, left, right);

        if(pivot > 1)
            QuickSort_Recursive(arr, left, pivot - 1);

        if(pivot + 1 < right)
            QuickSort_Recursive(arr, pivot + 1, right);
    }
}

我试着解决这个问题，我已经了解代码本身是如何工作的，但有一件事让我感到困惑。递归(上面的代码)是如何工作的。它是如何被终止的。我是递归函数的新手，我只知道它的基础。

谁能开门见山、简单易懂地向我解释一下。 :)

P.S:我知道分区部分，所以我没有包含它。

Answer 1

您可能知道，递归的工作原理是根据较小的实例定义较大的问题，并通过解决问题的较小实例并使用这些解决方案构建较大的解决方案来解决较大的问题。

在您的情况下，检查 left < right 的 if 语句是您问题的答案。随着 Quicksort_recursive 递归地减小问题的大小，将会出现数组中只有 1 个元素的点。然后，左将等于右，函数将不需要继续尝试递归地解决问题的较小实例。原因很简单:没有更小的问题实例。换句话说，不存在大小小于 1 的非空子数组。