我的合并排序实现有什么问题

Question

我确定我犯了一个非常愚蠢的错误，但我已经犯了几个小时了，我只是希望我的代码能够漂亮地排序......当奇数出现时，实现出现了问题等式.

下面是我的MergeSplit方法：

     static List<Motor> MergeSplit(List<int> ListX)
     {
            int n = ListX.Count;
            if (n <= 1)
                return ListX;

            List<int> left = new List<int>();
            List<int> right = new List<int>();

            for (int i = 0; i < n; i++)
            {
                if (i < (n / 2))
                    left.Add(ListX[i]);
                else
                    right.Add(ListX[i]);
            }

            left = MergeSplit(left);
            right = MergeSplit(right);
            return Merge(left, right);

      }

这里是 Merge 方法：

    static List<int> Merge(List<int> ListX, List<int>  ListY)
    {
        List<int> result = new List<int>();

        int i = 0;
        while (ListX.Count > i && ListY.Count > i)
        {
            if (ListX[i] > ListY[i])
            {
                result.Add(ListY[i]);
                result.Add(ListX[i]);
            }
            else
            {
                result.Add(ListX[i]);
                result.Add(ListY[i]);
            }
            i++;
        }

        //If odd, add the rest to the result
        if (ListX.Count > ListY.Count)
            result.Add(ListX[ListX.Count - 1]);
        else if (ListY.Count > ListX.Count)
            result.Add(ListY[ListY.Count - 1]);

        return result;
    }

感谢您的帮助！

更新

算法只是不能正确排序某些输入

Answer 1

问题是你的 Merge 例程

您正在比较左侧和右侧并将它们分别添加到列表中，您应该比较头部，并将最低的添加到结果中，并分别移除该头部以进行下一次比较

这是来自 wiki 的伪代码 https://en.wikipedia.org/wiki/Merge_sort

while left is not empty and right is not empty do
    if first(left) ≤ first(right) then
        append first(left) to result
        left := rest(left)
    else
        append first(right) to result
        right := rest(right)

你可以在这里看到为什么那很重要

如您所见，它实际上比较了第一个左边和第一个右边，然后将它们添加到结果中并从列表中删除该项目。这与你正在做的有很大不同。您要么需要 2 个索引变量，要么从列表中删除项目

while (listX.Count > 0 && listY.Count > 0)
   if (listX[0] > listY[0])
   {
      result.Add(listY[0]);
      listY.RemoveAt(0);
   }
   else
   {
      result.Add(listX[0]);
      listX.RemoveAt(0);
   }


if (listX.Count > 0)
   result.AddRange(listX);
else if (listY.Count > 0)
   result.AddRange(listY);

只是为了好玩，我发现队列更容易玩，他们似乎喜欢这种东西

private static Queue<int> Merge(Queue<int> left, Queue<int> right)
{
   var result = new Queue<int>();

   while (left.Count > 0 && right.Count > 0)
      result.Enqueue(left.Peek() > right.Peek() ? right.Dequeue() : left.Dequeue());

   foreach (var item in left)
      result.Enqueue(item);

   foreach (var item in right)
      result.Enqueue(item);

   return result;
}

private static Queue<int> MergeSplit(Queue<int> list)
{
   var n = list.Count;

   if (n <= 1)
      return list;

   var left = new Queue<int>();
   var right = new Queue<int>();

   for (var i = 0; i < n; i++)
      if (i < n / 2)
         left.Enqueue(list.Dequeue());
      else
         right.Enqueue(list.Dequeue());

   left = MergeSplit(left);
   right = MergeSplit(right);
   return Merge(left, right);
}

用法

var list = new List<int> { 8, 7, 6, 4, 43, 23, 435, 76, 7, 7877, 5, 421, 2 };
var results = MergeSplit(new Queue<int>(list));
Console.WriteLine(string.Join(", ", results));

输出

2, 4, 5, 6, 7, 7, 8, 23, 43, 76, 421, 435, 7877

Full Demo Here

我的合并排序实现有什么问题

What's wrong with my merge sort implementation

c#

sorting

mergesort