難以在c＃中實現快速排序

Question

我在嘗試使此快速排序算法工作100％時遇到了一些麻煩。到目前爲止，當它試圖交換兩個相同的數字（試圖補救，就像你會在代碼中看到的那樣）時，它會變得越來越多。

該死的事情幾乎在那裏。我只是不確定我錯過了什麼。我花了幾個小時試圖弄清楚它無濟於事。因爲我在做泛型（額外的功勞），他只能在C＃中抽取字符串或整數（他主要是一個Java /平臺），但是我的老師說他不能幫助我， C++老師......他還沒有和c＃一起工作很長時間）。

快速排序靜態類

class QuickSort<T> where T : IComparable<T> 
{ 
    //No variables or properties, more of a helper class 

    //This is the method that will be called by the user. 
    //It ties the internal methods into one to sort the 
    //array. It needs an array passed into it, As well as 
    //the size of the array. 
    public static void QSort(T[] array,int size) 
    { 
     //If array is empty, or has 1 element, it is sorted. 
     //Return immediatly. 
     if (size == 1 || size == 0) 
     { return; } 
     else 
     { 
      //Time to sort, pass in the array, the left bounds of 0, 
      //and the right bounds of high - 1 (the last element). 
      Partition(array, 0, size); 
     } 
    } 

    //This method splits the work area in half, putting lower 
    //values left of the pivot, and greater values right of 
    //the pivot. 
    private static void Partition(T[] array, int lower, int upper) 
    { 
     //If upper is less 1, then there is no 
     //sorting that can be done. 
     if ((upper - lower) < 2) 
     { return; } 

     //Get the right bound -1, to make sure it stays 
     //within actual array bounds 
     int left = lower; 
     int right = upper-1; 

     //Set pivot to equal the middle most array. I used this 
     //expression because wikipedia mentions it will stop 
     //overflow and invalid pivot position that can come 
     //with exceptionally large arrays using the basic 
     //(a+b)/2 equation. 
     int pivot_index = left + (right - left)/2; 
     T pivot = array[pivot_index]; 

     while (left < right) 
     { 
      //array[left] < pivot 
      while ((array[left].CompareTo(pivot) <= 0) && (left < right)) 
      { 
       left++; 
      } 
      //array[right] > pivot 
      while ((array[right].CompareTo(pivot) >= 0)&& (left < right)) 
      { 
       right--; 
      } 


      if (left != right) 
      { 
       Swap(array, left, right); 
       left++; 
       right--; 
      } 
     } 

      //Send in the lower bound, and the pivot point. 
      Partition(array, lower, right); 

      //Send in the pivot point as lower bound, and upper 
      Partition(array, right+1, upper); 

    } 


    //This method simply swaps the first position with the second. 
    private static void Swap(T[] array, int position1, int position2) 
    { 
     T tempHolder = array[position1]; 
     array[position1] = array[position2]; 
     array[position2] = tempHolder; 
    } 

} 

主要類

class Tester 
{ 
    static void Main(string[] args) 
    { 

     ContiguousList<int> tester = new ContiguousList<int>(100); 
     Random rand = new Random(5433); 
     for (int ii = 0; ii < tester.Size; ii++) 
     { 
      tester.SetElement(ii, rand.Next(0, 100)); 
     } 

     for (int ii = 0; ii < tester.Size; ii++) 
     { 
      Console.WriteLine(tester.GetElement(ii).ToString()); 
     } 
     Console.WriteLine(); 



     tester.Sort(); 
     for (int ii = 0; ii < tester.Size; ii++) 
     { 
      Console.WriteLine(tester.GetElement(ii).ToString()); 
     } 



    } 
} 

它證明了我相當困難，因爲我可以按照唯一的網上實現要麼用於C++（找到一個很好的僞碼的解釋會如果我可以使用指針> <）或者它們僅用於排序整數。

我想也許交換丟失，或者我的邏輯處理數組[左] ==數組[右]是錯誤的。

（呵呵，不介意在主要的ContiguousList事情......我們的老師把我們編寫我們自己的智能陣列，叫我們使用，所以我們可以看到陣列有多聰明的工作。）

感謝任何幫助的人。我的大腦真的難倒了這個。

- 編輯 我改變了循環，所以一個檢查> = 0，另一個< 0擺脫非必要的檢查。

- 編輯 我再次調整了一下，現在看起來它已經差不多排序了，但並不完全，我的前10個元素是1,1,2,3,2,3,6,5,4， 5所以不知何故，當值相同時，某些東西沒有正確地交換。

編輯 - 只是重新讀取我使用的quicksort解釋/僞代碼，並注意到一點「這個版本將只適用於具有獨特元素的數組」警告..​​....所以我是對的，因爲它當2個元素保持相同的值時，必須要做的事情是，某些東西不能正常工作......不知道如何修復它。 <

Answer 1

由於第一個循環，左側元素不能小於主元。由於第二個循環，正確的元素不能超過樞軸。因此，如果它們相等，那麼它們必須等於主軸，因此它們最終排列在哪個陣列中並不重要。

無論如何，我認爲您需要做的所有修復代碼的方法是稍微調整這些行：

 if (array[left].CompareTo(array[right]) == 0) 
     { 
      left++; 
      right--; 
     } 
     else if (left != right) 
     { 
      Swap(array, left, right); 
      left++; 
      right--; 
     } 

但有幾個簡化的：

1. 因爲left == right意味着array[left].CompareTo(array[right]) == 0)，你left != right測試是多餘的。
2. 作爲一個推論，你總是最終增加左邊和右邊遞減。所以你可以把它移到條件之外。

因此產生的代碼看起來是這樣的：

 if (array[left].CompareTo(array[right]) != 0) 
     { 
      Swap(array, left, right); 
     } 
     left++; 
     right--; 

Answer 2

你應該改變你的交換方式交換，而不是訪問陣列中的實際數據。在C＃中，您需要'ref'，所以任何數據都作爲參考發送：

private static void Swap(ref T a, ref T b) 
    { 
     T temp = a; 
     a = b; 
     b = temp; 
    }