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

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

我们先看归并排序的定义

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

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

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

归并排序流程

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

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

  4. 重复步骤3直到某一指针达到序列尾

  5. 将另一序列剩下的所有元素直接复制到合并序列尾

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

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,$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有其自己的特色，可以用更少的代码来实现归并排序。但是上述代码更能体现整个分解和合并的过程。所以如果是学习归并排序算法的话，建议使用上述代码，虽说代码繁琐，但是对于理解归并排序的过程有很大的帮助。

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

本文转载自：迹忆客（https://www.jiyik.com）

以上是 排序算法学习之路——归并排序 的全部内容， 来源链接： utcz.com/z/290044.html

回到顶部