Предположим, что мой вход (a, b и c различает равные ключи)
1 6a 8 3 6b 0 6c 4
Моя сортировка сортировки будет сохраняться как (отбрасывание a, b и c info!)
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
который даст мне результат
0 1 3 4 6 6 6 8
Итак, как этот стабильный вид? Я не уверен, как это "поддерживать относительный порядок записей с равными ключами".
Пожалуйста, объясните.
Простой, на самом деле: вместо простого счетчика для каждого "ведра" это связанный список.
То есть вместо
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, зная, что он может иметь другую информацию, отличающую его от других элементов с тем же ключом, вы не просто увеличиваете счетчик для ведра x (который будет отбрасывать всю эту дополнительную информацию).
Вместо этого у вас есть связанный список (или аналогично упорядоченная структура данных с добавлением постоянного времени) для каждого ведра, и вы добавляете этот элемент в конец списка для bucket x при сканировании ввода слева направо.
Поэтому вместо использования O(k) пробела для счетчиков k у вас есть O(k) изначально пустые списки, сумма которых будет n в конце части "подсчета" алгоритма. Этот вариант сортировки по-прежнему будет O(n + k) по-прежнему.
Чтобы понять, почему учетная сортировка стабильна, вам нужно понять, что сортировка подсчета может использоваться не только для сортировки списка целых чисел, она также может использоваться для сортировки списка элементов, ключ которых является целым числом, и эти элементы будут сортироваться по их ключам, имея дополнительную информацию, связанную с каждым из них.
Пример сортировки, который сортирует элементы с дополнительной информацией, поможет вам понять это. Например, мы хотим сортировать три акции по их ценам:
[(GOOG 3), (CSCO 1), (MSFT 1)]
Здесь цены акций - это целые ключи, а имена запасов - их ассоциированная информация.
Ожидаемый результат сортировки должен быть:
[(CSCO 1), (MSFT 1), (GOOG 3)]
(containing both stock price and its name,
and the CSCO stock should appear before MSFT so that it is a stable sort)
Будет подсчитан массив counts для его сортировки (пусть цены на акции могут быть только от 0 до 3):
counts array: [0, 2, 0, 1] (price "1" appear twice, and price "3" appear once)
Если вы просто сортируете целочисленный массив, вы можете пройти через массив counts и вывести "1" дважды и "3" один раз, и это будет сделано, и после этого весь массив counts станет массивом с нулевым значением.
Но здесь мы также хотим иметь имена запасов в сортировке. Как мы можем получить эту дополнительную информацию (кажется, массив counts уже отбрасывает эту часть информации)? Ну, связанная информация сохраняется в исходном несортированном массиве. В несортированном массиве [(GOOG 3), (CSCO 1), (MSFT 1)] у нас есть как название запаса, так и его цена. Если мы узнаем, какая позиция (GOOG 3) должна быть в конечном отсортированном массиве, мы можем скопировать этот элемент в отсортированную позицию в отсортированном массиве.
Чтобы получить конечную позицию для каждого элемента в отсортированном массиве, в отличие от сортировки целочисленного массива, вы не используете массив counts напрямую для вывода отсортированных элементов. Вместо этого подсчет сортировки имеет дополнительный шаг, который вычисляет совокупный массив сумм из массива counts:
counts array: [0, 2, 2, 3] (i from 0 to 3: counts[i] = counts[i] + counts[i - 1])
Этот совокупный массив сумм сообщает нам каждую позицию значения в конечном отсортированном массиве в настоящее время. Например, counts[1]==2 означает, что текущий элемент со значением 1 должен быть помещен в слот 2nd в отсортированном массиве. Интуитивно, потому что counts[i] является суммарной суммой слева, она показывает, сколько меньших элементов находится перед значением ith, которое сообщает вам, где должно быть положение для значения ith.
Если в первый раз появится фондовый рынок за 1 доллар, он должен быть выведен на вторую позицию отсортированного массива, и если в первый раз появится ценовой запас за 3 доллара, он должен быть выведен на третью позицию отсортированного массива, Если появится фон $1, и его элемент будет скопирован в отсортированный массив, мы уменьшим его количество в массиве counts.
counts array: [0, 1, 2, 3]
(so that the second appearance of $1 price stock position will be 1)
Таким образом, мы можем итерировать несортированный массив назад (это важно для обеспечения стабильности), проверить его позицию в отсортированном массиве в соответствии с массивом counts и скопировать его в отсортированный массив.
sorted array: [null, null, null]
counts array: [0, 2, 2, 3]
iterate stocks in unsorted stocks from backwards
1. the last stock (MSFT 1)
sorted array: [null, (MSFT 1), null] (copy to the second position because counts[1] == 2)
counts array: [0, 1, 2, 3] (decrease counts[1] by 1)
2. the middle stock (CSCO 1)
sorted array: [(CSCO 1), (MSFT 1), null] (copy to the first position because counts[1] == 1 now)
counts array: [0, 0, 2, 3] (decrease counts[1] by 1)
3. the first stock (GOOG 3)
sorted array: [(CSCO 1), (MSFT 1), (GOOG 3)] (copy to the third position because counts[3] == 3)
counts array: [0, 0, 2, 2] (decrease counts[3] by 1)
Как вы можете видеть, после сортировки массива массив counts (который равен [0, 0, 2, 2]) не становится массивом с нулевым нулем, например сортировкой массива целых чисел. Массив counts не используется, чтобы указать, сколько раз целое число появляется в несортированном массиве, вместо этого оно используется, чтобы указать, в какой позиции элемент должен находиться в конечном отсортированном массиве. И так как мы уменьшаем счетчик каждый раз, когда мы выводим элемент, мы по существу делаем элементы с одним и тем же ключом. Поэтому нам нужно итерировать несортированный массив назад, чтобы обеспечить его стабильность.
Вывод:
Поскольку каждый элемент содержит не только целое число как ключ, но и некоторую дополнительную информацию, даже если их ключ один и тот же, вы можете сказать, что каждый элемент отличается другой информацией, поэтому вы сможете определить, является стабильным алгоритмом сортировки (да, это стабильный алгоритм сортировки, если он выполняется соответствующим образом).
Литература:
Некоторые хорошие материалы, объясняющие сортировку и ее стабильность:
Ваше решение не является полным сортировщиком и отбрасывает связанные значения.
Здесь полный алгоритм сортировки счетчика.
После вычисления гистограммы:
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
вам нужно рассчитать накопленные суммы - каждая ячейка будет содержать количество элементов меньше или равно этому значению:
0(1) 1(2) 3(3) 4(4) 6(7) 8(8)
Теперь вы начинаете с конца своего исходного списка и возвращаетесь назад.
Последний элемент 4. Есть 4 элемента, которые меньше или равны 4. Таким образом, 4 перейдет на 4-ю позицию. Вы уменьшаете счетчик на 4.
0(1) 1(2) 3(3) 4(3) 6(7) 8(8)
Следующий элемент 6c. Есть 7 элементов меньше или равно 6. Таким образом, 6c перейдет на 7-ю позицию. Опять же, вы уменьшаете счетчик на 6.
0(1) 1(2) 3(3) 4(3) 6(6) 8(8)
^ next 6 will go now to 6th position
Как вы можете видеть, этот алгоритм является стабильным. Порядок для элементов с одним и тем же ключом будет сохранен.
Если ваши три значения "6" отличаются друг от друга, то сортировка счета неверна (она отбрасывает информацию о значениях, которые истинная сортировка не делает, поскольку истинный вид только переупорядочивает значения).
Если ваши три значения "6" не различаются, сортировка стабильна, потому что у вас есть три неотличимых "6" на входе и три в выходе. Бессмысленно говорить о том, были ли они или не были "перенаправлены": они идентичны.
Концепция нестабильности применяется только тогда, когда значения имеют некоторую связанную информацию, которая не участвует в заказе. Например, если вы сортировали указатели на эти целые числа, тогда вы могли бы "рассказать разницу" между тремя 6, просмотрев их разные адреса. Тогда было бы целесообразно спросить, стабилен ли какой-либо конкретный вид. Сортировка счета, основанная на целых значениях, тогда не будет сортировать указатели. Сортировка счета, основанная на значениях указателя, не будет упорядочивать их по целочисленному значению, а по адресу.