排序算法学习之路——归并排序(非递归实现)
在这篇文章中我们介绍了归并排序的原理以及操作步骤,最后我们使用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);
我们看相对于递归方式实现归并排序,该方法代码比较多。但是鉴于归并排序的原理,此种方式我个人看来要比递归方式更容易理解。毕竟递归的实现也是借助于栈的机制。我们通过直接操作栈来实现归并算法,将使我们对归并排序的理解更加深了一步。
关于归并排序又写了一篇 。里面更详细的说明了归并排序的拆分和合并的过程,代码包括递归和非递归两种实现方式。
希望这些对大家有所帮助。
转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处
本文地址:
相关文章
如何对 pandas 中的 dataframe 行随机排序
发布时间:2024/04/23 浏览次数:128 分类:python
-
我们可以使用 sample(),shuffle()和 permutation()方法随机地对 pandas 中的 dataframe 行进行随机排序。
获取 pandas 列中的唯一值并进行排序
发布时间:2024/04/20 浏览次数:147 分类:python
-
本教程演示了如何在 pandas dataframe 中查找列中的唯一值以及如何对其进行排序。
在 javascript 中对整数数组进行排序
发布时间:2024/03/16 浏览次数:110 分类:javascript
-
本教程解释了使用 .sort 方法对整数数组进行排序的正确方法,该方法带有一个接收两个数字并返回由比较操作定义的排序顺序的比较函数。
使用 powershell 对数组值进行排序
发布时间:2024/02/06 浏览次数:169 分类:编程语言
-
本教程将教你在 powershell 中对数组值进行排序。数组是一种数据结构,用作多个项目的集合。这些项目可以是相同的或不同的类型。
在 c# 中按值对字典排序
发布时间:2024/01/19 浏览次数:179 分类:编程语言
-
有两种主要方法可用于按 c# 中的值对字典进行排序:list 方法和 linq 方法。使用 c# 中的 list 方法按值对字典进行排序。c# 字典数据结构以 key:value 对的形式存储数据。