Реализации алгоритмов/Сортировка/Быстрая: различия между версиями
Содержимое удалено Содержимое добавлено
м →Быстрая сортировка, нерекурсивный вариант: оформление |
комментарий |
||
Строка 2:
Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка <math>\Theta(n^2)</math>.
В качестве опорного элемента следует выбирать случайный элемент массива, чтобы получить гарантированное время сортировки <math>\Theta(n \log n)</math> в среднем. В случае, если использование случайных чисел нежелательно, в качестве опорного элемента можно выбрать, например, элемент в середине массива, но такие алгоритмы всё равно будут работать за <math>\Theta(n^2)</math> времени на некоторых специально-сконструированных массивах.муоср гомно
== [[Язык Си в примерах|C]] ==
| |||