Может кто-нибудь объяснить, что означает "стабильный" и "нестабильный" в отношении различных алгоритмов сортировки. Как определить, является ли алгоритм стабильным или нет, и какие приложения используют нестабильные алгоритмы сортировки, как правило, (поскольку они неустойчивы)?
В чем смысл "стабильного" и "неустойчивого" для различных алгоритмов сортировки?
Ответ 1
Если алгоритм сортировки называется "неустойчивым", это означает, что для любых элементов, которые ранжируются одинаково, порядок связанных членов не гарантированно остается неизменным при последовательных сортировках этой коллекции. Для "стабильной" сортировки привязанные записи всегда будут в том же порядке отсортированы.
Для примера приложений алгоритм быстрой сортировки нестабилен. Это будет отлично работать для чего-то вроде сортировки действий по приоритету (если два действия имеют равный приоритет, вы вряд ли будете заботиться о том, какие элементы галстука выполняются в первую очередь).
С другой стороны, стабильный алгоритм сортировки хорош для таких вещей, как таблица лидеров для онлайн-игры. Если вы использовали нестабильный сортировку, сортируя по точкам (например), пользователь, просматривающий отсортированные результаты на веб-странице, может испытывать разные результаты при обновлении страницы, а операции, такие как прохождение через результаты, будут работать неправильно.
Ответ 2
Устойчивая сортировка сохраняет порядок идентичных элементов. Любой тип может быть стабильным, добавив индекс строки к ключу. Нестабильные сортировки, такие как сортировка кучи и быстрая сортировка, например, не имеют этого свойства по своей сути, но они используются, потому что они, как правило, быстрее и легче кодируются, чем устойчивые. Насколько я знаю, нет никаких других причин использовать нестабильные сорта.