使用线程对 Java 中的 ArrayList 进行排序

Question

我想使用线程二叉树对 Java 中的 ArrayList 进行排序。问题如下：

The main method creates the first node passing a randomly generated list. Every node behaves the same way. If the list has 0 or 1 elements, it returns. Otherwise, it creates two new nodes passing them the two halfes of the list. Once the child nodes have sorted their lists, the parent node merges them keeping them sorted.

这是我到目前为止编写的代码...
但我无法让它工作！它继续打印最后未排序的列表。
非常感谢您。

Main.java

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        Random rnd = new Random();
        List<Integer> list = new ArrayList<Integer>();
        int size = rnd.nextInt(90) + 1 + 10;

        for (int i = 0; i < size; i++) {
            list.add(rnd.nextInt(100));
        }

        Node n = new Node(list);
        n.start();

        try {
            n.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("The sorted list:\n" + list.toString());
    }
}

Node.java

import java.util.ArrayList;
import java.util.List;

public class Node extends Thread {
    private List<Integer> list;

    public Node(List<Integer> list) {
        this.list = list;
    }

    public void run() {
        if (list.size() <= 1)
            return;

        List<Integer> l1, l2;
        l1 = new ArrayList<Integer>();
        l2 = new ArrayList<Integer>();
        add(l1, 0, list.size() / 2);
        add(l2, list.size() / 2, list.size());

        Node a, b;
        a = new Node(l1);
        b = new Node(l2);
        a.start();
        b.start();

        try {
            a.join();
            b.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        merge(l1, l2);
    }

    private void add(List<Integer> l, int from, int to) {
        l.addAll(list.subList(from, to));
    }

    private void merge(List<Integer> l1, List<Integer> l2) {
        list = new ArrayList<Integer>();
        int size1 = l1.size();
        int size2 = l2.size();

        int i1 = 0, i2 = 0, n1, n2;
        while (i1 < size1 && i2 < size2) {
            n1 = l1.get(i1);
            n2 = l2.get(i2);

            if (n1 <= n2) {
                list.add(n1);
                i1++;
            } else {
                list.add(n2);
                i2++;
            }
        }

        while (i1 < size1) {
            list.add(l1.get(i1++));
        }

        while (i2 < size2) {
            list.add(l2.get(i2++));
        }
    }
}

Answer 1

您没有看到处于合并状态的原始 List，因为您在 merge() 方法中做的第一件事就是丢弃您持有的原始 [=11] 的引用=]:

private void merge(List<Integer> l1, List<Integer> l2) {
    list = new ArrayList<Integer>();
    ...

排序数据的所有实际合并都发生在您创建的新 List 中，但是您在 main() 方法中打印原始的、未排序的 List .

您需要对原始 List 的元素进行排序，或者 return 以某种方式对（新）排序的元素进行排序。

使用线程对 Java 中的 ArrayList 进行排序

Sorting an ArrayList in Java using Threads

java

sorting

multithreading

binary-tree

arraylist