#.net #algorithm #sorting
#.net #алгоритм #сортировка
Вопрос:
Завтра у меня намечается собеседование по .NET , и я понял , что я немного слаб в своей алгоритмической части (в остальном я исключительно хороший программист , возможно , лучше вас … ха-ха, шутка, кто смеялся?), поскольку я никогда не программировал никаких математически сложных алгоритмов на своей работе.
Мне было интересно, какие алгоритмы лучше всего подходят / наиболее эффективны для сортировки данных определенных типов? Например, какой алгоритм вы бы использовали для сортировки двух списков DateTime в порядке возрастания? Здесь не разрешен LINQ, чтобы вы сортировали их быстрее всего?
И точно так же, какие алгоритмы лучше всего подходят для сортировки других типов данных, таких как строки или числа и т.д.?
Комментарии:
1. Мне кажется, что одно из преимуществ работы .NET-программистом заключается в том, что вам больше не нужно писать «математически сложные алгоритмы», по крайней мере, не для простых, повседневных задач, таких как сортировка . Здесь есть много других вопросов об алгоритмах сортировки; в этом нет ничего уникального для .NET, кроме, возможно, свободы забыть, каково это — каждый раз заново внедрять колесо.
2. Да, мне тоже так кажется, пока 2 года назад, когда я снова искал работу, я не использовал метод ‘List.Sort()’, как сделал бы обычный человек, и не получил работу 🙂 Поэтому на этот раз я хотел бы быть более подготовленным на случай, если мне придется столкнуться с аналогичной задачей кодирования
3. Они действительно сказали вам, что использование встроенного метода в фреймворке было причиной того, что вы не получили работу? Я думаю, что вы уклонились от пули там. Благодарите свою счастливую звезду, что вы не работаете в компании с синдромом Not Invented Here…
4. Я не знаю, насколько детализирована операция, но существуют специализированные (быстрее, чем O (n lg n)) алгоритмы сортировки, когда ключами являются целые числа или числа с плавающей запятой в небольшом диапазоне, или другие специализированные вещи, которые имеют операции, выходящие за рамки простого сравнения.
5. @Cody Gray: Нет, это был сотрудник из списка 500 лучших
Ответ №1:
Существуют разные алгоритмы сортировки, но вы можете использовать любой из них независимо от типа данных, вам просто нужен метод для сравнения двух значений и определения, совпадают ли они или одно из них больше другого.
В фреймворке есть готовые алгоритмы сортировки, например List.Sort метод. Если вы сортируете список простых значений (таких как строки, числа, даты и т.д.), Который уже поддерживается, поскольку для них существуют средства сравнения по умолчанию:
myList.Sort();
Если вы сортируете пользовательские объекты, вы можете предоставить средство сравнения для метода:
myList.Sort((x, y) => x.Name.CompareTo(y.Name));
Если вы хотите реализовать алгоритм сортировки самостоятельно, вы можете посмотреть на различные из них, такие как сортировка вставкой, сортировка слиянием, быстрая сортировка, сортировка оболочкой и т.д. Одним из самых простых для понимания и реализации является пузырьковая сортировка.
Комментарии:
1. Спасибо, Гуффа, я тоже так думал, поскольку в конечном итоге все преобразуется в число — его сопоставимо. Итак, знаете ли вы какие-либо быстрые алгоритмы, которые могут быть применены в том редком случае, который вам следует делать, когда обычный цикл Linq или for не обрезает его?
2. Боже! Пузырьковая сортировка! <выполняется и скрывается>
Ответ №2:
Большинство алгоритмов сортировки разработаны на основе идеи о том, что сравнение элементов данных является примитивной операцией (то есть это не является частью разработки алгоритма). Однако существуют исключения (например, сортировка по радиусу).
Более интересным является вопрос о том, какой алгоритм лучше всего подходит для конкретных предположений о входных данных: в основном ли они уже отсортированы; все ли это помещается в памяти без серьезных проблем с производительностью; должны ли связанные элементы оставаться в порядке ввода; нужно ли соотносить внешние данные с сортировкой; и т.д.
Если бы я готовился к собеседованию, я бы остановился на последних вопросах. (Но я бы не хотел делать это накануне вечером :). Удачи вам на собеседовании.)
Комментарии:
1. Спасибо за ваши пожелания, Ted! С такого рода проблемами я сталкивался, поэтому я думаю, что здесь со мной все в порядке, но, к счастью, я сейчас их рассмотрю.