多線程快速排序不正確排序

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); 

正如你所看到的，我也搬出了測試將由當前線程反正運行的一部分。