Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0 - Сортировщики и алгоритмы
ОГЛАВЛЕНИЕ
Сортировщики
Интерфейс ISorter
public interface ISorter<T>
{
// методы
void Sort(IList<T> list);
void Sort(IList<T> list, SortOrder order);
void Sort(IList<T> list, IComparer<T> comparer);
void Sort(IList<T> list, Comparison<T> comparison);
}
В библиотеке реализовано множество сортировщиков. Стандартные библиотеки каркаса .NET дают малый выбор в плане сортировки, поэтому появились данные сортировщики. Они обобщенные в том смысле, что любой класс, реализующий IList<T>, можно отсортировать, если находящиеся в нем элементы реализуют интерфейс IComparable<T> или если предоставлен экземпляр IComparer<T>.
Предоставляются следующие сортировщики:
• BubbleSorter
• GnomeSorter
• HeapSorter
• InsertionSorter
• SelectionSorter
• MergeSorter
• QuickSorter
• ShellSorter
• BucketSorter
• CombSorter
• CocktailSorter
• OddEvenTransportSorter
• ShakerSorter
Алгоритмы
Алгоритм Дейкстры
Алгоритм Дейкстры помогает с решением задач о кратчайших путях в теории графоф. То есть, если на входе задан направленный или ненаправленный Graph<T>, на выходе выдается граф, представляющий кратчайший путь от вершины источника до любой другой вершины в графе (если вершины достижимы из вершины источника). Ниже показан пример входного и выходного графов с вершиной источника G.
Входной граф
Выходной граф – кратчайшие пути
[Дополнительная информация об алгоритме Дейкстры]
Интересные особенности
Отсутствие поддержки ковариации в C# заставляет избегать интерфейсов для данного типа работы, потому что их применение вынудило бы программиста приводить типы гораздо больше необходимого (или разработчика этой библиотеки заставило бы сделать кучу неявных реализаций).
Также взятая из C++ поддержка множественного наследования и закрытого / защищенного наследования сильно бы изменила эту структуру. Следует надеяться, их поддержка однажды появится в какой-то далекой версии спецификации языка.