C#中的通用Mergesort

本文关键字:Mergesort | 更新日期: 2023-09-27 18:27:06

我正试图在C#中实现一个通用的Mergesort算法,但我在Constraints方面遇到了困难。我已经搜索了很多参考文献,但我找不到任何像我这样实现算法的参考文献。

C#中的MergeSort算法

排序算法的通用实现

无论如何,我试图提供一种只允许用户对从IComparable接口继承的数据集进行Mergesort的实现。

以下是我到目前为止所拥有的:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace SortUtil
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> testList = new List<int> { 1, 5, 2, 7, 3, 9, 4, 6 };
            Mergesort.mergeSort<int>(testList); // Compiler Error at this Line.
        }
    }
    class Mergesort
    {   
        public static void mergeSort<T>(ref List<T> inputData)
            where T: IComparable<T>
        {
            mergeSort(ref inputData, 0, inputData.Count - 1);
        }
        private static void mergeSort<T>(ref List<T> inputData, int firstIndex, int lastIndex)
            where T: IComparable<T>
        {
            // If the firstIndex is greater than the lastIndex then the recursion 
            // has divided the problem into a single item. Return back up the call 
            // stack.
            if (firstIndex >= lastIndex)
                return;
            int midIndex = (firstIndex + lastIndex) / 2;
            // Recursively divide the first and second halves of the inputData into
            // its two seperate parts.
            mergeSort(ref inputData, firstIndex, midIndex);
            mergeSort(ref inputData, midIndex + 1, lastIndex);
            // Merge the two remaining halves after dividing them in half.
            merge(ref inputData, firstIndex, midIndex, lastIndex);
        }
        private static void merge<T>(ref List<T> inputData, int firstIndex, int midIndex, int lastIndex)
            where T: IComparable<T>
        {
            int currentLeft = firstIndex;
            int currentRight = midIndex + 1;
            T[] tempData = new T[(lastIndex - firstIndex) + 1];
            int tempPos = 0;
            // Check the items at the left most index of the two havles and compare
            // them. Add the items in ascending order into the tempData array.
            while (currentLeft <= midIndex && currentRight <= lastIndex)
                if (inputData.ElementAt(currentLeft).CompareTo(inputData.ElementAt(currentRight)) < 0)
                {
                    tempData[tempPos++] = inputData.ElementAt(currentLeft++);
                }
                else
                {
                    tempData[tempPos++] = inputData.ElementAt(currentRight++);
                }
            // If there are any remaining items to be added to the tempData array,
            // add them.
            while (currentLeft <= midIndex)
            {
                tempData[tempPos++] = inputData.ElementAt(currentLeft++);
            }
            while (currentRight <= lastIndex)
            {
                tempData[tempPos++] = inputData.ElementAt(currentRight++);
            }
            // Now that the items have been sorted, copy them back into the inputData
            // reference that was passed to this function.
            tempPos = 0;
            for (int i = firstIndex; i <= lastIndex; i++) {
                inputData.Insert(firstIndex, tempData.ElementAt(tempPos));
            }
        }
    }
}

My issue:我在Program类的Main方法中遇到编译器错误;然而,当我静态调用mergeSort函数时,我不应该为它提供参数化类型吗?

我收到错误"The best overloaded method match for... has some invalid arguments."

我将非常感谢任何实施建议和/或任何纠正这一错误的方式。注意,我对Java最熟悉,因为C#不直接支持通配符,所以这种方法对我来说是陌生的。对此的任何解释都将不胜感激。

C#中的通用Mergesort

您可以从所有参数中删除ref,因为您似乎没有使用它的功能。

此外,在大多数情况下,您不需要提供泛型参数类型,因为编译器会为您推断类型。因此,在大多数情况下,这应该有效(假设您已经从参数中删除了ref):

Mergesort.mergeSort(testList);

此外,List<T>和数组具有索引器,因此您可以通过inputData[index]而不是ElementAt获取特定元素。这样打字就少了。

MergeSort重用ref参数,因此需要ref关键字。这应该有效:

Mergesort.mergeSort<int>(ref testList);  

ref关键字导致参数通过引用传递,而不是通过价值通过引用传递的效果是方法中的参数反映在基础参数中调用方法中的变量。参考参数的值为始终与基础参数变量的值相同。