迹忆客 专注技术分享

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

全面了解归并排序算法及代码实现

作者:迹忆客 最近更新:2023/01/08 浏览次数:

在之前我写过关于归并排序的介绍,排序算法学习之路——归并排序。据现在已经有很长时间了。现在再重新进行规整,对归并排序再从代码层面详细说一下。

归并排序算法

按照惯例,对于排序算法。我们还是先罗列概念

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


合并

通过概念我们也能看出,既然是归并排序,那核心的问题就是如何进行归并了。这可以归结为从小往大的一个合并问题。

给定我们一组数据

归并排序原始数组

我们通过分治策略,将其拆分。直到不能拆为止,想要达到的效果如下

归并排序拆分数组

这就是我们最终用来进行归并的拆分后的数组。下面开始合并

归并排序合并过程

我们可以看到,每两个数组进行合并。合并之后的新数组是有序的。然后新数组之间再两两合并,直到合并为一个最终的数组。

下面我们以最后一步合并为例子,介绍一下两个数组之间合并的细节步骤。

归并排序合并细节开始

第一步、 sl 和 sr位置上的元素进行比较,值小的一方的元素放入新数组,然后对应的索引 sl/sr 向前进一位。这里 sl位置上的2小,因此将2 放入新数组,sl移到该组的下一个元素

归并排序合并细节第二步

第二步、再次将 sl 和 sr 位置上的元素进行比较,3 比 6 小,因此 3放入新数组,sl再次移动到下一个元素

归并排序合并细节第三步

第三步、二者继续比较,此时 sr上的 6 要比 sl上的7小。因此将6放入新的数组,sr移动到该组的下一个元素

归并排序合并细节第四步

第四步、重复上面的比较过程,直到有一组先于另一组全部放入到新数组中

归并排序合并细节第五步

最后,此时的 sl一组已经全部排序完成了,而对于 sr一组剩余的元素可以直接放入新数组。因为每一组之内的元素都是有序的。

归并排序合并细节成功

此时我们看到整个归并过程已经完成了。下面我们看一下合并过程的代码

function Merge($arr,$l,$m,$r)
{
    $t = $arr;
    $lstart = $l;
    $rstart = $m+1;

    while($l < $r) {
        if($lstart > $m || $rstart > $r) break;
        if($arr[$lstart] > $arr[$rstart]) {
            $t[$l++] = $arr[$rstart++];
        }else{
            $t[$l++] = $arr[$lstart++];
        }
    }

    $start = $l;
    $end = $r;

    if($lstart <= $m) {
        $start = $lstart;
        $end = $m;
    }elseif($rstart <= $r) {
        $start = $rstart;
        $end = $r;
    }

    while($start <= $end) {
        $t[$l++] = $arr[$start++];
    }
    $arr = $t;

    return $arr;
}

拆分

上面我们看到了归并排序的核心的过程,合并。但是只是有合并的过程还是不完整的,因为给到我们的原始数据是一组完整的数据。因此在合并之前我们应该先对其进行拆分。

拆分的过程比较简单,它不会涉及到排序的问题,只是拆就完了。

归并排序拆分过程

这里拆分过程的代码可以分为两种方式:递归实现和非递归实现

下面我们分别看一下两种不同的拆分代码

递归

递归方式代码就非常简单了,我们只需要设定递归终止条件,然后按照一个整体的轮廓写代码就可以了

function MergeSort(&$arr,$l,$r)
{
    if($l >= $r) {
        return;
    }
    $m = floor(($l+$r) / 2);

    MergeSort($arr,$l,$m);
    MergeSort($arr,$m+1,$r);
    $arr = Merge($arr,$l,$m,$r);
}

我们可以看到,代码很简单。按照深度优先方式,先拆左边,然后再拆右边。最后调用我们上面的Merge() 函数进行合并就行了。

非递归

非递归的方式代码显得就有点复杂了,在上面使用递归的方式拆分的过程中,其实我们只是设定了终止递归的条件,其他的细节不用考虑的。但是非递归方式就必须需要考虑细节了。

因为拆分的过程是一个深度优先的过程,针对深度优先这里就需要用到栈机制。

其实,递归底层的实现机制也是借助的栈的机制实现的。

这里我们看一下代码

function MergeSort(&$arr)
{
    $stack = []; //  初始化一个栈
    $toMergeStack = []; // 用于归并的栈
    $l = 0;
    $r = count($arr) - 1;

    $tmp = [$l,$r,floor(($l+$r)/2)];

    array_push($stack,$tmp);
    array_push($toMergeStack,$tmp);

    while(!empty($stack)) {
        $s = array_pop($stack);
        if($s[0] < $s[2]) {
            array_push($stack,[$s[0],$s[2],floor(($s[0]+$s[2])/2)]);
            array_push($toMergeStack,[$s[0],$s[2],floor(($s[0]+$s[2])/2)]);
        }

        if($s[2]+1 < $s[1]) {
            array_push($stack,[$s[2]+1,$s[1],floor(($s[2]+1+$s[1])/2)]);
            array_push($toMergeStack,[$s[2]+1,$s[1],floor(($s[2]+1+$s[1])/2)]);
        }
    }

    // 开始合并
    while(!empty($toMergeStack)){
        $s = array_pop($toMergeStack);
        $arr = Merge($arr,$s[0],$s[2],$s[1]);
    }
}

我们再看代码明显多出许多来。但是这个过程并不复杂,理解了非递归的方式更有助于我们对归并排序的理解。

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

本文地址:

相关文章

MySQL 递归查询

发布时间:2023/04/18 浏览次数:89 分类:MySQL

在本指南中,我们将了解 MySQL 的递归查询。 如何在 SQL 中编写递归查询及其工作原理将在本指南中进行解释,以便您更好地理解。

MATLAB 递归函数

发布时间:2023/03/19 浏览次数:95 分类:MATLAB

在 MATLAB 中可以轻松定义递归函数。

在 Linux 中递归查找文件

发布时间:2023/02/28 浏览次数:103 分类:操作系统

在这篇 Linux 文章中,我们将学习如何在 Linux 中递归查找文件。我们还将了解如何在 Linux 系统的子目录中递归搜索文件。

排序算法学习之路——基数排序(MSD)

发布时间:2016/04/14 浏览次数:6071 分类:算法

MSD基数排序是从最高位开始对序列进行分组,到最低位为止。但是其实现过程是和LSD基数排序不同的,排序过程中需要用到递归函数。

排序算法学习之路——基数排序(LSD)

发布时间:2016/04/14 浏览次数:6727 分类:算法

基数排序的基本原理是,按照整数的每个位数分组。在分组过程中,对于不足位的数据用0补位。基数排序按照对位数分组的顺序的不同,可以分为LSD基数排序和MSD基数排序。

排序算法学习之路——冒泡排序

发布时间:2016/04/13 浏览次数:379 分类:算法

冒泡排序也是一种简单直观的排序算法。其思想是:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有

排序算法学习之路——选择排序

发布时间:2016/04/12 浏览次数:424 分类:算法

选择排序是一种简单直观的排序算法。其基本思想是在未排序的序列中选择一个最大(或最小)元素放到末尾(注意:这里是未排序序列的末尾,可以认为是有序序列的起始位置)。

排序算法学习之路——堆排序

发布时间:2016/04/11 浏览次数:873 分类:算法

堆排序(Heapsort):是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节

扫一扫阅读全部技术教程

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

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便