/*
* 递归之归并排序
* 归并排序就是将两个有序的数组,合到一起,得到一个新的有序数组的过程
* 算法分析:首先拿a的第一个元素跟b的第一个元素比较,a的大,那么把b的元素放到新的数组c上
* 然后再拿a的第一个元素跟b的第二个元素比较,a的元素小,那么就把a的第一个元素放到数组c上
* 依次类推:当组数a的所有元素都被放到c中时,可以直接把b中剩下的元素直接放到c中,反之同理
*/
public class RecursiveMerge {
public static void main(String[] args) {
int[] a = {3,5,7,9,18,20,25,28,30,54,67,87,98};
int[] b = {2,4,6,7,9,12,15,17,19,23,26,67};
int[] c = new int[a.length + b.length];
merge(a, b, c);
for(int cv : c){
System.out.print(cv +",");
}
}
private static void merge(int[] a, int[] b, int[] c){
int ai = 0; int bi = 0; int ci = 0;
//当数组a或者数组b中有一个数组的数据已经被merge完了的时候,退出循环
while(ai < a.length && bi < b.length){
if(a[ai] > b[bi]){
c[ci++] = b[bi++];
}else{
c[ci++] = a[ai++];
}
}
//如果是b数组merge完了,那么把a数组剩下的元素放进去
while(ai < a.length){
c[ci++] = a[ai++];
}
//如果是a数组merge完了,那么把b数组剩下的元素放进去
while(bi < b.length){
c[ci++] = b[bi++];
}
}
}
//运行结果如下:
2,3,4,5,6,7,7,9,9,12,15,17,18,19,20,23,25,26,28,30,54,67,67,87,98,