Когда использовать какой алгоритм сортировки, а когда - нет

Question

Мы видим множество методов сортировки, таких как Merge, quick, Heap.Не могли бы вы помочь мне решить, какие из этих методов сортировки использовать в какой среде (как в проблеме)?Когда мы должны использовать какой из этих алгоритмов сортировки, а где нет (их недостатки во времени и пространстве)?

Я ожидаю ответа на что-то в этой форме: a) Мы будем использовать сортировку слиянием, когда ... мы должны определенноне использовать сортировку слиянием, когда ... б) мы будем использовать быструю сортировку, когда ... определенно не следует использовать быструю сортировку, когда ...

Answer 1

Существует несколько основных параметров, которые характеризуют поведение каждого алгоритма сортировки:

• средняя сложность вычислений
• вычислительная сложность в худшем случае
• требования к памяти
• стабильность (т.е. это стабильная сортировка или нет?)

Все это широко документировано для всех обычно используемых сортов , и это вся информация, необходимая для предоставления ответа в нужном формате. Тем не менее, поскольку даже четыре параметра для каждого вида имеют большое значение, и не все из них будут важны для рассмотрения, попытка дать такой «скриптовый» ответ не очень хорошая идея. Кроме того, есть еще более продвинутые концепции, которые могут быть приняты во внимание (например, поведение при работе с почти отсортированными или обратно отсортированными данными, производительность кэша, устойчивость к злонамеренному вводу), что делает такой ответ еще более длинным и подверженным ошибкам. .

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

Answer 2

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