algorithm
Сортировка

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language
Поиск…


параметры

параметр Описание
стабильность Алгоритм сортировки является стабильным, если он сохраняет относительный порядок равных элементов после сортировки.
На месте Алгоритм сортировки на месте, если он сортирует, используя только O(1) вспомогательную память (не считая массив, который нужно сортировать).
Наилучшая сложность случая Алгоритм сортировки имеет наилучшую временную сложность O(T(n)) если ее время работы не менее T(n) для всех возможных входов.
Средняя сложность случая Алгоритм сортировки имеет среднюю временную сложность O(T(n)) если ее время работы, усредненное по всем возможным входам , равно T(n) .
Худшая сложность случая Алгоритм сортировки имеет худшую временную сложность O(T(n)) если ее время работы не превышает T(n) .

Стабильность при сортировке

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

Таким образом, алгоритм сортировки считается стабильным, если два объекта с равными ключами отображаются в том же порядке в отсортированном виде, что и во входном несортированном массиве.

Рассмотрим список пар: 

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

Теперь мы отсортируем список, используя первый элемент каждой пары.

При стабильной сортировке этого списка будет выводиться следующий список: 

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

Потому что (9, 3) появляется после (9, 7) в исходном списке.

Нестабильная сортировка выведет следующий список: 

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

Нестабильная сортировка может генерировать тот же результат, что и стабильный, но не всегда.

Известные стабильные сорта:

Известные неустойчивые сорта:



Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow