При реализации этого общего merge sort, как своего рода Код Kata, я наткнулся на разницу между IEnumerable и List, мне нужна помощь, чтобы понять.
Здесь MergeSort
public class MergeSort<T>
{
public IEnumerable<T> Sort(IEnumerable<T> arr)
{
if (arr.Count() <= 1) return arr;
int middle = arr.Count() / 2;
var left = arr.Take(middle).ToList();
var right = arr.Skip(middle).ToList();
return Merge(Sort(left), Sort(right));
}
private static IEnumerable<T> Merge(IEnumerable<T> left, IEnumerable<T> right)
{
var arrSorted = new List<T>();
while (left.Count() > 0 && right.Count() > 0)
{
if (Comparer<T>.Default.Compare(left.First(), right.First()) < 0)
{
arrSorted.Add(left.First());
left=left.Skip(1);
}
else
{
arrSorted.Add(right.First());
right=right.Skip(1);
}
}
return arrSorted.Concat(left).Concat(right);
}
}
Если я удаляю .ToList()
в переменных left
и right
, он не может правильно сортироваться. Вы понимаете, почему?
Пример
var ints = new List<int> { 5, 8, 2, 1, 7 };
var mergeSortInt = new MergeSort<int>();
var sortedInts = mergeSortInt.Sort(ints);
С .ToList()
[0]: 1 [1]: 2 [2]: 5 [3]: 7 [4]: 8
Без .ToList()
[0]: 1 [1]: 2 [2]: 5 [3]: 7 [4]: 2
Edit
Это был мой тупой тест, который заставил меня.
Я протестировал его так:
var sortedInts = mergeSortInt.Sort(ints);
ints.Sort();
if (Enumerable.SequenceEqual(ints, sortedInts)) Console.WriteLine("ints sorts ok");
просто изменив первую строку на
var sortedInts = mergeSortInt.Sort(ints).ToList();
устраняет проблему (и ленивую оценку).
EDIT 2010-12-29
Мне показалось, что я выясню, как ленивая оценка беспорядок здесь, но я просто не понимаю.
Удалите .ToList()
в методе сортировки выше, как это показано
var left = arr.Take(middle);
var right = arr.Skip(middle);
попробуйте это
var ints = new List<int> { 5, 8, 2 };
var mergeSortInt = new MergeSort<int>();
var sortedInts = mergeSortInt.Sort(ints);
ints.Sort();
if (Enumerable.SequenceEqual(ints, sortedInts)) Console.WriteLine("ints sorts ok");
При отладке Вы можете видеть, что до ints.Sort()
a sortedInts.ToList()
возвращает
[0]: 2
[1]: 5
[2]: 8
но после ints.Sort()
он возвращает
[0]: 2
[1]: 5
[2]: 5
Что на самом деле происходит здесь?