Алгоритмы сортировки по типу сортируемых данных

Question

Завтра у меня интервью .NET, и я понял, что я немного слаб в своей алгоритмической стороне (в противном случае я исключительно хороший программист, может быть, лучше, чем вы ... хаха, шутка, кто смеялся?) КакЯ никогда не программировал математически интенсивные алгоритмы на своей работе.

Мне было интересно, какие алгоритмы лучше всего подходят / наиболее эффективны для сортировки данных определенных типов?Например, какой алгоритм вы бы использовали для сортировки двух списков DateTime в порядке возрастания?LINQ здесь не разрешен, так что вы сортируете их быстрее всего?

И аналогично, какие алгоритмы лучше всего подходят для сортировки других типов данных, таких как строки или числа и т. Д .?

Answer 1

Большинство алгоритмов сортировки основаны на идее, что сравнение элементов данных является примитивной операцией (то есть не является частью разработки алгоритма). Однако есть исключения (например, сортировка по основанию).

Более интересным является вопрос о том, какой алгоритм лучше всего подходит для конкретных предположений о входных данных: он в основном уже отсортирован; все ли умещается в памяти без серьезных проблем с производительностью; должны ли связанные элементы оставаться в порядке ввода; нужно ли соотносить внешние данные с сортировкой; и т.д.

Если бы я готовился к собеседованию, я бы был в курсе последних вопросов. (Но я бы не хотел делать это прошлой ночью :). Удачи на собеседовании.)

Answer 2

Существуют разные алгоритмы сортировки, но вы можете использовать любой из них независимо от типа данных, вам просто нужен метод для сравнения двух значений и определения, являются ли они одинаковыми или один из них больше другого.

В структуре есть готовые алгоритмы сортировки, например, метод List.Sort.Если вы сортируете список простых значений (таких как строки, числа, даты и т. Д.), Которые уже поддерживаются, поскольку для них есть стандартные сравнения:

myList.Sort();

Если вы сортируете пользовательские объекты,вы можете предоставить метод сравнения:

myList.Sort((x, y) => x.Name.CompareTo(y.Name));

Если вы хотите реализовать алгоритм сортировки самостоятельно, вы можете посмотреть на разные, такие как вставка сортировка, сортировка слиянием, быстрая сортировка, сортировка оболочки и т. д.,Одним из самых простых для понимания и реализации является пузырьковая сортировка .