PHP 一次循环合并两个有序数组
2019-05-11 本文已影响0人
MikeLue
php通过一层循环方式,合并两个有序数组算法
原理:
分别获取两个数组的元素个数和初始化当前索引值, 通过循环依次将两个数组的当前索引的元素值进行比较, 取得最小值, 将最小值所在的数组的当前索引+1, 然后进入下一次循环, 循环终止条件是两个数组都遍历完成.
具体代码如下(这里是先获取最小值);
<?php
// 测试数据
$a = [1,4,5,7,12];
$b = [2,3,6,8];
// 测试
$data = mergeSort($a,$b);
var_dump($data);
/**
* 合并有序数组
* @param array $arr1 有序数组arr1
* @param array $arr2 有序数组arr2
* @return array 合并后的有序数组
*/
function mergeSort($arr1,$arr2){
$arr = [];//定义最终数组容器
$arr1Num = count($arr1);//数组长度
$arr2Num = count($arr2);//数组长度
$i1 = 0;//数组1 的循环标记
$i2 = 0;//数组2 的循环标记
while($i1 < $arr1Num || $i2 < $arr2Num){//是否还需要合并
if($i1 < $arr1Num && $i2 < $arr2Num){//当两个数组都没有到达末尾,情况一
if($arr1[$i1] > $arr2[$i2]){//需要比较数组1和数组2,小的放入目标数组,并且标记+1
$arr[] = $arr2[$i2];
$i2++;
}else{
$arr[] = $arr1[$i1];
$i1++;
}
}elseif($i1 < $arr1Num && $i2 >= $arr2Num){//数组2 已经到达末尾,而数组1还为到达,情况二
$arr[] = $arr1[$i1];//直接把数组1的内容插入到目标数组中
$i1++;
}elseif($i2 < $arr2Num && $i1 >= $arr1Num){//数组1已经到达末尾,而数组2还未到达,情况三
$arr[] = $arr2[$i2];//直接把数组2的内容插入到目标数组中
$i2++;
}
}
return $arr;
}
```