首页 后端开发 php教程 PHP实现归并排序的方法

PHP实现归并排序的方法

May 31, 2018 pm 03:09 PM
php 排序 方法

本文主要介绍了php归并排序的实现算法,即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列。有兴趣的朋友可以来了解一下。

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表。归并排序的一个缺点是它需要存储器有另一个大小等于数据项数目的数组。如果初始数组几乎占满整个存储器,那么归并排序将不能工作,但是如果有足够的空间,归并排序会是一个很好的选择。

假设待排序的序列:

4 3 7 9 2 8 6

先说思路,归并排序的中心思想是将两个已经排序好的序列,合并成一个排序的序列。

上面的序列可以分成:

4 3 7 9

2  8  6

这两个序列,然后对这两个序列分别排序:结果为:

设置为序列A,与序列B,

3 4 7 9
2  6  8

将上面的两个序列 合并成一个排序好的序列:

合并的具体思路是:

设置两个位置指示器,分别指向序列A与序列B开始的位置:红色为指示器指向位置:

3 4 7 9
2  6  8

比较两个指示器所指向的元素的值,将较小的插入到一个新的数组内,例如序列C,同时将对应的指示器向后移动一位:
结果为:

3 4 7 9
6  8

形成的序列C:已经被插入一个元素了,刚才较小的 元素2.
2

然后 再次 比较序列A与序列B中指示器所指向的元素:将小的放入到序列C中,移动相应指针,结果为:

3 4 7 9
8
2  3

以此类推,迭代执行,直到序列A或者序列B中某个指示器已经移到到数组末端。例如:
多次比较后,序列B已经将指示器移出到序列末端(最后一个元素之后)了。
3 4 7 9
2  6  8
2 3 4 6 7 8

然后将没有用完的序列,这里面是序列A中其余的元素全部插入到序列C的后边即可,就剩下一个9 了,将其插入到序列C后即可:

序列C结果:

2 3 4 5 6 7 8 9

这样就实现了将两个有序序列合并成一个有序序列的操作,

下面先看这个合并的php代码:

/**
 * 将两个有序数组合并成一个有序数组
 * @param $arrA,
 * @param $arrB,
 * @reutrn array合并好的数组
 */
function mergeArray($arrA, $arrB) {
  $a_i = $b_i = 0;//设置两个起始位置标记
  $a_len = count($arrA);
  $b_len = count($arrB);
  while($a_i<$a_len && $b_i<$b_len) {
    //当数组A和数组B都没有越界时
    if($arrA[$a_i] < $arrB[$b_i]) {
      $arrC[] = $arrA[$a_i++];
    } else {
      $arrC[] = $arrB[$b_i++];
    }
  }
  //判断 数组A内的元素是否都用完了,没有的话将其全部插入到C数组内:
  while($a_i < $a_len) {
    $arrC[] = $arrA[$a_i++];
  }
  //判断 数组B内的元素是否都用完了,没有的话将其全部插入到C数组内:
  while($b_i < $b_len) {
    $arrC[] = $arrB[$b_i++];
  }
  return $arrC;
}
登录后复制

经过上面的分析和程序的实现,我们不难发现,合并已排序的序列的时间应该是线性的,就是说,最多会发生N-1次比较,其中N是所有元素之和。

通过上面的描述,我们实现了将两个排序好的数组进行和并的过程。

此时,大家可能会有疑问,这个和归并排序整个序列有什么关系?或者你是如何能够得到最开始的两个排序好的子序列的呢?
下面,我们就来描述以下什么是归并排序,然后再看,上面的合并与归并排序的关系是如何的:

大家不妨去想,当我们需要排序如下的数组时,我们是否可以先将数组的前半部分与数组的后半部分分别进行归并排序,然后将排序的结果合并起来呢?

例如:待排序的数组:
4 3 7 9 2 8 6

先分成2部分:

4 3 7 9
2 8 6

将前半部分 与 后半部分 分别看成一个序列,再次进行归并(就是拆分,排序,合并)操作
就会变成:

前:
4 3
7 9

后:
2 8
6

同样 再对每个自序列进行 归并排序,再次(拆分,排序,合并)。

当拆分的子序列内只存在一个元素(长度为1)时,那么这个序列就不必再拆分了,就是一个排序好的数组了。然后将这个序列,与其他的序列再合并到一起即可,最终就将所有的都合并好了,成为一个完整的排序好的数组。

程序实现:

通过上面的描述 大家应该想到,可以使用递归程序来实现这个程序设计吧:

想要实现这个程序,可能需要解决如下问题:

怎么将数组做拆分:

设定两个指示器,一个指向数组开始假定为$left,一个指向数组最后一个元素$right:
4 3 7 9 2 8 6

然 后判断 $left 是否小于$right,如果小于,说明这个序列内元素个数大于一个,就将其拆分成两个数组,拆分的方式是生成一个中间的指示器$center,值 为$left + $right /2 整除。结果为:3,然后将$left 到$center 分成一组,$center+1到$right分成一组:
4 3 7 9
2 8 6
接下来,递归的 利用$left, $center, $center+1, $right分别做为 两个序列的 左右指示器,进行操作。知道数组内有一个元素$left==$right .然后按照上面的合并数组即可:

