Java：通过多线程并行化快速排序

使numThreads静态化可能会导致问题，在某些时候您最终可能会运行超过MAX_THREADS个。

您之所以无法获得完全双倍的性能，可能是因为您的快速排序无法完全并行化。请注意，对quicksort的第一次调用将在初始线程真正开始并行运行之前，在初始线程中对整个数组进行传递。当耕种到单独的线程时，以上下文切换和模式转换的形式并行化算法也存在开销。

看一下Fork / Join框架，这个问题可能很整洁。

关于实施的几点。实现可运行而不是扩展线程。仅当您创建一些新版本的Thread类时，才应使用扩展Thread。当您只想做一些可以并行运行的工作时，最好使用Runnable。在实现Runnable的同时，您仍然可以扩展另一个类，从而为您提供面向对象设计的更多灵活性。使用限制为您在系统中可用的线程数的线程池。也不要使用numThreads来决定是否派生新线程。您可以预先计算。使用最小分区大小，该大小是整个阵列的大小除以可用处理器的数量。就像是：

public class ThreadedQuick implements Runnable {    public static final int MAX_THREADS = Runtime.getRuntime().availableProcessors();    static final ExecutorService executor = Executors.newFixedThreadPool(MAX_THREADS);    final int[] my_array;    final int start, end;    private final int minParitionSize;    public ThreadedQuick(int minParitionSize, int[] array, int start, int end) {        this.minParitionSize = minParitionSize;        this.my_array = array;        this.start = start;        this.end = end;    }    public void run() {        quicksort(my_array, start, end);    }    public void quicksort(int[] array, int start, int end) {        int len = end - start + 1;        if (len <= 1) return;        int pivot_index = medianOfThree(array, start, end);        int pivotValue = array[pivot_index];        swap(array, pivot_index, end);        int storeIndex = start;        for (int i = start; i < end; i++) { if (array[i] <= pivotValue) {     swap(array, i, storeIndex);     storeIndex++; }        }        swap(array, storeIndex, end);        if (len > minParitionSize) { ThreadedQuick quick = new ThreadedQuick(minParitionSize, array, start, storeIndex - 1); Future<?> future = executor.submit(quick); quicksort(array, storeIndex + 1, end); try {     future.get(1000, TimeUnit.SECONDS); } catch (Exception ex) {     ex.printStackTrace(); }        } else { quicksort(array, start, storeIndex - 1); quicksort(array, storeIndex + 1, end);        }    }    }

您可以通过执行以下 *** 作开始：

ThreadedQuick quick = new ThreadedQuick(array / ThreadedQuick.MAX_THREADS, array, 0, array.length - 1);quick.run();

这将在同一线程中启动排序，从而避免了启动时不必要的线程跳跃。

警告：不确定上面的实现实际上会更快，因为我还没有对其进行基准测试。