0

我目前有一个合并排序，它根据每个节点中称为“F”（即 Node.F）的整数对节点列表进行排序。

但是，我想出需要将 MergeSort 用于另一个对象列表 - 实体。但是，我想根据每个实体中称为“AmountEaten”（即 Entity.AmountEaten）的整数对其进行排序。

现在这是我的问题-> 使 MergeSort 类适用于所有对象。我已经用“对象”替换了排序中对节点的所有引用，但是如何允许自定义标准进行排序？有没有办法将它作为参数提供。

如果这没有意义，在 MergeSort 中，我比较两个值（例如 Left.F < Right.F）。对于通用对象，这是行不通的，因为 F 不存在。我希望能够在我的排序中比较对象内的任何内容（例如 Left.AmountEaten < Right.AmountEaten）。我不知道如何将其作为参数。我立即想到了代表，但我不确定如何/是否正确。

由于排序处理的是列表而不是单个对象，因此我不能简单地给出 F/AmountEaten 的参数，因为我想访问变量而不是值。

如果您需要更多详细信息/不明白，请询问。

似乎已经得出了某种形式的结论，但你能帮我完成吗？

合并排序类：

static class MergeSort
{
    public static IList<object> Sort(IList<object> input, Comparison<object> comparison /* Comparison is a delegate that works out the difference
                                                                                         * between 2 values - Same signature used by List<T>.Sort */)
    {
        List<object> Result = new List<object>();
        Queue<object> Left = new Queue<object>(); //Switched from lists to queues because removing at index 0 is more efficient
        Queue<object> Right = new Queue<object>();
        //Dequeue() and Count() have a time complexity of O(1)

        if (input.Count <= 1)
            return input;

        int midpoint = input.Count / 2;

        for (int i = 0; i < midpoint; i++)
            Left.Enqueue(input[i]);
        for (int i = midpoint; i < input.Count; i++)
            Right.Enqueue(input[i]);

        Left = new Queue<object>(Sort(Left.ToList(), comparison)); //Recursion! :o
        Right = new Queue<object>(Sort(Right.ToList(), comparison)); ; //This line and the one above split the list into smaller lists (left and right)

        Result = Merge(Left, Right, comparison); //This joins the lists together

        return Result;
    }

    private static List<object> Merge(Queue<object> Left, Queue<object> Right, Comparison<object> comparison)
    {
        int cmp = comparison(Left.Peek(), Right.Peek());
        //If cmp is less than 0, left is less. If it is greater, left is greater

        List<object> Result = new List<object>();
        while (Left.Count /* O(1) operation */ > 0 && Right.Count > 0)
        {
            if (cmp < 0)
                Result.Add(Left.Dequeue());
            //Left.RemoveAt(0) - Using a list to remove at a certain point is inefficient
            else
                Result.Add(Right.Dequeue());
        }

        while (Left.Count > 0)
            Result.Add(Left.Dequeue());

        while (Right.Count > 0)
            Result.Add(Right.Dequeue());

        return Result;
    }
}
}

用法：

Entities = MergeSort.Sort(Entities, (p, q) => p.F.CompareTo(q.F)).ToList();
4

1 回答 1

1

通常最好的签名是类似于以下使用的签名List<T>.Sort(...)：

static void MergeSort<T>(IList<T> coll, Comparison<T> comparison)
{
    ...
    // < 0 coll[i] < coll[j], == 0 coll[i] == coll[j], > 0 coll[i] > coll[j]
    int cmp = comparison(coll[i], coll[j]);
    ...
}

利用：

MergeSort(coll, (p, q) => p.F.CompareTo(q.F));

请注意，如果F是整数，您通常会看到如下比较：(p, q) => p.F - q.F. 这是有效的，因为 if p.F > q.Fthenp.F - q.F > 0等等。

另一种可能的变体是 LINQ 使用的变体OrderBy(...)

通常最好的签名是类似于以下使用的签名List<T>.Sort(...)：

static void MergeSort<T, TKey>(IList<T> coll, Func<T, TKey> selector)
{
    var comparer = Comparer<Tkey>.Default;

    ...
    // < 0 coll[i] < coll[j], == 0 coll[i] == coll[j], > 0 coll[i] > coll[j]
    int cmp = comparer(selector(coll[i]), selector(coll[j]));
    ...
}

利用：

MergeSort(coll, p => p.F);

在这里，我们将一个能够返回“排序键”的委托传递给该方法，例如p => p.F. 它有点慢，更难使用（但它可能在 LINQ 中使用，因为它更类似于在 SQL 中所做的）

于 2013-09-01T08:05:19.967 回答