c#中的归并排序算法

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

这个代码有两个问题:

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

    //merge sort recurcive
    public void MergeSort(int[] input,int startIndex,int endIndex)
    {
        int mid;
        if (endIndex > startIndex)
        {
            mid = (endIndex + startIndex) / 2;
            MergeSort(input, startIndex, mid);
            MergeSort(input, (mid + 1), endIndex);
            Merge(input, startIndex, (mid + 1), endIndex);
        }
    }
    public void Merge(int[] input, int left, int mid, int right)
    {
        //Merge procedure takes theta(n) time
        int[] temp = new int[input.Length];
        int i, leftEnd,lengthOfInput,tmpPos;
        leftEnd = mid - 1;
        tmpPos = left;
        lengthOfInput = right - left + 1;
        //selecting smaller element from left sorted array or right sorted array and placing them in temp array.
        while ((left <= leftEnd) && (mid <= right))
        {
            if (input[left] <= input[mid])
            {
                temp[tmpPos++] = input[left++];
            }
            else
            { 
                temp[tmpPos++]=input[mid++];
            }
        }
        //placing remaining element in temp from left sorted array
        while (left <= leftEnd)
        {
            temp[tmpPos++] = input[left++];
        }
        //placing remaining element in temp from right sorted array
        while (mid <= right)
        {
            temp[tmpPos++] = input[mid++];
        }
        //placing temp array to input
        for (i = 0; i < lengthOfInput;i++ )
        {
            input[right]=temp[right];
            right--;
        }
    }
     int[] input3 = { 22, 4, 6, 0, 9, 12, 156, 86,99};
     MergeSort(input3, 0, input3.Length - 1);
        for (int i = 0; i < input3.Length; i++)
            Console.Write(input3[i]+", ");
        Console.WriteLine("");

你的sort方法是静态的，你不应该从你的类的实例调用它。

你应该这样称呼它:

Merge.sort(MyArray);

:

ms.sort(MyArray);

事实上，由于您的Merge类没有实例方法，因此创建它的实例是没有意义的，您可能应该将整个类标记为静态。

一个简单的c#代码来做归并排序

using System;
namespace MergeSort
{
    class Program
    {
        static void Main(string[] args)
        {            
            int[] arInt = { 6, 4, 2, 8, 4, 8, 11, 1, 7, 4, 13, 5, 45, -1, 0, -7, 56, 10, 57 };
            var sortedIntAr = GenericMergeSort<int>.Sort(arInt);
            string[] arStr = { "Here", "Is", "A", "Cat", "Really", "Fast", "And", "Clever" };
            var sortedStrAr = GenericMergeSort<string>.Sort(arStr);
            Console.WriteLine(String.Join(',', sortedIntAr));
            Console.WriteLine(String.Join(',', sortedStrAr));
            Console.ReadLine();
        }
    }
    class GenericMergeSort<T> where T : IComparable
    {
        public static T[] Sort(T[] ar)
        {
            var arLen = ar.Length;
            if (arLen < 2)
                return ar;
            var arL = ar.AsSpan(0..(arLen / 2)).ToArray();
            var arR = ar.AsSpan((arLen / 2)..arLen).ToArray();
            arL = Sort(arL);
            arR = Sort(arR);
            return Merge(arL, arR);
        }
        private static T[] Merge(T[] arL, T[] arR)
        {
            var mergedArray = new T[arL.Length + arR.Length];
            int iM = 0, iL = 0, iR = 0;
            while (iL < arL.Length || iR < arR.Length)
            {
                mergedArray[iM++] = iL < arL.Length && (iR > arR.Length - 1 || arL[iL].CompareTo(arR[iR]) < 0)
                                    ? arL[iL++] : arR[iR++];
            }
            return mergedArray;
        }
    }
}

下面是输出

7 - 1, 0, 1, 2, 4, 4, 4, 5, 6, 7, 8、8、10、11、13日,45岁的56、57

,猫,聪明,很快,在这里,真的是,

public static int[] mergeSort(int[] ar)
{
    Func<int[], int[]> firstHalf = (array) =>
     {
         return array.Take((array.Length + 1) / 2).ToArray();
     };
    Func<int[], int[]> secondHalf = (array) =>
    {
        return array.Skip((array.Length + 1) / 2).ToArray();                
    };
    Func<int[], int[], int[]> mergeSortedArrays = (ar1, ar2) =>
    {
        int[] mergedArray = new int[ar1.Length + ar2.Length];
        int i1 = 0, i2 = 0, currentMin;
        while (i1 < ar1.Length || i2 < ar2.Length)
        {
            if (i1 < ar1.Length && i2 < ar2.Length)
            {
                if (ar1[i1] < ar2[i2])
                {
                    currentMin = ar1[i1];
                    i1++;
                }
                else
                {
                    currentMin = ar2[i2];
                    i2++;
                }
            }
            else if (i1 < ar1.Length)
            {
                currentMin = ar1[i1];
                i1++;
            }
            else
            {
                currentMin = ar2[i2];
                i2++;
            }
            mergedArray[i1 + i2 - 1] = currentMin;
        }
        return mergedArray;
    };
    int[] half1 = firstHalf(ar); //always /geq than half2
    int[] half2 = secondHalf(ar);
    if (half1.Length < 2)
        return mergeSortedArrays(half1, half2);
    else
        return mergeSortedArrays(mergeSort(half1), mergeSort(half2));
}

一个简单的c#归并排序。

using System.Collections.Generic;
namespace Sort
{
    public class MergeSort
    {
        public static List<int> mergeSort(List<int> list)
        {
            if (list.Count <= 1) return list;
            List<int> result;
            List<int> left = new List<int>();
            List<int> right = new List<int>();
            int midPoint = list.Count / 2;
            left.AddRange(list.GetRange(0, midPoint));
            right.AddRange(list.GetRange(midPoint, list.Count - midPoint));
            left = mergeSort(left);
            right = mergeSort(right);
            result = merge(left, right);
            return result;
        }
        //This method will be responsible for combining our two sorted arrays into one giant array
        public static List<int> merge(List<int> left, List<int> right)
        {
            List<int> result = new List<int>();
            int indexLeft = 0, indexRight = 0, indexResult = 0;
            while (indexLeft < left.Count || indexRight < right.Count)
            {
                //if both arrays have elements  
                if (indexLeft < left.Count && indexRight < right.Count)
                {
                    if (left[indexLeft] <= right[indexRight])
                    {
                        result.Add(left[indexLeft]);
                        indexLeft++;
                    }
                    else
                    {
                        result.Add(right[indexRight]);
                        indexRight++;
                    }
                }
                else if (indexLeft < left.Count)
                {
                    result.Add(left[indexLeft]);
                    indexLeft++;
                }
                else if (indexRight < right.Count)
                {
                    result.Add(right[indexRight]);
                    indexRight++;
                }
                indexResult++;
            }
            return result;
        }
    }
}