PHP两个有序数组如何合并成一个有序数组

方法一 : 合并后排序（没有用到两个有序的特性）

   合并（array_merge），排序（冒泡、归并...）

方法二：插入排序（使用到了数字一个有序的特性，另一个有没有序无所谓）

   *时间复杂度O(nlogm),空间复杂度O(1)*

function insert($insert1, $insert2)
{
   $count1 = count($insert1);
   $count2 = count($insert2);
   $count = $count1 + $count2;
   if($insert1[$count1 - 1] < $insert2[0]) $insert1 = array_merge($insert1, $insert2);
   for($i = 0; $i < $count2; $i ++) {
       $tmp =  $insert2[$i];
       for($j = $count1 - 1; $j >= 0; $j --) {
           if($tmp < $insert1[$j]) {
               $insert1[$j + 1] = $insert1[$j];
               $insert1[$j] = $tmp;
               //$count > $count1 ++;
               $count1 ++;
           } else {
               continue;
           }
       }
   }
   return $insert1;
}

方法三：归并思想

    *时间复杂度O(m+n),空间复杂度O(1)*

function insert($insert1, $insert2)
{
    $count1 = count($insert1);
    $count2 = count($insert2);
    $count = $count1 + $count2;
    if($insert1[$count1 - 1] < $insert2[0]) $insert1 = array_merge($insert1, $insert2);

    $p1 = $count1 - 1;
    $p2 = $count2 - 1;
    $p = $count - 1;

    $tmp = [];
    while(($p1 >= 0) && ($p2 >= 0)) { 
        $tmp[$p--] = $insert1[$p1] > $insert2[$p2] ? $insert1[$p1--] : $insert2[$p2--];
    }

    return array_merge($tmp,$insert1,$insert2);
}

方法四，双层遍历，时间复杂度n^m