c# - C#中的MergeSort算法

Question

我为合并类编写了以下代码:

class Merge
{

    public static void sort(IComparable[] a)
    {
        sort(a, 0, a.Length);
    }

    public static void sort(IComparable[] a, int low, int high)
    {
        int N = high - low;
        if (N <= 1)
            return;

        int mid = low + N / 2;

        sort(a, low, mid);
        sort(a, mid, high);

        IComparable[] aux = new IComparable[N];
        int i = low, j = mid;
        for (int k = 0; k < N; k++)
        {
            if (i == mid) aux[k] = a[j++];
            else if (j == high) aux[k] = a[i++];
            else if (a[j].CompareTo(a[i]) < 0) aux[k] = a[j++];
            else aux[k] = a[i++];
        }

        for (int k = 0; k < N; k++)
        {
            a[low + k] = aux[k];
        }
    }

    private static Boolean isSorted(IComparable[] a)
    {
        for (int i = 1; i < a.Length; i++)
            if (a[i].CompareTo(a[i - 1]) < 0) return false;
        return true;
    }

}

下面的代码是实现。我认为下面的代码应该没有错!但它无法编译...

class Program
{
    static void Main(string[] args)
    {
    Merge ms = new Merge();

    Double[] MyArray = { 80,10,52,7,36,7,67,1,8,54 };
    Console.WriteLine("first array is: \n");
    for (int k = 0; k < MyArray.Length; k++)
    {
        Console.Write(MyArray[k]);
        if (k<9)
           Console.Write(" , ");
    }
    ms.sort(MyArray);  // Error is here. Does't compile !!!
    Console.WriteLine("\n");
    Console.WriteLine("\nsorted array is: \n ");
    for (int k = 0; k < MyArray.Length; k++)
    {
        Console.Write(MyArray[k]);
        if (k<9)
           Console.Write(" , ");
    }
    Console.ReadLine();
    }
}

它不编译。错误在 ms.sort(MyArray); 中。 我究竟做错了什么？ 请带领我...

问候

Answer 1

这段代码有两个问题:

1. 签名不匹配，IComparable[]不直接兼容 double[]在这种情况下
2. 您不能调用 sort直接通过实例方法

修复此问题的最少更改是使方法通用，并调用 Merge.sort而不是 ms.sort .

以下是我将如何实现 sort :

public static void sort<T>(T[] a)
    where T : IComparable<T>
{
    sort(a, 0, a.Length);
}

public static void sort<T>(T[] a, int low, int high)
    where T : IComparable<T>
{
    int N = high - low;
    if (N <= 1)
        return;

    int mid = low + N / 2;

    sort(a, low, mid);
    sort(a, mid, high);

    T[] aux = new T[N];
    int i = low, j = mid;
    for (int k = 0; k < N; k++)
    {
        if (i == mid) aux[k] = a[j++];
        else if (j == high) aux[k] = a[i++];
        else if (a[j].CompareTo(a[i]) < 0) aux[k] = a[j++];
        else aux[k] = a[i++];
    }

    for (int k = 0; k < N; k++)
    {
        a[low + k] = aux[k];
    }
}

请注意，我改为使用 T而不是 IComparable , 并添加了一个约束说明我们需要 T实现 IComparable<T> .

此外，将您的电话改为:

ms.sort(...);

为此:

Merge.sort(...);