java - 多线程 QuickSort 比普通 QuickSort 花费更长的时间

Question

我已经使用多线程实现了快速排序，它正确地对整数数组进行了排序，但是它比普通的快速排序需要更长的时间来执行。例如，对 10000 个整数进行排序多线程:6856 毫秒正常:1毫秒

我不知道我的代码有什么问题。

public void run()
{
    quickSort1(this.Array,this.low,this.high);
}
int partition(int[]A,int l,int r)
  {
    int v = A[r];
    int i = l;
    int j = r;

    while(i<j)
    {
        while(A[i]<v)
        {
            i++;
        }

        while((i<j)&&(A[j]>=v))
        {
            j--;
        }

        if(i<j)
        {
            int C = A[i];


            A[i] = A[j];
            A[j] = C;
        }

        else
        {
            int D = A[i];

            A[i] = A[r];
            A[r] = D;
        }
    }


    return i;
}



void quickSort1(int[] A,int l,int r)
{
    int i;
    if(r>l)
    {
        i = partition(A,l,r);

        quickSort sort1 = new quickSort(A,l,i-1);
        Thread t1 = new Thread(sort1);


        quickSort sort2 = new quickSort(A,i+1,r);
        Thread t2 = new Thread(sort2);
        t1.start();
        t2.start();

        try
        {
            t1.join();
            t2.join();
        }catch(Exception e){}



    }
}

void normal_quickSort(int[] A,int l,int r)
{

    int i;
    if(r>l)
    {
        i = partition(A,l,r);

        normal_quickSort(A,l,i-1);
        normal_quickSort(A,i+1,r);
    }
}

Answer 1

两个问题，

(1) 您创建的线程过多。创建线程是昂贵的。对于计算密集型任务，如果您创建的线程总数大于平台中的 CPU 数量，则可能是错误的。

诀窍是将线程池化。 (例如，创建一个 java.util.concurrent.ThreadPoolExecutor，并给它任务来执行)。

(2) 您将工作分解为太小的任务。同步线程和在线程之间传递数据也很昂贵。几乎没有创建和销毁线程那么昂贵，但是您想要执行它的次数仍然有限制。

您的算法可能会将工作划分为您为线程提供一个 元素列表并要求线程对其进行“排序”的位置。对于多线程来说，这是一个小得可笑的任务。

要实现快速排序，您必须不断将数组分成越来越小的 block ，但您不必将每个 block 交给不同的线程，并且在它们变得足够小之后，您不应该这样做。我不知道多小才算足够小(100？1000？10,000？)，但您可以轻松地通过实验找出答案。