【php】PHP 归并排序（Merge Sort）

• Z时代
• 2024-01-10
• 分类：技术分享

​归并排序 时间复杂度属于 O(nlogn) 级别的，相比于 O(n^2) 级别的排序算法，在处理大的数据量时，它的优势非常明显，下面通过原理图和代码演示介绍归并排序是如何实现 O(nlogn) 时间复杂度级别的。

1.将数组中有序的两部归并成一个过程原理图

在学习 归并排序 之前，先学习一下使用临时空间将数组中有序的两个部分归并成一个有序部分的原理图

合并代码如下：

<?php
function twoMergeSort($arr,$left,$mid,$right){
$aIndex = $left==$mid ? -1 : $left;
$bIndex = $mid==$right ? -1 : $mid;
$crr = [];
while (($aIndex >= $left && $aIndex < $mid) || ($bIndex >= $mid && $bIndex <= $right)){
$aValue = $arr[$aIndex]??null;
$bValue = $arr[$bIndex]??null;
if(($aIndex < $left || $aIndex >= $mid) || ($bValue < $aValue && $bValue != null)){
$crr[] = $bValue;
$bIndex++;
}else{
$crr[] = $aValue;
$aIndex++;
}
}
for ($i = 0;$i < ($right - $left);$i++){
$arr[$i+$left] = $crr[$i];
}
return $arr;
}
$arr = [1,4,7,10,15,8,11,13,19,24];
print_r(twoMergeSort($arr,0,5,9));
/**
Array
(
[0] => 1
[1] => 4
[2] => 7
[3] => 8
[4] => 10
[5] => 11
[6] => 13
[7] => 15
[8] => 19
[9] => 24
)
*/

2. 无序数组分解示意图

可以使用递归二分的思想把一个无序的数组分解为多个单元素的数组（单元素数组也可以看做有序数组）

3.归并排序代码

<?php
class MergeSort
{
/**
* 将数组两个有序部分合并成一个
* @param $arr
* @param $left
* @param $mid
* @param $right
* @return mixed
*/
private function twoMergeSort($arr,$left,$mid,$right){
$aIndex = $left==$mid ? -1 : $left;
$bIndex = $mid==$right ? -1 : $mid;
$crr = [];
while (($aIndex >= $left && $aIndex < $mid) || ($bIndex >= $mid && $bIndex <= $right)){
$aValue = $arr[$aIndex]??null;
$bValue = $arr[$bIndex]??null;
if(($aIndex < $left || $aIndex >= $mid) || ($bValue < $aValue && $bValue != null)){
$crr[] = $bValue;
$bIndex++;
}else{
$crr[] = $aValue;
$aIndex++;
}
}
for ($i = 0;$i < ($right - $left);$i++){
$arr[$i+$left] = $crr[$i];
}
return $arr;
}
public function arrayMergeSort($arr){
$this->recursionMergeSort($arr,0,count($arr) - 1);
return $arr;
}
private function recursionMergeSort($arr,$left,$right){
if($left == $right){
return;
}
$mid = ceil((($right - $left)/2) + $left);//($right + $left)/2 这种考虑内存溢出的优化
$arr = $this->recursionMergeSort($arr,$left,$mid-1); //递归思想，交给下层处理排序
$arr = $this->recursionMergeSort($arr,$mid,$right);//递归思想，交给下层处理排序
$arr = $this->twoMergeSort($arr,$left,$mid,$right);//merge 两部有序内容
return $arr;
}
}

4.演示输出代码如下

<?php
//require 'merge_arr.php';
require 'MergeSort.php';
$mergeSort = new MergeSort();
print_r($mergeSort->arrayMergeSort([1,3,2,4,5,9,6,7,8]));

如下图所示:

5. O(nlogn) 和 O(n^2) 时间复杂度简单对比

代码仓库 ：https://gitee.com/love-for-po...

扫码关注爱因诗贤

以上是 【php】PHP 归并排序（Merge Sort） 的全部内容， 来源链接： utcz.com/a/104916.html