Сортировка слиянием
|
Следует принципу «разделяй и властвуй», согласно которому массив данных разделяется на равные части, которые сортируются по-отдельности. После они сливаются, в результате получается отсортированный массив.
|
Сортировка, в результате которой относительная последовательность элементов не изменилась, называется устойчивой.
При неустойчивой сортировке элементы в массиве меняются местами
Какие алгоритмы сортировки обеспечивают стабильность?
В таблице ниже представлена стабильность рассмотренных алгоритмов сортировки
Алгоритм сортировки
|
Стабильность
|
Сортировка пузырьком
|
✓
|
Сортировка выбором
|
✘
|
Быстрая сортировка
|
✘
|
Сортировка кучей
|
✘
|
Сортировка вставками
|
✓
|
Сортировка слиянием
|
✓
| Можно ли оценить эффективность алгоритмов сортировки?
Да, это возможно.
Критериями оценки эффективности алгоритма сортировки является пространственная и временная сложность.
Означает количество памяти, затраченной на выполнение алгоритма. Пространственная сложность включает вспомогательную память и память для хранения входных данных.
Вспомогательная память – дополнительное место, занимаемое алгоритмом помимо входных данных. Она учитывается при расчете пространственной сложности алгоритмов.
Do'stlaringiz bilan baham: |
