JIYIK CN >

In the article "Quick Sort", we introduced the principles and steps of quick sort, and implemented the algorithm using recursion. In the previous article, we also mentioned the use of non-recursive methods to implement the algorithm. In this article, we will use non-recursive methods to implement quick sort.

First, let's introduce the steps of the stack involved.

The first step is to apply for a stack to store the starting and ending positions of the sorted array.

Step 2: Push the starting position s and the end position e of the entire array into the stack

The third step is to pop the data from the stack, sort the data that has been popped, and find the final position p of the benchmark data.

Step 4: Determine whether the starting position s is less than the reference position p-1. If so, push the starting position and p-1 into the stack as the end position.

Step 5: Determine whether the reference position p+1 is less than the end position e. If so, push p+1 as the starting position and e as the end position into the stack.

Step 6: Determine whether the stack is empty. If it is not empty, repeat step 3, otherwise exit the operation.

The overall approach of using non-recursive methods is the above steps. Next, we will implement quick sorting through code.

The function for finding the base position can be the same as the one using recursion

function FindPv(&$arr, $s, $e)
{
    $p = $s;
    //基准起始位置
    $v = $arr[$p];
    //将数组的第一个值作为基准值
    while ($s < $e) {
        while ($arr[$e] > $v && $e > $p) {
            $e--;
        }
        $arr[$p] = $arr[$e];
        $p = $e;
        while ($arr[$s] < $v && $s < $p) {
            $s++;
        }
        $arr[$p] = $arr[$s];
        $p = $s;
    }
    $arr[$p] = $v;
    return $p;
}

function PvSort(&$arr)
{
    $stack = array();
    array_push($stack, array(0, count($arr) - 1));
    while (count($stack) > 0) {
        $temp = array_pop($stack);
        $p = FindPv($arr, $temp[0], $temp[1]);
        if ($p + 1 < $temp[1]) array_push($stack, array($p + 1, $temp[1]));
        if ($temp[0] < $p - 1) array_push($stack, array($temp[0], $p - 1));
    }
}

$arr = array(10, 6, 8, 23, 4, 1, 17, 56, 32, 50, 11, 9);
PvSort($arr);
print_r($arr);

The above is a non-recursive way to implement quick sort. In fact, the code is not complicated. Of course, PHP has more concise code to implement quick sort, but here we use this more primitive method, which will be more helpful for our understanding of quick sort.

I hope this article is helpful to you.