ВУЗ:
Составители:
Рубрика:
Исходный
массив
Опорный
Неопределенная
часть
элемент
Опорный
элемент
5,
Неопределенная
часть
5 3
iI
Опорный
элемент
5,
52
Неопределенная
часть
" "
5
3
:~?:
, , .
Опорный
82
Неопределенная
часть
элемент
8,
5 3
Опорный
элемент
5,
52
5
3
4
7
Множества
81
и
52
определены
51
>S
.-
:а
:r:
:I:
Ф
Q..~
О
Ф
с
с:
0(1)
52
Первое
7
5
3
разбиение
Вставляем
опорный
элемент
между
множествами
51
и
52
РИСУНОК
20.
Разбиение
массива
в
алгоритме
ашскзоп
в
среднем
варианте
Формальный
анализ
алгоритма
quicksort
для
среднего
варианта
показывает,
что
его
сложность
является
величиной
O(n*log n).
Таким
образом,
с
большими
массивами
алгоритм
quicksort
работает
значительно
быстрее,
чем
алгоритм
insertionSort,
хотя
в
наихудшем
варианте
они
оба
имеют
приблизительно
одинаковое
быстродействие.
Алгоритм
quicksort
часто
используется
для
сортировки
больших
массивов.
Причина
его
популярности
заключается
в
исключительном
быстродействии,
несмотря
на
обескураживающие
оценки
наихудшего
варианта.
Дело
в
том,
что
этот
вариант
встречается
крайне
редко,
и
на
практике
алгоритм
quicksort
отлично
работает
с
относительно
большими
массивами.
Значительное
различие
между
оценками
сложности
в
среднем
и
наихудшем
вариантах
выделяет алгоритм
быстрой
сортировки
среди
остальных
алгоритмов,
рассмотренных
в
данной
главе.
Если
порядок
записи
элементов
в
исходном
массиве
является
"случайным",
алгоритм
quickSort
работает,
по
крайней
мере,
не
хуже
любого
другого
алгоритма,
43
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
