合并排序时出现 StackOverFlowException

Question

所以，我正在尝试进行合并排序，但我一直收到 WhosebugException 并且我不太明白我做错了什么。此工作代码是否适用于合并排序，或者是否有更好的代码编写方法？

static public List<string> MergeSort(List<string> list)
        {
            List<string> left = new List<string>();
            List<string> right = new List<string>();

            if (list.Count <= 1)
            {
                return list;
            }

            foreach (var item in list)
            {
                if (list.IndexOf(item) <= (list.Count / 2))
                {
                    left.Add(item);
                }
                else
                    right.Add(item);
            }
            left = MergeSort(left);
            right = MergeSort(right);
            return Merge(left, right);
        }
        static public List<string> Merge(List<string> left, List<string> right)
        {
            List<string> merged = new List<string>();

            while (left.Count != 0 && right.Count != 0)
            {
                if (left.First().Length <= right.First().Length)
                {
                    merged.Add(left.First());
                    left.Remove(left.First());
                }
                else
                {
                    merged.Add(right.First());
                    right.Remove(right.First());
                }
            }
            while(left.Count != 0)
            {
                merged.Add(left.First());
                left.Remove(left.First());
            }
            while (right.Count != 0)
            {
                merged.Add(right.First());
                right.Remove(right.First());
            }
            return merged;
        }

Answer 1

您的问题在于确定将每个项目放入哪个列表的代码

 if (list.IndexOf(item) <= (list.Count / 2))

如果列表有 2 个项目，则索引为 0 和 1，并且此条件对两者都成立，因此它们都放在左侧列表中，而右侧没有任何内容。然后你打电话给

left = MergeSort(left);

这是一个包含 2 个项目的列表，它再次将两者都放在左边，然后再次调用它，将它们都放在左边......永远。

只需将比较更改为

 if (list.IndexOf(item) < (list.Count / 2))

此外，您不应使用 IndexOf，因为如果您在列表中有重复项，它将 return 第一项而不是当前项的索引。因此，其中两次包含 "abc" 的列表将 return 0 两次，您将陷入同一个无限循环。相反，您可以像这样 for 循环

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

合并排序时出现 StackOverFlowException

StackOverFlowException on Merge Sort

c#

stack-overflow

mergesort