0

在让我的合并排序工作时遇到一些问题。如果有人可以帮助我，我将不胜感激。

我不知道为什么，但是排序出来的列表没有排序。我尝试过使用断点，但这似乎无助于找到问题。

static class MergeSort
{
    //Sort<T> - The <T> is called a generic parameter
    public static IList<T> Sort<T>(IList<T> input)
    {
        List<T> Result = new List<T>();
        Queue<T> Left = new Queue<T>(); //Switched from lists to queues because removing at index 0 is more efficient
        Queue<T> Right = new Queue<T>();
        //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<T>(Sort(Left.ToList())); //Recursion! :o
        Right = new Queue<T>(Sort(Right.ToList())); ; //This line and the one above split the list into smaller lists (left and right)

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

        return Result;
    }

    private static List<T> Merge<T>(Queue<T> Left, Queue<T> Right)
    {
        List<T> Result = new List<T>();
        while (Left.Count /* O(1) operation */ > 0 && Right.Count > 0)
        {
            int cmp = Comparison((Left.Peek() as Entity), (Right.Peek() as Entity));
            //If cmp is less than 0, left is less. If it is greater, left is greater

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

    private static int Comparison(Entity Left, Entity Right)
    {
        if (Left.TimesEaten > Right.TimesEaten)
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }
}

如果您需要知道，在“比较”方法中，Left.TimesEaten 是一个整数。

4

2 回答 2

1

您在实现中有一个错误Merge。对于给定的一对Left和Right队列，您只比较它们的第一个元素。您实际上需要在每次添加后重新执行比较（例如，通过Comparison在循环内移动调用）：

private static List<T> Merge<T>(Queue<T> Left, Queue<T> Right)
{
    List<T> Result = new List<T>();
    while (Left.Count > 0 && Right.Count > 0)
    {
        int cmp = Comparison((Left.Peek() as Entity), (Right.Peek() as Entity));
        //If cmp is less than 0, left is less. If it is greater, left is greater

        if (cmp < 0)
            Result.Add(Left.Dequeue());
        else
            Result.Add(Right.Dequeue());
    }

    // ...
于 2013-10-25T19:03:36.587 回答
1

该行与

int cmp = Comparison((Left.Peek() as Entity), (Right.Peek() as Entity));

必须在 while 循环内。整个合并使用相同比较的结果。

于 2013-10-25T19:04:44.403 回答