如何修改我的快速排序算法以便它可以对 Double 数据类型数组进行排序？

Question

我使用此快速排序算法对整数数组进行排序，但我还希望它对双精度数组进行排序。我需要更改哪些变量才能使其正常工作？我尝试更改许多不同的数据类型组合。

感谢任何帮助。

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

Answer 1

您应该能够使用泛型，其中类型实现 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);
}

Answer 2

无论您决定选择什么：

安全使用浮点数

为双精度浮点数定义相等性的可靠方法不是 operator==。它是：

(a - b < Double.Epsilon)

专门针对快速排序

Quicksort 初看起来很简单，但有很多陷阱。第一个是它在最坏情况下的性能可能是二次方的。如果您想推出自己的快速排序，您需要了解如何缓解这些情况：

排序前随机排列数组。这是保证性能所必需的。具体来说，如果数组呈现某些顺序，Hoare 分区方案（快速排序的原始分区方案）会降低性能。
请记住，快速排序不是一种稳定的排序算法。这意味着您不能按多个标准进行排序，因为在嵌套排序中不会保留该顺序。
荷兰国旗问题。如果您允许重复值，您最终可能会得到一个胖分区，它会在二次时间 (O(n^2)) 中进行快速排序运行。这可以通过 3 向快速排序等快速排序变体来解决。

如何修改我的快速排序算法以便它可以对 Double 数据类型数组进行排序？

How do I modify my Quick Sort Algorithm so that it can sort Double data type arrays?

c#

arrays

sorting

algorithm

quicksort