Java 中的多线程快速排序比普通快速排序慢？

Question

我正在比较快速排序（正常，具有递归性）和线程快速排序（使用线程）。我知道 Normal-QuickSort 比 Threaded-QuickSort 快。这是正确的吗？感觉自己做错了什么。

代码如下：

public class QuickSort implements SortAlgorithm {
    public void Sort(Integer[] array) {
        Sort(array, 0, array.length-1);
    }

    private void Sort(Integer[] array, Integer low, Integer high) {
        if (low < high) {
            Integer pivot = partition(array, low, high);
            Sort(array, low, pivot-1);
            Sort(array, pivot+1, high);
        }
    }

    private Integer partition(Integer[] array, Integer low, Integer high) {
        Integer pivot = array[high];  
        Integer i = (low-1);
        for (Integer j=low; j<high; j++) 
            if (array[j] < pivot) { 
                i++; 
                Integer temp = array[i]; 
                array[i] = array[j]; 
                array[j] = temp; 
            } 

        Integer temp = array[i+1]; 
        array[i+1] = array[high]; 
        array[high] = temp; 

        return i+1; 
    }
}

public class ThreadsQuickSort extends Thread implements SortAlgorithm {
    private Integer low, high;
    private Integer[] array;

    public ThreadsQuickSort() {
        ;
    }
    
    public ThreadsQuickSort(Integer[] array, Integer low, Integer high) {
        this.array = array;
        this.low = low;
        this.high = high;
    }

    public void run() {
        Sort(array, low, high);
    }

    public void Sort(Integer[] array) {
        Sort(array, 0, array.length - 1);
    }

    private void Sort(Integer[] array, Integer low, Integer high) {
        if (low < high) {
            Integer pivot = partition(array, low, high);
            ThreadsQuickSort lowQSort = new ThreadsQuickSort(array, low, pivot - 1);
            lowQSort.start();
            ThreadsQuickSort highQSort = new ThreadsQuickSort(array, pivot + 1, high);
            highQSort.start();
            try {
                lowQSort.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            try {
                highQSort.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    private Integer partition(Integer[] array, Integer low, Integer high) {
        Integer pivot = array[high];  
        Integer i = (low-1);
        for (Integer j=low; j<high; j++) 
            if (array[j] < pivot) { 
                i++; 
                Integer temp = array[i]; 
                array[i] = array[j]; 
                array[j] = temp; 
            } 

        Integer temp = array[i+1]; 
        array[i+1] = array[high]; 
        array[high] = temp; 

        return i+1; 
    }
}

主函数使用两种算法对 10,000 项的数组进行排序并获取它们的执行时间。得到这个输出：

Single array sorted in 11 ms
The array was successfully sorted
Threaded array sorted in 6378 ms
The array was successfully sorted

我的问题是这是否编码正确并且输出符合预期。这与 Threaded-QuickSort 的实现无关。

Answer 1

每个线程~70 个微创建和切换。

线程总和应该在20000-1左右这给出了 20000 * 70us = 1400000us = 1400ms = 1.4s

所以接近预期。

Java 中的多线程快速排序比普通快速排序慢？

Multithread Quick Sort slower than normal Quick Sort in Java?

java

sorting

parallel-processing

multithreading

quicksort