189 8069 5689
今天小编给大家分享一下php如何实现并归排序的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。
我们提供的服务有：网站制作、成都网站建设、微信公众号开发、网站优化、网站认证、叶集ssl等。为超过千家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的叶集网站制作公司
php实现并归排序的方法：1、创建一个PHP示例文件；2、定义“public function handle(){...}”方法；3、通过“private function mergeSort($a, $lo, $hi) {...}”方法把数据逐步分解；4、通过“merge”方法对分解后的数据进行排序，再合并到一起即可。
php实现归并排序算法
归并排序算法的复杂度是O(nlogn)。
代码如下,只需要clone下来执行composer install然后执行 php artisan test:mergeSort 就可以看到结果了
/**
* 归并排序把数据逐步分解，然后对分解后的数据进行排序，最后合并到一起
*
* @return mixed
*/
public function handle()
{
$this->a = [3,70,4,38,5,6,8,4,7,10,6,10,34,4];
dump($this->a);
$a = $this->mergeSort($this->a, 0, count($this->a));
dd($a);
}
private function mergeSort($a, $lo, $hi) {
if (($hi - $lo) < 2) return [$a[$lo]];
$mi = ($lo + $hi) >> 1;
//把中点左边的进行归并
$b = $this->mergeSort($a, $lo, $mi);
dump('$b:',$b);
//把中点右边的进行归并
$c = $this->mergeSort($a, $mi, $hi);
dump('$c:',$c);
//把所有数据进行排序
return $this->merge($b, $c, $lo,$mi,$hi);
}
/**
* 假设有一个数组$a分成了两个数组[3,4] [2,8]
* 逐一比较，3and2，取出来2然后3and8取出来3然后4and8取出来4，最后取出来8
*
* @param [type] $lo
* @param [type] $mi
* @param [type] $hi
* @return void
*/
private function merge($b, $c, $lo, $mi, $hi) {
$lb = $mi - $lo; //$b数组的边界
$lc = $hi - $mi; //$c数组的边界
$res = [];
//$i表示合并后数组的下标 $ib是b数组的下标 $ic是c数组的下标
for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
//ib 下标没有越界 && c的数组已经空了也就是$ic >= $lc || 比较两个数组首位的大小 如果b的首元素 < c的首元素，那么取出来b的首元素
if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
$res[$i++] = $b[$ib++];
}
//k 下标没有越界 && b的数组已经空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那么取出来c的首元素
if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
$res[$i++] = $c[$ic++];
}
}
return $res;
}
归并排序和快排刚好相反，是先将整个数组左右打散，然后在逐一合并进行排序，最终完成整个数组的排序，排序示意图如下：
.jpg)
首先将整个数组左右打散，变成单个元素，因为单个元素可以被认为是有序的。
对应代码
if (($hi - $lo) < 2) return [$a[$lo]];
$mi = ($lo + $hi) >> 1;
//把中点左边的进行归并
$b = $this->mergeSort($a, $lo, $mi);
dump('$b:',$b);
//把中点右边的进行归并
$c = $this->mergeSort($a, $mi, $hi);
dump('$c:',$c);
接下来对左右两个有序数组进行排序，假设有一个数组$a分成了两个数组[3,4] [2,8]，逐一比较，3and2，取出来2然后3and8取出来3然后4and8取出来4，最后取出来8，对应代码：
$lb = $mi - $lo; //$b数组的边界
$lc = $hi - $mi; //$c数组的边界
$res = [];
//$i表示合并后数组的下标 $ib是b数组的下标 $ic是c数组的下标
for($i = 0,$ib=0,$ic=0;$ib<$lb || $ic < $lc;){
//ib 下标没有越界 && c的数组已经空了也就是$ic >= $lc || 比较两个数组首位的大小 如果b的首元素 < c的首元素，那么取出来b的首元素
if ($ib < $lb && ( $ic >= $lc || $b[$ib] <= $c[$ic])) {
$res[$i++] = $b[$ib++];
}
//k 下标没有越界 && b的数组已经空了也就是$ib >= $lb || 如果c的首元素 < b的首元素，那么取出来c的首元素
if ($ic < $lc && ($ib >= $lb || $b[$ib] > $c[$ic])) {
$res[$i++] = $c[$ic++];
}
}
return $res;
示意图如下：
.jpg)
以上就是“php如何实现并归排序”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注创新互联行业资讯频道。