0

我正在尝试在 中实现通用Mergesort算法C#，但在Constraints. 我搜索了很多参考资料，但找不到任何像我一样实现算法的参考资料。

C#中的合并排序算法

排序算法的通用实现

无论如何，我试图提供一个只允许用户对从IComparable接口继承的数据集进行合并排序的实现。

以下是我到目前为止的内容：

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# 不直接支持通配符，这种方法对我来说是陌生的。对此的任何解释也将不胜感激。

4

2 回答 2

1

MergeSort需要一个ref参数，所以它需要ref关键字。这应该有效：

Mergesort.mergeSort<int>(ref testList);

ref 关键字导致参数通过引用而不是值传递。通过引用传递的效果是方法中参数的任何更改都会反映在调用方法中的底层参数变量中。引用参数的值始终与基础参数变量的值相同。

于 2013-08-11T00:25:30.143 回答
1

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

此外，在大多数情况下，您不需要提供泛型参数类型，因为编译器会为您推断类型。ref所以这在大多数情况下应该可以工作（假设你已经从参数中删除了）：

Mergesort.mergeSort(testList);

此外List<T>，数组具有索引器，因此您可以通过inputData[index]而不是ElementAt. 这样打字就少了。

于 2013-08-11T00:43:13.560 回答