迹忆博客
当前位置: 主页 > 学无止境 > 算法 > 文章

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

发布时间: 2016-04-09 作者: 迹忆 浏览次数:

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

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

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

第二步、将整个数组的起始位置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有更简洁的代码来实现快速排序,但是这里我们使用这种比较原始的方式,将更有助于我们对快速排序的理解。

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

赞助
迹忆博客

除非注明转载,本站文章均为原创,欢迎转载,转载请以链接形式注明出处

本文地址: