赛车传奇插曲,谷幸仪,曹妃甸教师招聘
给定两个排序后的数组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 --;
}
}
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!!
点击进行留言回复
网友评论