Среднее время:
- Сортировка выбором: $O(n^2)$ (всегда примерно $\Theta (n^2)$ по числу сравнений).
- Быстрая сортировка: $O(n\log n)$ в среднем (с случайным выбором опорного элемента или хорошей выборкой).
Худший случай:
- Сортировка выбором: $O(n^2)$ (ничем не хуже среднего).
- Быстрая сортировка: $O(n^2)$ в худшем случае при неудачном выборе опоры; этот риск устраняется рандомизацией или медианой трёх, тогда на практике редок.
Устойчивость:
- Сортировка выбором: по умолчанию неустойчива (можно сделать устойчивой, но потребуются дополнительные затраты памяти/копирования).
- Быстрая сортировка: типичная in‑place реализация неустойчива; существуют устойчивые версии, но они обычно требуют дополнительной памяти или усложнённой реализации.
Дополнительные характеристики:
- Перестановок (swap): выбором делает $O(n)$ обменов, но $O(n^2)$ сравнений; быстрая сортировка делает больше обменов/рекурсий, но в среднем значительно меньше сравнений, и лучше использует кэш/локальность, поэтому быстрее на практике для больших массивов.
- Память: выбором $O(1)$ доп. памяти; быстрая in‑place сортировка требует $O(\log n)$ стековой памяти в среднем (хотя в худшем может потребовать $O(n)$ без оптимизаций).
Пригодность для частичных сортировок (например, получить первые $k$ наименьших элементов или частично отсортировать большие массивы):
- Сортировка выбором: чтобы получить первые $k$ минимальных элементов в отсортированном порядке, нужно выполнить $k$ проходов — время $O(nk)$. При маленьком $k$ это приемлемо; при $k$ порядка $n$ — плохо ($O(n^2)$).
- Быстрая сортировка (или её приёмники):
- Quickselect (партитирование без полной сортировки) находит $k$-й элемент и разделяет массив за среднее $O(n)$; после этого первые $k$ элементов можно отсортировать за $O(k\log k)$. Итого среднее $O(n+k\log k)$.
- Частичный quicksort/partial_sort (рекурсивно только в нужной части) даёт похожие асимптотики.
- Для задачи «топ‑k» эффективен также кучный подход с $O(n\log k)$ и небольшой памятью $O(k)$.
Вывод: для больших массивов и частичных задач выбор быстрых алгоритмов (quickselect/partial quicksort/heap) гораздо предпочтительнее чистой сортировки выбором, за исключением очень малого $k$ и очень простых реализаций.
Коротко:
- Для полных больших сортировок: быстрая сортировка (с рандомизацией/оптимизациями) предпочтительнее по средней скорости.
- Для гарантии худшего времени — выбирать другие алгоритмы (heapsort или mergesort).
- Для частичных сортировок больших массивов — использовать quickselect/partial_sort или кучу; сортировка выбором годится только при очень малом $k$ и простоте реализации.