如何修改我的快速排序算法，以便它可以對Double數據類型數組進行排序？

我使用這種快速排序算法對整數數組進行排序，但我也希望它對排序數組進行排序。我需要改變哪些變量才能完成這項工作？我試着改變許多不同的數據類型組合。如何修改我的快速排序算法，以便它可以對Double數據類型數組進行排序？

任何幫助表示讚賞。

 static void Main(string[] args) 
    { 

    double[] myArray_3 = { 25.1573, 5.1437, 8.1421, 3.1625, 12.3187, 2.8465, 78.0454, -32.6666, - 
    51.9204, -31.9391, -30.6136, -12.1411, -4.7172, -6.1189, 15.1574, 10.8995, 21.0344, 49.7912}; 
    double[] myArray_4 = {-56.6149, -27.4997, 17.1503, -1.5368, -31.3245, -17.5386, 6.9865, -27.8045, 
    27.2986, -17.9399, 50.6482, -30.2363, 5.5773, -42.5887, -20.2617, -16.6110, 11.2374, 
    26.3797, 8.4136, -10.4460, 22.8337, 22.3688, 3.3657, 15.9949, 11.5583, -27.6349, 21.2679, - 
    18.4016, -16.9097, 4.9545, -8.6101, -3.6910}; 

     QuickSort(myArray_3); 

     foreach (int item in myArray_3) 
     { 
      Console.WriteLine(item); 
     } 

    } 
    public static void QuickSort(int[] data) 
    { 
     Quick_Sort(data, 0, data.Length - 1); 
    } 

    public static void Quick_Sort(int[] data, int left, int right) 
    { 
     int i, j; 
     int pivot, temp; 
     i = left; 
     j = right; 
     pivot = data[(left + right)/2]; 
     do 
     { 
      while ((data[i] < pivot) && (i < right)) i++; 
      while ((pivot < data[j]) && (j > left)) j--; 
      if (i <= j) 
      { 
       temp = data[i]; 
       data[i] = data[j]; 
       data[j] = temp; 
       i++; 
       j--; 
      } 
     } while (i <= j); 
     if (left < j) Quick_Sort(data, left, j); 
     if (i < right) Quick_Sort(data, i, right); 
    }

來源

2017-05-04 Ulfren

您可能會考慮使'Quick_Sort（）'爲類型約束爲IComparable <>'的通用方法。例如'公共靜態無效Quick_Sort （T []的數據，詮釋左，右詮釋），其中T：IComparable的 {...}'然後你可以使用'數據[I] .CompareTo（支點）'或任何代替'<' and '> '運營商。 ints和double都實現了'IComparable <>'，所以它將適用於這兩者，再加上實現該接口的其他任何東西。 – itsme86

您應該能夠使用泛型，那裏的類型實現IComparable<T>，這樣就可以比較的物品（你不能使用泛型類型<或>運營商）。

這應該做的伎倆：

public static void QuickSort<T>(T[] data) where T:IComparable<T> 
{ 
    Quick_Sort(data, 0, data.Length - 1); 
} 

public static void Quick_Sort<T>(T[] data, int left, int right) where T:IComparable<T> 
{ 
    int i, j; 
    T pivot, temp; 
    i = left; 
    j = right; 
    pivot = data[(left + right)/2]; 

    do 
    { 
     while ((data[i].CompareTo(pivot) < 0) && (i < right)) i++; 
     while ((pivot.CompareTo(data[j]) < 0) && (j > left)) j--; 
     if (i <= j) 
     { 
      temp = data[i]; 
      data[i] = data[j]; 
      data[j] = temp; 
      i++; 
      j--; 
     } 
    } while (i <= j); 

    if (left < j) Quick_Sort(data, left, j); 
    if (i < right) Quick_Sort(data, i, right); 
}

來源

2017-05-04 22:50:16

我發現itsme86基本上在寫評論的時候比在Visual Studio中修改代碼的時間更少。不錯的工作！ –

謝謝，這解決了我的問題^^它正在排序正確，但現在它不顯示與他們的小數值的數字，我怎樣才能打印出所有的4位小數的數組數組？（是的，我是一個noob）。 – Ulfren

那麼，在你的'foreach'代碼中，你將所有項目從'double'轉換爲'int'。不要這樣做。 :)它應該是：'的foreach（在myArray_3雙項）' –

不管你決定去什麼：

使用浮點數安全

可靠的方法來定義平等對於雙精度浮點數不是operator==。它是：

(a - b < Double.Epsilon)

在快速排序專門

快速排序看第一個簡單的，但有很多陷阱。首先是它具有可以是二次方的最差情況表現。如果你想推出自己的快速排序，你需要了解如何緩解這些情況：

數組排序洗牌之前。這是保證性能所必需的。具體來說，如果數組呈現特定順序，則Hoare分區方案（用於快速排序的原始分區方案）會降低性能。
記住，快速排序不是一種穩定的排序算法。這意味着您無法按多個條件進行排序，因爲順序不會在嵌套排序中保留。
荷蘭國旗問題。如果你允許重複的值，你最終可以得到一個胖分區，這將使得快速排序以二次方式運行（O(n^2)）。這可以通過快速排序來解決，比如3路快速排序。

來源

2017-05-05 09:38:48 arboreal84

這個問題被標記爲c＃... – Chris

我的不好:)我編輯它。這幾乎是相同的想法。 – arboreal84

epsilon的擔憂在這裏不合適。我們絕對**要**在排序*時要嚴格比較我們的值。我們*想* epsilon，2 * epsilon，3 * epsilon都被視爲*不同*。 – AakashM

如何修改我的快速排序算法，以便它可以對Double數據類型數組進行排序？

回答

相關問題