/**
* mergeSort 归并排序
* 是开始递归函数的一个驱动函数
* @param &$arr array 待排序的数组
*/
function mergeSort(&$arr) {
  $len = count($arr);//求得数组长度
 
  mSort($arr, 0, $len-1);
}
/**
* 实际实现归并排序的程序
* @param &$arr array 需要排序的数组
* @param $left int 子序列的左下标值
* @param $right int 子序列的右下标值
*/
function mSort(&$arr, $left, $right) {
 
  if($left < $right) {
    //说明子序列内存在多余1个的元素,那么需要拆分,分别排序,合并
    //计算拆分的位置,长度/2 去整
    $center = floor(($left+$right) / 2);
    //递归调用对左边进行再次排序:
    mSort($arr, $left, $center);
    //递归调用对右边进行再次排序
    mSort($arr, $center+1, $right);
    //合并排序结果
    mergeArray($arr, $left, $center, $right);
  }
}
 
/**
* 将两个有序数组合并成一个有序数组
* @param &$arr, 待排序的所有元素
* @param $left, 排序子数组A的开始下标
* @param $center, 排序子数组A与排序子数组B的中间下标,也就是数组A的结束下标
* @param $right, 排序子数组B的结束下标(开始为$center+1)
*/
function mergeArray(&$arr, $left, $center, $right) {
  //设置两个起始位置标记
  $a_i = $left;
  $b_i = $center+1;
  while($a_i<=$center && $b_i<=$right) {
    //当数组A和数组B都没有越界时
    if($arr[$a_i] < $arr[$b_i]) {
      $temp[] = $arr[$a_i++];
    } else {
      $temp[] = $arr[$b_i++];
    }
  }
  //判断 数组A内的元素是否都用完了,没有的话将其全部插入到C数组内:
  while($a_i <= $center) {
    $temp[] = $arr[$a_i++];
  }
  //判断 数组B内的元素是否都用完了,没有的话将其全部插入到C数组内:
  while($b_i <= $right) {
    $temp[] = $arr[$b_i++];
  }
 
  //将$arrC内排序好的部分,写入到$arr内:
  for($i=0, $len=count($temp); $i<$len; $i++) {
    $arr[$left+$i] = $temp[$i];
  }
 
}
 //do some test:
$arr = array(4, 7, 6, 3, 9, 5, 8);
mergeSort($arr);
print_r($arr);
登录后复制

注意上面的代码带排序的数组都使用的是 引用传递,为了节约空间。

而且,其中的合并数组的方式也为了节约空间做了相对的修改,把所有的操作都放到了$arr上完成,引用传递节约资源。

好了 上面的代码就完成了归并排序,归并排序的时间复杂度为O(N*LogN) 效率还是相当客观的。

再说,归并排序算法,中心思想是 将一个复杂问题分解成相似的小问题,再把小问题分解成更小的问题,直到分解到可以马上求解为止,然后将分解得到的结果再合并起来的一种方法。这个思想用个 成语形容叫化整为零。 放到计算机科学中有个专业属于叫分治策略(分治发)。分就是大问题变小问题,治就是小结果合并成大结果。

分治策略是很多搞笑算法的基础,我们在讨论快速排序时,也会用到分治策略的。

最后简单的说一下这个算法,虽然这个算法在时间复杂度上达到了O(NLogN)。但是还是会有一个小问题,就是在合并两个数组时,如果数组的总元素个数为 N,那么我们需要再开辟一个同样大小的空间来保存合并时的数据(就是mergeArray中的$temp数组),而且还需要将数据有$temp拷贝 会$arr,因此会浪费一些资源。因此在实际的排序中还是 相对的较少使用。

总结:以上就是本篇文的全部内容,希望能对大家的学习有所帮助。

相关推荐:

PHP使用curl_multi实现并发请求的方法示例

PHP性能测试工具xhprof安装与使用方法详解

PHP实现通过strace定位故障原因的方法

以上是PHP实现归并排序的方法的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解锁Myrise中的所有内容
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 Dec 24, 2024 pm 04:42 PM

PHP 8.4 带来了多项新功能、安全性改进和性能改进,同时弃用和删除了大量功能。 本指南介绍了如何在 Ubuntu、Debian 或其衍生版本上安装 PHP 8.4 或升级到 PHP 8.4

CakePHP 日期和时间 CakePHP 日期和时间 Sep 10, 2024 pm 05:27 PM

为了在 cakephp4 中处理日期和时间,我们将使用可用的 FrozenTime 类。

讨论 CakePHP 讨论 CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP 是 PHP 的开源框架。它的目的是使应用程序的开发、部署和维护变得更加容易。 CakePHP 基于类似 MVC 的架构,功能强大且易于掌握。模型、视图和控制器 gu

CakePHP 文件上传 CakePHP 文件上传 Sep 10, 2024 pm 05:27 PM

为了进行文件上传,我们将使用表单助手。这是文件上传的示例。

CakePHP 创建验证器 CakePHP 创建验证器 Sep 10, 2024 pm 05:26 PM

可以通过在控制器中添加以下两行来创建验证器。

CakePHP 日志记录 CakePHP 日志记录 Sep 10, 2024 pm 05:26 PM

登录 CakePHP 是一项非常简单的任务。您只需使用一项功能即可。您可以记录任何后台进程(如 cronjob)的错误、异常、用户活动、用户采取的操作。在 CakePHP 中记录数据很容易。提供了 log() 函数

如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 Dec 20, 2024 am 11:31 AM

Visual Studio Code,也称为 VS Code,是一个免费的源代码编辑器 - 或集成开发环境 (IDE) - 可用于所有主要操作系统。 VS Code 拥有针对多种编程语言的大量扩展,可以轻松编写

CakePHP 快速指南 CakePHP 快速指南 Sep 10, 2024 pm 05:27 PM

CakePHP 是一个开源MVC 框架。它使开发、部署和维护应用程序变得更加容易。 CakePHP 有许多库可以减少大多数常见任务的过载。

See all articles