PHP排序算法系列之归并排序详解

yipeiwu_com5年前PHP代码库

归并排序

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

归并过程

归并排序的核心就是如何将两个有序序列进行合并,假定有两个有序数组,比较两个有序数组的首个元素,谁小就取谁,并将该元素放入第三个数组中,取了之后在相应的数组中将删除此元素,依次类推,当取到一个数组已经没有元素时,就可将另一数组的剩余元素直接添加到第三个数组中。

原理

1、将序列每相邻两个数字进行归并操作,形成ceil(n/2)个序列,排序后每个序列包含两个元素,最后一个序列可能只有一个元素。

2、将上述序列再次归并,形成ceil(n/4)个序列,每个序列包含四个元素,最后一个序列可能只有三个及以下元素。

3、重复步骤2,直到所有元素排序完毕。

举例

对数组[53,89,12,6,98,25,37,92,5]进行排序

第一次归并后

(53,89),12,(6,98),(25,37),(5,92)

第二次归并后

(12,53,89),(6,25,37,98),(5,92)

第三次归并后

(6,12,25,37,53,89,98),(5,92)

第四次归并后

5,6,12,25,37,53,89,92,98

PHP代码实现

<?php
function merge_sort($arr){
  $length=count($arr);
  if($length<=1){
    return $arr;
  }
  //分解数组,递归排序
  $half=ceil($length/2);
  $arr2=array_chunk($arr,$half);
  $left=merge_sort($arr2[0]);
  $right=merge_sort($arr2[1]);
  while(count($left)&&count($right)){
    if($left[0]<$right[0]){
      $reg[]=array_shift($left);
    }else{
      $reg[]=array_shift($right);
    }
  }
  return array_merge($reg,$left,$right);
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【宜配屋www.yipeiwu.com】。

相关文章

PHP调试的强悍利器之PHPDBG

PHPDBG是一个PHP的SAPI模块,可以在不用修改代码和不影响性能的情况下控制PHP的运行环境。 PHPDBG的目标是成为一个轻量级、强大、易用的PHP调试平台。可以在PHP5.4和...

深入理解PHP原理之错误抑制与内嵌HTML分析

PHP提供了一个错误抑制符'@', 它是通过什么方式来阻止错误输出呢? 我又该在什么时候使用它呢? 这是这俩天一些网友提到的共同问题, 今天就索性整体回答下, 备后来人翻阅. PHP文件...

php上传图片生成缩略图(GD库)

首先来一段简单的php上传图片生成缩略图的详细代码,分享给大家供大家参考,具体内容如下 <?php function createThumbnail($imageDir...

jQuery+PHP+ajax实现微博加载更多内容列表功能

在一些微博网站上我们经常可以看到这样的应用,微博内容列表上并没有使用分页条,而是一次加载一定数量的记录显示在列表页,当用户浏览到列表页底部时,可以通过单击“查看更多”来加载更多记录。本文...

PHP程序61条面向对象分析设计的经验小结

(1)所有数据都应该隐藏在所在的类的内部。 (2)类的使用者必须依赖类的共有接口,但类不能依赖它的使用者。 (3)尽量减少类的协议中的消息。 (4)实现所有类都理解的最基本公有接口[例如...