算法升级之路（二）

合并排序的数组

---

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
说明:

A.length == n + m

解法思路：
将b数组全部放入a数组中，然后直接排序

 public void merge(int[] A, int m, int[] B, int n) {
        
            for(int i =0;i<n;i++){
                A[m+i]=B[i];
            }
            Arrays.sort(A);
        

    }
1
2
3
4
5
6
7
8
9

解法思路
将两个数组循环比较放入新的数组中

• 易懂复杂版

 public void merge(int[] A, int m, int[] B, int n) {
        
         int[] arr = new int[m+n];
         int pa =0;
         int pb =0;
         int count =0;
         while(pb<n&&pa<m){
             if(A[pa]==B[pb]){
                 arr[count]=A[pa];
                 pa+=1;
                 count+=1;
                 arr[count]= B[pb];
                 pb+=1;
                 count+=1;
             }
            else if(A[pa]>B[pb]){
                   arr[count]=B[pb];
                  count+=1;
                  pb+=1;
             }
             else if(A[pa]<B[pb]){
                   arr[count]=A[pa];
                  count+=1;
                  pa+=1;

             }
         }
         if(pa==m){
           System.out.println(pb);

             for (int i =pb;i<n;i++){

                 arr[count] =B[i];
                 count+=1;
             }
         }else if(pb==n) {
                for (int i =pa;i<m;i++){               
                 arr[count] =A[i];
                  count+=1;
             }

         }
         
           for (int i = 0; i != m + n; ++i) {
            A[i] = arr[i];
        }


        

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

• 巧妙简洁版

 public void merge(int[] A, int m, int[] B, int n) {
        int pa = 0, pb = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (pa < m || pb < n) {
            if (pa == m) {
                cur = B[pb++];
            } else if (pb == n) {
                cur = A[pa++];
            } else if (A[pa] < B[pb]) {
                cur = A[pa++];
            } else {
                cur = B[pb++];
            }
            sorted[pa + pb - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            A[i] = sorted[i];
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20