StackOverFlowException при сортировке слиянием - PullRequest
Новая
       17

StackOverFlowException при сортировке слиянием

0 голосов
/ 22 апреля 2020

Итак, я пытаюсь выполнить сортировку слиянием, но продолжаю получать 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;
        }

1 Ответ

2 голосов
/ 22 апреля 2020

Ваша проблема с кодом, который определяет, в какой список помещать каждый элемент в 

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

Если в списке 2 элемента, то индексы равны 0 и 1, и это условие верно для обоих, поэтому они оба внесены в левый список и ничего в правый. Затем вы звоните 

left = MergeSort(left);

, который берет список из 2-х элементов, и снова он собирается поместить оба слева и вызвать его снова и поместить их оба слева и .... навсегда.

Просто измените сравнение на 

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

Кроме того, вы не должны использовать IndexOf, поскольку он вернет индекс первого элемента вместо текущего, если у вас есть дубликаты в списке. Таким образом, список с «ab c» в нем дважды будет возвращать 0 оба раза, и вы попадете в один и тот же бесконечный l oop. Вместо этого вы можете просто сделать for l oop вот так 

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