大佬教程收集整理的这篇文章主要介绍了PHP 实现归并排序(Merge Sort),大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
归并排序
时间复杂度属于 O(nlogn)
级别的,相比于 O(n^2)
级别的排序算法,在处理大的数据量时,它的优势非常明显,下面通过原理图和代码演示介绍归并排序是如何实现 O(nlogn)
时间复杂度级别的。
在学习 归并排序
之前,先学习一下使用临时空间
将数组中有序的两个
部分归并成一个
有序部分的原理图
合并代码如下:
<?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
)
*/
可以使用递归二分的思想把一个无序的数组分解为多个单元素的数组(单元素数组也可以看做有序数组)
<?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;
}
}
<?PHP
//require 'merge_arr.PHP';
require 'MergeSort.PHP';
$mergeSort = new MergeSort();
print_r($mergeSort->arraymergeSort([1,3,2,4,5,9,6,7,8]));
如下图所示:
扫码关注爱因诗贤
以上是大佬教程为你收集整理的PHP 实现归并排序(Merge Sort)全部内容,希望文章能够帮你解决PHP 实现归并排序(Merge Sort)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。