迹忆客 专注技术分享

在《快速排序》这篇文章中我们介绍了快速排序的原理和步骤，以及使用递归的方式实现了该算法。而且在上篇文章中我们还提到使用非递归的方式实现该算法，本篇我们就使用非递归的方式来实现快速排序。

首先我们对其中涉及到的栈的操作步骤进行一下介绍

第一步、申请一个栈，存放排序数组的起始位置和终点位置。

第二步、将整个数组的起始位置s和终点位置e进栈

第三步、出栈数据，对出栈的数据进行排序，查找基准数据所在最终的位置 p。

第四步、判断起始位置s 是否小于基准位置p-1，如果小于则将起始位置和p-1为终点位置进栈

第五步、判断基准位置p+1 是否小于终点位置e，如果小于则将 p+1作为起始位置，e作为终点位置进栈

第六步、判断栈是否为空，如果不为空则重复第三步，否则退出操作。

使用非递归的方式整体上就是上面的这个步骤。下面我们通过代码来实现快速排序。

其中查找基准位置的函数可以和使用递归方式的相同

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

上面就是实现快速排序的非递归的方式。其实代码也并不复杂，当然PHP有更简洁的代码来实现快速排序，但是这里我们使用这种比较原始的方式，将更有助于我们对快速排序的理解。

希望本文对大家有所帮助。