排序算法学习之路——快速排序（非递归实现）

Z时代
2024-01-10
分类：综合

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

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

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

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

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

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

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

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

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

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


functionFindPv(&$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;
}
functionPvSort(&$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);