Quicksort算法中的递归如何工作？ [英] How the recursion in Quicksort algorithm works?

问题描述

我已经在Google中看到一些实现Quicksort算法的代码。

I've seen some code in Google implementing Quicksort algorithm like this.

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);
    }
}

我试图解决这个问题，我已经了解了代码本身是如何工作的，但是我很困惑。递归（上面的代码）如何工作。它是如何终止的。我是递归函数的新手，我只知道它的基本知识。

I tried to work out with this, I've already understood how the code itself works but one thing I got confused. How the recursion (the code above) works. How it is getting terminated. I am new in recursive functions, I only know its basic.

有人可以直接并简单地向我解释它吗？ ：）

Can someone explain it to me in a straight to the point and simple explanation. :)

PS：我知道分区部分，所以我没有包括它。

P.S: I know the Partitioning parts so I didn't include it.

推荐答案

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

As you probably know, recursion works by defining the larger problem in terms of its smaller instances and solves the larger problem by solving the smaller instances of the problem and using those solutions to construct the larger solution.

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

In your case, the if statement that checks left < right is the answer to your question. As Quicksort_recursive recursively decreases the size of the problem, there will come a point where the array only has 1 element in it. Then, left will be equal to right, and the function will not need to continue trying to recursively solve smaller instances of the problem. The reason is simple: there are no smaller instances of the problem. In other words, there are no non-empty subarrays to sort which has a size smaller than 1.

这篇关于Quicksort算法中的递归如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！