多线程快速排序不正确排序

Question

作为一个学校任务，我应该使用至少2个线程做一个多线程快速排序算法，但我的代码有一些问题，我似乎无法修复。

编辑：这是它看起来不是多线程时的样子。我已经证实这是有效的。

public class Sorter 
{ 
    private int[] mInts; 

    public void QuickSort() 
    { 
     QuickSort(mInts, 0, mInts.Length - 1); 
    } 

    public Sorter(int[] ints) 
    { 
     mInts = ints; 
    } 

    private int Partition(int[] ints, int left, int right) 
    { 
     int pivotIndex = (right + left)/2; 
     int pivotValue = ints[pivotIndex]; 

     Swap(ints, right, pivotIndex); 

     int storeIndex = left; 

     for (int i = left; i <= right - 1; i++) 
     { 
      if (ints[i] < pivotValue) 
      { 
       Swap(ints, storeIndex, i); 
       storeIndex++; 
      } 
     } 

     Swap(ints, storeIndex, right); 

     return storeIndex; 
    } 

    private void Swap(int[] ints, int x, int y) 
    { 
     int temp = ints[x]; 
     ints[x] = ints[y]; 
     ints[y] = temp; 
    } 

    private void QuickSort(int[] ints, int left, int right) 
    { 
     if (left < right) 
     { 
      int newIndex = Partition(ints, left, right); 


      QuickSort(ints, left, newIndex - 1); 
      QuickSort(ints, newIndex + 1, right); 
     } 
    } 

以上工作正常，下面的代码没有。现在它不能正确排序，而且在我看来，粗体代码片段必须位于其他地方...或其他东西？我很难理解线程编程，所以我希望有人能给我一些关于如何解决这个问题的指导，而不必在可能的情况下重构我的整个程序。以下是我用线程版本得到的多少。

public class Sorter 
{ 
    private int[] mInts; 

    Thread myThread = null; 
    int numThreads = 0; 
    int maxThreads = 10; 

    public void QuickSort() 
    { 
     QuickSort(mInts, 0, mInts.Length - 1); 
    } 

    public Sorter(int[] ints) 
    { 
     mInts = ints; 
    } 

    private int Partition(int[] ints, int left, int right) 
    { 
     int pivotIndex = (right + left)/2; 
     int pivotValue = ints[pivotIndex]; 

     Swap(ints, right, pivotIndex); 

     int storeIndex = left; 

     for (int i = left; i <= right - 1; i++) 
     { 
      if (ints[i] < pivotValue) 
      { 
       Swap(ints, storeIndex, i); 
       storeIndex++; 
      } 
     } 

     Swap(ints, storeIndex, right); 

     return storeIndex; 
    } 

    private void Swap(int[] ints, int x, int y) 
    { 
     int temp = ints[x]; 
     ints[x] = ints[y]; 
     ints[y] = temp; 
    } 

    private void QuickSort(int[] ints, int left, int right) 
    { 
     if (left < right) 
     { 
      int newIndex = Partition(ints, left, right); 

      if (numThreads < maxThreads) 
      { 
       numThreads++; 
       myThread = new Thread(new ParameterizedThreadStart(startSort)); 
       myThread.Start(new SortParameters(this, ints, left, newIndex - 1)); 
       **QuickSort(ints, newIndex + 1, right);** 
      } 
     } 
    } 

    static void startSort(Object obj) 
    { 
     SortParameters sortParams = (SortParameters)obj; 
     sortParams.instance.QuickSort(sortParams.ints, sortParams.left, sortParams.right); 
    } 

    public class SortParameters 
    { 
     public Sorter instance; 
     public int[] ints; 
     public int left; 
     public int right; 

     public SortParameters(Sorter instance, int[] ints, int left, int right) 
     { 
      this.instance = instance; 
      this.ints = ints; 
      this.left = left; 
      this.right = right; 
     } 
    } 
} 

感谢您的帮助！

Answer 1

问自己以下：

1. 多少个线程将用于n元素的顺序运行？
2. 这个数字在某种程度上受限于你的代码吗？
3. 达到此限制时会发生什么情况？

我在下面提供了我的解决方案，但您可能想先自己想想。

这里是我的答案：

1. Theorically，你的代码将计算日志（n）的快速排序，因为其划分分区后2子调用之间的每个分拣。在你的线程版本中，你为每个子调用启动一个补充线程，所以总共可以启动多个线程。

2. 您提供的代码实际上限制了maxThreads值的启动线程数。所以实际上，如果日志为（n）>maxThreads，即。如果n> 2 ^maxThreads，代码将达到可能的并发线程的最大数量。

3. 在线程代码中，突出显示的部分周围，对该最大值的测试会限制执行任何递归调用。因此，如果n高于第2点中提到的限制，代码将停止正常工作。

解决方法是很容易，添加一个else子句来完成整理了当前线程。

 if (numThreads < maxThreads) 
     { 
      numThreads++; 
      myThread = new Thread(new ParameterizedThreadStart(startSort)); 
      myThread.Start(new SortParameters(this, ints, left, newIndex - 1)); 
     } 
     else { 
      QuickSort(ints,left,newIndex - 1); 
     } 
     QuickSort(ints, newIndex + 1, right); 

正如你所看到的，我也搬出了测试将由当前线程反正运行的一部分。