合并排序时出现StackOverFlowException异常。

所以,我想做合并排序,但我一直得到一个 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;
        }

解决方案:

你的问题在于决定将每个项目放入哪个列表的代码。

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

本文来自投稿,不代表运维实战侠立场,如若转载,请注明出处:https://www.shizhanxia.com/272.html

(0)
上一篇 2022年6月29日 下午3:54
下一篇 2022年6月29日 下午3:54

相关推荐

发表评论

登录后才能评论