合并排序时出现StackOverFlowException异常。

Question

所以，我想做合并排序，但我一直得到一个 StackOverFlowException 而我不太明白自己做错了什么。这个工作代码是否能很好地用于合并排序，或者是否有更好的方法来编写代码？

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 因为如果列表中有重复的项目，它将返回第一个项目的索引，而不是当前项目的索引，所以一个有 "abc "的列表两次都将返回0，你会陷入同样的无限循环。 所以一个列表中包含 "abc "两次，两次都会返回0，你会陷入同样的无限循环。 相反，你可以只做一个 for 循环

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