Как подсчет вида является стабильным видом?
Предположим, что мой вход (a,b и c различать равные ключи)
1 6a 8 3 6b 0 6c 4
Мой вид подсчета сохранит как (отбрасывание a,b и c информация!!)
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
который даст мне результат
0 1 3 4 6 6 6 8
Так, как этот стабильный вид? Я не уверен, как это "поддерживает относительный порядок записей с равными ключами".
Объясните.
2 ответа
На самом деле все просто: вместо простого счетчика для каждого «ведра» это связанный список.
То есть вместо
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
вы получите
0(.) 1(.) 3(.) 4(.) 6(a,b,c) 8(.)
(здесь я использую . для обозначения некоторого элемента в корзине).
Затем просто сбросьте их обратно в один отсортированный список:
0 1 3 4 6a 6b 6c 8
То есть, когда вы найдете элемент с ключом x , зная, что он может содержать другую информацию, которая отличает его от других элементов с таким же key, вы не просто увеличиваете счетчик для сегмента x (который отбрасывает всю эту дополнительную информацию).
Вместо этого у вас есть связанный список (или подобная упорядоченная структура данных с постоянным амортизированным добавлением) для каждого сегмента, и вы добавляете этот элемент в конец списка для сегмента x при сканировании ввод слева направо.
Таким образом, вместо использования пространства O (k) для k счетчиков, у вас есть O (k) изначально пустых списков, сумма длин которых будет n в конце «счетной» части алгоритма.Этот вариант сортировки с подсчетом по-прежнему будет O (n + k) , как и раньше.
Если ваши три значения «6» различимы, то ваша сортировка с подсчетом неверна (она отбрасывает информацию о значениях, чего не делает истинная сортировка, потому что истинная сортировка только переупорядочивает значения).
Если ваши три значения «6» не различимы, то сортировка является стабильной, потому что у вас есть три неотличимых «6» на входе и три на выходе. Бессмысленно говорить о том, «переупорядочены» они или нет: они идентичны.
Концепция нестабильности применяется только тогда, когда значения имеют некоторую связанную информацию, которая не участвует в порядке. Например, если вы сортируете указателей на эти целые числа, то вы можете «определить разницу» между тремя шестерками, глядя на их разные адреса. Тогда будет иметь смысл спросить, был ли какой-то конкретный сорт стабильным. Сортировка с подсчетом на основе целочисленных значений не будет сортировкой указателей. Подсчетная сортировка, основанная на значениях указателя, будет упорядочивать их не по целочисленному значению, а по адресу.