抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

排序数组合并

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

上一题一样,很多人首先想到的办法是在A1中从头到尾复制数字,但这样就会出现多次复制 一个数字的情况。更好的办法是从尾到头比较A1和A2中的数字,并把较大的数字复制到A1的合适位置。

代码:

private static int[] mergeSort(int[] a1, int a1Len, int[] a2, int a2Len) {

//a1数组实际占用长度
int i = a1Len - 1;
//a2数组实际占用长度
int j = a2Len - 1;

//合并后数组实际占用长度
int end = a1Len + a2Len - 1;

while (i >= 0 && j >= 0) {
if (a1[i] >= a2[j]) {
//如果a1数组中未处理末尾的数大于或等于a2数组中未处理末尾的数,则将a1的该位置的数插入到a1数组末尾
a1[end--] = a1[i--];
} else {
//否则在a1数组末尾插入a2该位置的数
a1[end--] = a2[j--];
}
}

//如果数组a2中还有元素没有处理完,则全部依次插入到数组a1剩余位置(在前面移动位置后剩余的空位)
while (j >= 0) {
a1[end--] = a2[j--];
}

return a1;
}

测试main函数:

public static void main(String[] args) {
int[] a1 = new int[]{0, 11, 22, 33, 44, 55, -1, -1, -1, -1};
int[] a2 = new int[]{22, 33, 42, 52};

System.out.println(Arrays.toString(a1));

System.out.println(Arrays.toString(a2));

//传入拟定长度 在java中没有int数组元素为null的情况
int[] a3 = mergeSort(a1, 6, a2, 4);

System.out.println(Arrays.toString(a3));
}

0条评论

发表评论