谁能帮我为什么我的合并排序不会对列表进行排序

本文关键字：排序 列表 合并 为什么 我的 | 更新日期: 2023-09-27 18:36:58

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

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

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是一个整数。

谁能帮我为什么我的合并排序不会对列表进行排序

您在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());
    }
    // ...


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

必须位于 while 循环内。整个合并使用同一比较的结果。

相关文章：