某校2017专硕编程题-将2个序列合并成一个有序序列

某校2017专硕编程题-将2个序列合并成一个有序序列

问题

输入一个有序数列，设计算法将2个序列合并成一个有序序列

分析

方法1 最简单的思路应该是将2个序列，重新放到1个新序列中对新序列选择一种排序方法进行排序。

方法2 先找到 a 序列中元素正确的索引位置，比如 a序列的 元素a1 在新序列中的位置是 3 那么就先将 a1 放到 3的位置上，这样依次将a序列全部放到正确的位置上，接着把空白的部分按顺序将b序列放上去。 下面拿2个序列举例说一下如何将a序列正确的放到索引上： 序列a : 1 3 5 7 9 序列b: 2 4 6 8 10 如： a中元素1的当前位置是0，然后和b序列的值比较，新序列的位置还是0 a中元素2的当前位置是1，然后和b序列的值比较，新序列的位置是0+1 … 若重复元素出现导致位置被占，进行冲突检测，让其向后移动一位，直到出现空值

方法3 利用指针的思路，指针分别指向两个序列的头部，对两个指针的值进行比较。较小的值输出，指针后移，较大的值进行下一次比较。

Java实现

方法1不进行实现

方法2

//假设2个序列是递增的 public static int[] merge(int[] a,int[] b){ int[] c = new int[a.length+b.length]; //找到a序列重新排列后的索引 for (int i = 0; i < a.length; i++) { int k = i; for (int j = 0; j < b.length; j++) { if (a[i] > b[j]) k += 1; else break; } while (c[k] != 0) k++; c[k] = a[i]; } //将b序列填充到空白出 int k = 0; for (int i = 0; i < c.length; i++) { if (c[i] == 0) c[i] = b[k++]; } return c; }

时间复杂度：O(n^2)空间复杂度：O(n)

方法3

public static void merge2(int[] a, int[] b){ if (a == null || b == null ) return; int n = 0; int m = 0; while (m < a.length || n < b.length){ if (m == a.length) { System.out.print(b[n++]+" "); continue; } if (n == b.length){ System.out.print(a[m++]+" "); continue; } if (a[m] < b[n]) System.out.print(a[m++]+" "); else System.out.print(b[n++]+" "); } }

时间复杂度：O(n）空间复杂度：O(1)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。