Когда использовать сортировки над другим

Question

Среди Quicksort, MergeSort и Binary Insertion Sort, была ли когда-нибудь ситуация, чтобы использовать один из них над другим?

Я знаю, что такие вещи, как Quicksort, могут стать проблематичными в почти отсортированном списке (но я считаю, что случайное назначение сводки может исключить наихудшее время), поэтому может быть лучше использовать MergeSort. MergeSort может использовать больше места, чем QuickSort, я не совсем уверен, и Merge может быть лучше для LinkedLists.

И я предполагаю, что Binary Insertion Sort лучше для небольших списков? Если так, есть ли порог для использования этого или размер оставлен только для интерпретации? Например, если список имеет размер 3, следует ли использовать сортировку бинарных вставок вместо Quick или Merge?

Answer 1

Я предполагаю, что это требует практических советов о том, как сортировать вещи в Java.

Мой совет состоит в том, что обычно лучше использовать Arrays.sort(...) и полагаться на эвристику стандартной реализации для принятия решения.какой алгоритм сортировки использовать.Вам следует беспокоиться об этом, только если:

• вы знаете, что будете сортировать огромные наборы данных,
• вы знаете, что ваш набор данных поддается специальным методам сортировки;например, подсчет сортировки или
• профилирование говорит вам, что использование вами стандартного метода сортировки является узким местом производительности.

---

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

Answer 2

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