题目

有两个排序的数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入到A1中并且所有的数字是排序的。

解题思路

从尾到头比较A1和A2中的数字，比较大的数字复制到A1数组的最后一个未替换的位置

实现代码

/** *  */package com.jason.interviewQuestions.basicKnowledge;/** * 有两个排序的数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入到A1中并且所有的数字是排序的。 * @author jason zhang * */public class InsertSortedArray {	public void insertSortedArray(int[] a1, int[] a2, int a1OriginalLength) {		if (a1 == null || a2 == null || a1OriginalLength <= 0) {			return;		}		int indexOfOriginalA1 = a1OriginalLength - 1;		int indexOfA2 = a2.length - 1;		int indexOfA1 = a1.length - 1;		while (indexOfA2 >= 0) {			if (a2[indexOfA2] >= a1[indexOfOriginalA1]) {				a1[indexOfA1--] = a2[indexOfA2--];			} else {				a1[indexOfA1--] = a1[indexOfOriginalA1--];			}		}	}}

测试代码

package com.jason.interviewQuestions.basicKnowledge;import junit.framework.TestCase;public class InsertSortedArrayTest extends TestCase {	private InsertSortedArray isa;	protected void setUp() throws Exception {		super.setUp();		this.isa = new InsertSortedArray();	}	public void testInsertSortedArray() {		int[] a1 = {1,3,8,9,11};		int[] a2 = {2,5,10,12};		int[] newA1 = new int[(a1.length + a2.length)];		System.arraycopy(a1, 0, newA1, 0, a1.length);		this.isa.insertSortedArray(newA1, a2, a1.length);		for (int i=0; i