都已经排序好的两个数组。
把两个数组合并，那个算法对新数据做排序是最快的。
------解决方案--------------------------------------------------------
归并排序啊,这一步骤是O(n)的
原理其实很简单,你有两打排好的扑克,
你第一次次各抽一张,比较大小,把这两张放在桌子上.
然后再各抽一张,,比较大小,把这两张放在原先两张的两端.
重复上面步骤,直到有一打见底,把另一打直接放桌子上.
这就是Merge函数的原理.
需要开辟两个链表做这个事情.
------解决方案--------------------------------------------------------
各抽一张,是从最上面拿,不是从里边拿.
算法导论上有这段,有图的
public static void merge(ArrayList<Integer> A, int p, int q, int r) {
36. //length of the child array
37. int n1 = q - p + 1;
38. int n2 = r - q;
39. //create arrays L[1...n1 + 1] and R[1...n2 + 1]
40. ArrayList<Integer> L = new ArrayList<Integer>(n1 + 1);
41. ArrayList<Integer> R = new ArrayList<Integer>(n2 + 1);
42. for(int i = 0; i < n1; i ++) {
43. L.add(A.get(p + i));
44. }
45. L.add(max);
46.
47. for(int i = 0; i < n2; i ++) {
48. R.add(A.get(q + i + 1));
49. }
50. R.add(max);
51.
52. for (int i = 0, j = 0, k = p; k <= r; k ++) {
53. if (L.get(i) <= R.get(j)) {
54. A.set(k, L.get(i));
55. i ++;
56. } else {
57. A.set(k, R.get(j));
58. j ++;
59. }
60. }
61. }
------解决方案--------------------------------------------------------
时间复杂度cnlog2n + cn 为 O(nlog2n)
------解决方案--------------------------------------------------------