合併兩個有序數組

題目：有兩個排序的數組A和B，數組A剩餘的空間剛好夠容納B，請實現一個函數，把B中的所有數字插入到A中並且所有的數都是排序的。

很多人一開始的想法就是簡單的插入，足夠暴力，在A中直接從頭到尾遍歷，找到合適的位置就移動後面所有的元素，讓出一個位填補新插入的數，這種做法是效率最低的。

反其道而行之，更好的辦法是從尾開始比較A和B中的數字，把較大的數字複製到A的末尾。

這種解決方法同樣可以運用到字串替換中去，如果要將字串中的空格替換成“%20”（在網絡編程中，URL中如果包含空格、“#”等特殊字符，可能導致在伺服器端無法正確解析，所以需要進行轉換，轉換規則為在'%'後面加上ASCII碼的兩位十六進位表示。制就是20，那就是轉換成%20。從尾開始複製，遇到空格就替換，可以有效減少移動次數。

數組合併的程式碼如下：

<?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);

版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。

以上就介紹了合併兩個有序數組，包括了方面的內容，希望對PHP教程有興趣的朋友有所幫助。