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

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

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

《归并排序》这篇文章中我们介绍了归并排序的原理以及操作步骤,最后我们使用PHP代码实现了排序算法。在程序中我们使用了递归的原理实现的该算法。

其实递归函数底层借助的无非就是栈的机制。在这篇文章中我们不使用递归函数,直接借助栈的机制来实现归并排序。

首先让我们大概来介绍一下非递归实现的基本原理:

首先我们需要申请两个栈——stack,stack1;

第一步、先将我们待排序序列的起始位置s,终点位置e和中间位置m进栈stack1。

第二步、出栈stack1中的数据,然后将出栈的数据进栈stack。然后判断s是否小于m? 如果s小于m,则将s作为起始位置,m作为终点位置,(s+m)/2作为中间位置进栈stack1。接着判断m+1是否小于e,如果m+1小于e,则将m+1作为起始位置,e作为终点位置,(m+1+e)/2作为中间位置进栈stack1。

第三步、判断stack1是否为空,如果为空则进行第四步。如果不为空则重复第二步。

第四步、出栈stack中的数据,按照出栈数据的起始位置,终点位置和中间位置进行合并(其合并的过程和上一篇文章中的相同)。

第五步、判断栈stack是否为空,如果不为空则重复第四步,如果为空则程序结束。

下面我们来看实现的代码

function Merge($arr,$l,$m,$r){
    $t = $arr;
    $start = $l;
    $end = $m+1;
    while($l<=$r){
        if($l>$m||$end>$r) break;
        if($arr[$l]<$arr[$end]){
            $t[$start++] = $arr[$l++];
        }else{
            $t[$start++] = $arr[$end++];
        }
    }
    if($l<=$m){
        $s = $l;
        $e = $m;
    }elseif($r>=$end){
        $s = $end;
        $e = $r;
    }
    while($s<=$e){
        $t[$start++] = $arr[$s++];
    }
    $arr = $t;
    return $arr;
}
function MergeSort(&$arr){
    $stack = array();
    $stack1 = array();
    $temp = array(0,count($arr)-1,floor((0+count($arr)-1)/2));
    array_push($stack1,$temp);
    while(count($stack1)>0){
        $temp = array_pop($stack);
        array_push($stack,$temp);
        if($temp[0]<$temp[2]){
            array_push($stack1,array($temp[0],$temp[2],floor(($temp[0]+$temp[2])/2)));
        }
        if($temp[2]+1<$temp[1]){
            array_push($stack1,array($temp[2]+1,$temp[1],floor(($temp[2]+1+$temp[1])/2)));
        }
    }
    while(count($stack)>0){
        $temp = array_pop($stack);
        $arr = Merge($arr,$temp[0], $temp[2], $temp[1]);
    }
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
MergeSort($arr);
print_r($arr);

我们看相对于递归方式实现归并排序,该方法代码比较多。但是鉴于归并排序的原理,此种方式我个人看来要比递归方式更容易理解。毕竟递归的实现也是借助于栈的机制。我们通过直接操作栈来实现归并算法,将使我们对归并排序的理解更加深了一步。

希望这些对大家有所帮助。

赞助
迹忆博客

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

本文地址: