迹忆客 专注技术分享

在《归并排序》这篇文章中我们介绍了归并排序的原理以及操作步骤，最后我们使用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);

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

关于归并排序又写了一篇 全面了解归并排序算法。里面更详细的说明了归并排序的拆分和合并的过程，代码包括递归和非递归两种实现方式。

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