Сравнение эффективности сортировки пузырьков, выделения и вставки

Question

У меня есть следующее понимание - и пузырьковая сортировка, и сортировка вставок имеют временную сложность

• Лучшее: Ω (n)
• Среднее: Θ (n ^ 2)
• Худшее: O (n ^ 2)

В то время как сортировка выбора имеет все временные сложности (лучше всего, в среднем и хуже): (n ^ 2)

Ниже приведенымои вопросы, основанные на том, что я обычно слышу об этих алгоритмах -

1. , говорят, что пузырьковая сортировка является наименее эффективным алгоритмом / рассматривается наравне с сортировкой выбора.Почему так?(Поскольку я знаю, согласно Ω, сортировка по пузырькам намного лучше, чем выборка.)
2. Сортировка вставкой считается улучшением по сравнению с сортировкой по пузырькам и сортировке.Почему именно так?(опять же, к тому времени сложность, хотя я понимаю, что * лучше, чем сортировка выбора, но это также ТОЧНО, как и сортировка пузырьков).

Answer 1

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