How the recursion in Quicksort algorithm works?

问题:

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. :)

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

回答1:

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.

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.

回答2:

In sequential terms, each recursive call pushes all the local variables (including the function parameters) and the current code position onto a stack (the call stack) and then jumps to the start of the function, with the new parameters. When the call finishes, it pops the variables and return address from the stack, and drops back to where the call was made.

But the best way to understand recursion is actually to not try to work it out sequentially, but in terms of breaking down the problem into parts. You sort an array by splitting it in two parts, and then sorting each of the parts – unless the parts are size 1 or 0, in case you stop and finish that part (which is trivial, less than 2 elements is always sorted) without breaking it down further.

The execution is kind of like binary tree, where the leaves are the stop condition of subarray size 0 or 1.

I suggest modifying the code like this:

static public void QuickSort_Recursive(int [] arr, int left, int right) {
    QuickSort_Recursive(arr, left, right, 1);
}

static public void QuickSort_Recursive(int [] arr, int left, int right, int depth)
{
    System.out.println(String.format("%"+(depth*3)+"sleft=%d, right=%d", "", left, right));
    // For Recusrion
    if(left < right)
        {
            int pivot = Partition(arr, left, right);

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

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

That will give you a printout at each call that may help you understand what's happening.