#algorithm #sorting
Вопрос:
Недавно я изучаю алгоритм сортировки. Когда я изучаю сортировку по ведрам, у меня возникает вопрос о названии. Я знаю, что быстрая сортировка нестабильна, и вики говорит, что сортировка по ведрам здесь стабильна. Но по-прежнему ли он стабилен при использовании быстрой сортировки в сортировке по корзинам? Я не могу представить, что произойдет, может ли кто-нибудь мне помочь? Большое спасибо.
Комментарии:
1. Короткий ответ-нет.
2. Значит, причина в том, что Быстрая сортировка нестабильна, верно? @MBo
Ответ №1:
Любая нестабильная сортировка может изменить порядок элементов в корзине. Когда вы объединяете ведра, этот нарушенный порядок сохраняется.
Представьте, что у нас есть ведра 0..9 с точкой (5,5) , а ведро 20..29 содержит точки (22,3), (21,14), (22,7) . После нестабильной сортировки (по первому ключу) мы можем увидеть порядок, подобный (21,14), (22,7), (22,3) (просто пример). После слияния мы сможем увидеть
(5,5), (21,14), (22,7), (22,3)
где взаимный порядок пунктов с x=22 был изменен
Если мы используем, например, сортировку вставки внутри ведер, мы гарантируем, что результат будет
(5,5), (21,14), (22,3), (22,7)