JAVA:实现合并排序的 ArrayList算法(附完整源码)

package com.thealgorithms.datastructures.lists;
import java.util.ArrayList;
import java.util.List;
public class MergeSortedArrayList {

    public static void main(String[] args) {
        List<Integer> listA = new ArrayList<>();
        List<Integer> listB = new ArrayList<>();
        List<Integer> listC = new ArrayList<>();

        /* init ListA and List B */
        for (int i = 1; i <= 10; i += 2) {
            listA.add(i);
            /* listA: [1, 3, 5, 7, 9]  */
            listB.add(i + 1);
            /* listB: [2, 4, 6, 8, 10] */
        }

        /* merge listA and listB to listC */
        merge(listA, listB, listC);

        System.out.println("listA: " + listA);
        System.out.println("listB: " + listB);
        System.out.println("listC: " + listC);
    }

    /**
     * merge two sorted ArrayList
     *
     * @param listA the first list to merge
     * @param listB the second list to merge
     * @param listC the result list after merging
     */
    public static void merge(List<Integer> listA, List<Integer> listB, List<Integer> listC) {
        int pa = 0;
        /* the index of listA */
        int pb = 0;
        /* the index of listB */

        while (pa < listA.size() && pb < listB.size()) {
            if (listA.get(pa) <= listB.get(pb)) {
                listC.add(listA.get(pa++));
            } else {
                listC.add(listB.get(pb++));
            }
        }

        /* copy left element of listA to listC */
        while (pa < listA.size()) {
            listC.add(listA.get(pa++));
        }

        /* copy left element of listB to listC */
        while (pb < listB.size()) {
            listC.add(listB.get(pb++));
        }
    }
}

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
52
53
54
55
56
57
58
59