有趣的Java算法(3)

给定两个排序后的数组A和B,其中A的末端有足够的空间容纳B,编写一个方法将B合并到A并排序

       拿到这个题后，最直接的想法就是比较A和B中的元素，并按顺序插入数组，直到遍历完A和B中的所有元素。但是这样做会有一个不好的地方：如果元素的插入位置在数组A的前端，那就必须将原来的数组往后移动。这会增加开销。但是我们可以使用另外的一种办法将元素插入数组A的末端。这样我们不会出现元素移动的情况！代码如下

 /*
	 * lastA:a中的实际元素数  lastB:b中的实际元素数 mergeIndex是新数组的实际空间大小
       */
      public static void mergeOrder(int[] a, int[] b, int lastA, int lastB) {
		int indexA = lastA - 1; 
		int indexB = lastB - 1;
		int mergeIndex = lastA + lastB - 1; 
		while (indexA >= 0 && indexB >= 0) {
			if (a[indexA] > b[indexB]) {
				a[mergeIndex] = a[indexA];
				mergeIndex --;
				indexA --;
			} else {
				a[mergeIndex] = b[indexB];
				mergeIndex --;
				indexB --;
			}
		}
		
		while (indexB >= 0) {
			a[mergeIndex] = b[indexB];
			mergeIndex --;
			indexB --;
		}
	}