Недавно в одном из интервью, после некоторых первоначальных вопросов о алгоритмах сортировки, например, как вы пишете QuickSort или разницу между QuickSort и MergeSort, интервьюер спросил, понимаете ли вы разницу между стабильным и нестабильным алгоритмом сортировки? Этот вопрос был новым для моего читателя, поэтому он говорит, извините, никогда не слышал об этом. На этом история закончилась, и Интервьюер перешел к следующему вопросу, но, как и многие из нас, мой читатель продолжил, чтобы узнать больше о оставшихся без ответа вопросах, и в конечном итоге он спросил меня, что означает стабильный и нестабильный алгоритм сортировки? Некоторые из вас могут слышать об этом, и многие из вас могут не знать об этом различии, я постараюсь ответить на этот вопрос в этой статье.
Алгоритм сортировки называется стабильным, если он поддерживает относительный порядок чисел / записей в случае связи, т.е. если вам нужно отсортировать 1 1 2 3, то если вы не измените порядок первых двух, чем ваш алгоритм стабильный, но если поменять их местами, он станет нестабильным, несмотря на то, что общий результат или порядок сортировки останутся прежними
Эта разница становится более очевидной, когда вы сортируете объекты, например, сортируете пары ключ-значение по ключам . В случае стабильного алгоритма исходный порядок пары ключ-значение сохраняется, как показано в следующем примере.
На самом деле, интервьюер может задать этот вопрос в качестве продолжения быстрой сортировки и сортировки слиянием, если вы забудете упомянуть эти понятия. Одно из основных различий между быстрой сортировкой и сортировкой слиянием заключается в том, что ранее она была нестабильной, но сортировка слиянием — это алгоритм устойчивой сортировки.
Стабильный алгоритм против нестабильного
Предположим, вам нужно отсортировать следующие пары ключ-значение в порядке возрастания ключей:
|
1
|
INPUT: (4,5), (3, 2) (4, 3) (5,4) (6,4) |
Теперь есть два возможных решения для двух пар, где ключ одинаков, то есть (4,5) и (4,3), как показано ниже:
|
1
2
3
|
OUTPUT1: (3, 2), (4, 5), (4,3), (5,4), (6,4)OUTPUT2: (3, 2), (4, 3), (4,5), (5,4), (6,4) |
Алгоритм сортировки, который будет производить первый вывод, будет называться стабильным алгоритмом сортировки, поскольку сохраняется исходный порядок равных ключей. Вы можете видеть, что (4, 5) предшествует (4,3) в порядке сортировки, который был исходный порядок, т.е. в данном входе, (4, 5) предшествует (4,3).
С другой стороны, алгоритм, который производит второй вывод, будет известен как нестабильный алгоритм сортировки, поскольку порядок объектов с одинаковым ключом не поддерживается в отсортированном порядке. Вы можете видеть, что во втором выводе (4,3) предшествует (4,5), чего не было в исходном вводе.
Теперь большой вопрос: каковы некоторые примеры стабильных и нестабильных алгоритмов сортировки? Ну, вы можете разделить все известные алгоритмы сортировки на отсортированные и несортированные. Некоторые примеры устойчивых алгоритмов: сортировка слиянием, сортировка вставкой, сортировка по пузырькам и сортировка по бинарному дереву. В то время как QuickSort , Heap Sort и Selection sort являются нестабильным алгоритмом сортировки.
Если вы помните, метод Collections.sort () из инфраструктуры Java Collection использует итеративную сортировку слиянием, которая является устойчивым алгоритмом. Это также делает намного меньше сравнения, чем NLog (N) в случае, если входной массив частично отсортирован.
Если вы хотите узнать больше об этой теме, я предлагаю вам прочитать хорошую книгу Томаса Х. Кормена «Структура данных и алгоритмы», например, « Введение в алгоритмы ».
Говорят, что картинка стоит больше 1000 слов, поэтому давайте посмотрим на изображение, которое объясняет, как работает стабильная и нестабильная сортировка:
Это все о разнице между стабильным и нестабильным алгоритмом сортировки . Просто помните, что если в отсортированном выводе сохраняется исходный порядок равных ключей или чисел, алгоритм называется алгоритмом сортировки. Некоторые популярные примеры устойчивых алгоритмов сортировки — сортировка слиянием, сортировка вставкой и пузырьковая сортировка.
Дальнейшее чтение
- Структура данных и алгоритм сделали проще
- Алгоритмы 4-е издание Роберт Седжвик
- 5 книг для изучения структуры данных и алгоритмов
- 20 вопросов по строковому алгоритму
- 20 вопросов интервью на основе массива
- 15 Вопросы структуры данных и алгоритма
Спасибо за чтение этой статьи. Если вам нравится этот вопрос интервью и мое объяснение, поделитесь с друзьями и коллегами. Если у вас есть какие-либо вопросы или пожелания, оставьте комментарий.
| Ссылка: | Разница между стабильным и нестабильным алгоритмом сортировки? от нашего партнера JCG Джавина Пола в блоге Javarevisited . |