java - 多线程

Question

我曾尝试在 Java 中创建一个并行快速排序，我认为这是一个幼稚的(因为我还没有研究接口(interface)执行器等)

我需要一种方法来在所有线程完成后打印排序数组..但我不知道我将提前拥有多少线程..所以我以等待的方式进行每次使用 join() 方法递归......所以第一个被调用的 join 方法必须等到所有其他线程完成......对吧？

这样，当我在 main()(打印数组的)中执行我的最后两行时，我可以确定我的所有线程都已完成...

所以我有两个问题..

1. 它是一个并行运行的多线程程序，对吧？还是我犯了一些错误，它实际上在一个线程一个线程之后以线性方式运行？

2. 我在 main 方法中显示排序数组的解决方案是否正确？

这是我的代码:

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> array = new ArrayList();
        //please assume that I have invoked the input for the array from the user 
        QuickSortWithThreads obj = new QuickSortWithThreads(array,0 ,array.size()-1 );
        for(int i = 0; i < array.size(); i++)
            System.out.println(array.get(i));
    }
}

public class QuickSortWithThreads {
    public QuickSortWithThreads(ArrayList <Integer> arr, int left, int right){  
        quicksort(arr, left, right);
    }

    static void  quicksort(ArrayList <Integer> arr, int left, int right)  {
        int pivot;

        if(left<right){
            pivot = partition(arr, left, right);    
            QuickSortThread threadLeftSide = new QuickSortThread(arr, pivot + 1, right);
            threadLeftSide.start();  
            quicksort(arr, left, pivot - 1);
            try {
                threadLeftSide.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }           
        }
    }

    static  int partition(ArrayList<Integer> arr, int left, int right)  {
        int pivot = arr.get(right);
        int i = left -1;
        for( int j = left; j <= right - 1; j++) {
            if (arr.get(j) <= pivot){
                i = i + 1;
                exchange(arr, i, j);
            }
        }
        exchange(arr, i + 1, right);
        return i + 1;
    }
    static void exchange(ArrayList<Integer> arr, int i, int j) {
        int swap = arr.get(i);
        arr.set(i, arr.get(j)); 
        arr.set(j, swap);
    }

    private static class QuickSortThread extends Thread {
        int right;
        int left;
        ArrayList<Integer> refArray; 

        public QuickSortThread(ArrayList<Integer> array, int left, int right) {
            this.right = right;
            this.left = left;
            refArray = new ArrayList<Integer>();
            refArray = array;   
        }

        public void run() {
            quicksort(refArray, left, right);
        }
    }
}

Answer 1

如果我们知道线程总数，我们可以使用 CountDownLatch用线程数初始化。但是由于我们不知道线程的数量，我们需要一个扩展的 CountDownLatch，它允许在创建后增加计数器。不幸的是，我们不能只扩展类 CountDownLatch，因为底层计数器是私有(private)的。一种方法是复制 CountDownLatch 的原始代码以访问底层计数器。不那么冗长的方法是扩展 Semaphore访问 reducePermits 方法，就像在 Reduceable Semaphore 中所做的那样.原则上，CountDownLatch 和 Semaphore 是类似的工具，但在内部计数器的解释上有所不同:前者计算否决，后者计算允许。

整个想法是在创建或启动线程时减少许可数，并在结束时释放许可，在方法 run() 的末尾。初始许可数为 1，因此如果没有线程启动，主程序可以自由结束。请注意，在 run() 方法开始时减少许可数量为时已晚。

要获得真正好的工作代码，您还需要使用具有固定线程数的线程池，并对小型数组进行串行排序。