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

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

在《归并排序》这篇文章中我们介绍了归并排序的原理以及操作步骤，最后我们使用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是否为空，如果不为空则重复第四步，如果为空则程序结束。

下面我们来看实现的代码


functionMerge($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;
}
functionMergeSort(&$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);