迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 算法 >

排序算法学习之路——归并排序

作者:迹忆 最近更新:2022/11/19 浏览次数:

我们先看归并排序的定义

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

简单来说就是将两个有序表合并成一个有序表。

我们先通过下图来了解一下归并排序的流程。

归并排序流程

下面我们来看如何分解然后再合并的步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

最后我们用PHP实现了归并排序的算法

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,$l,$r){
   if($r <= $l) return ;
   $m = floor(($l+$r)/2);
   MergeSort($arr,$l,$m);
   MergeSort($arr,$m+1,$r);
   $arr = Merge($arr,$l,$m,$r);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
MergeSort($arr,0,count($arr)-1);
print_r($arr);

上面代码是使用递归的机制实现的,当然也可以使用非递归的形式来实现,大家可以参考《归并排序(非递归实现)》这篇文章。

用PHP实现归并排序,按照上面的代码来说,其代码比较繁琐。PHP有其自己的特色,可以用更少的代码来实现归并排序。但是上述代码更能体现整个分解和合并的过程。所以如果是学习归并排序算法的话,建议使用上述代码,虽说代码繁琐,但是对于理解归并排序的过程有很大的帮助。

更详细的归并排序的算法我新写了一篇文章全面了解归并排序算法,大家可以参考。

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

MATLAB 对行进行排序

发布时间:2023/04/23 浏览次数:198 分类:MATLAB

本教程将讨论使用 MATLAB 中的 sortrows() 函数对矩阵中存在的行进行排序。在数据分析和处理中,排序是必不可少的,因为它可以使数据在排序时易于分析和处理。

在 Angular 中对表格进行排序

发布时间:2023/04/11 浏览次数:69 分类:Angular

我们可以按升序、降序等方式对表进行排序。现在让我们看看在 Angular 框架内创建具有排序功能的表的最佳方法。

在 C++ 中对字符串进行排序

发布时间:2023/03/31 浏览次数:102 分类:C++

本文演示了如何在 C++ 中对字符串进行排序。在本文中,我们假设字符序列存储在 std::string 对象中。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便