Merge two sorted arrays

Question: There are two sorted arrays A and B. The remaining space of array A is just enough to accommodate B. Please implement a function to insert all the numbers in B into A and all the numbers are sorted.

Many people’s initial idea is to simply insert, which is violent enough. They traverse A directly from beginning to end. When they find a suitable position, they move all the following elements to make room for a bit to fill in the newly inserted number. This kind of The approach is the least efficient.

Instead of doing the opposite, a better way is to compare the numbers in A and B starting from the end, and copy the larger number to the end of A.

This solution can also be applied to string replacement. If you want to replace the spaces in the string with "%20" (in network programming, if the URL contains spaces, "#", etc. Special characters may not be correctly parsed on the server side, so they need to be converted. The conversion rule is to add the two-digit hexadecimal representation of the ASCII code after '%'. For example, the ASCII code of a space is 32, so hexadecimal. The system is 20, that is, converted to %20. ). If you traverse from beginning to end to insert, the number of times the string will be moved will be many. Then If you know the number of spaces from the beginning, apply for more memory for the string, and then Start copying from the end and replace when encountering spaces, which can effectively reduce the number of moves.

The code for array merging is as follows:

<?php
/*
$data1 数组A
$data2 数组B
$num1  数组A的有效元素个数
*/
function merge(&$data1,$data2,$num1)
{
	$total=count($data1);
	$num2=count($data2);
	while($num1>0&&$num2>0)
	{
		if($data1[$num1-1]>$data2[$num2-1])
		{
			$data1[$total-1]=$data1[$num1-1];
			$total--;
			$num1--;
		}
		else
		{
			$data1[$total-1]=$data2[$num2-1];
			$total--;
			$num2--;
		}
	}
	if($num2>0)
	{
		while($total>0&&$num2>0)
		{
			$data1[$total-1]=$data2[$num2-1];
			$total--;
			$num2--;
		}
	}
}

$a=array(1,3,5,7,9,0,0,0,0,0);
$b=array(2,4,6,8,10);
merge($a,$b,5);
print_r($a);

Copyright Statement: This article is an original article by the blogger and may not be reproduced without the blogger's permission.

The above introduces the merging of two ordered arrays, including the relevant aspects. I hope it will be helpful to friends who are interested in PHP tutorials.