Чтобы понять, почему подсчет сортировки стабилен, вам необходимо понять, что сортировка подсчета может использоваться не только для сортировки списка целых чисел, но также для сортировки списка элементов, ключом которых является целое число, и этих элементов. будут отсортированы по ключам с дополнительной информацией, связанной с каждым из них.
Пример сортировки с подсчетом, которая сортирует элементы с дополнительной информацией, поможет вам понять это. Например, мы хотим отсортировать три акции по их ценам:
[(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)
Для сортировки будет рассчитан массив count (скажем, цены на акции могут быть только от 0 до 3):
counts array: [0, 2, 0, 1] (price "1" appear twice, and price "3" appear once)
Если вы просто сортируете массив целых чисел, вы можете пройти через массив count и вывести «1» дважды и «3» один раз, и все готово, и после этого весь массив count станет массивом с нулем.
Но здесь мы хотим, чтобы названия сортировки также были указаны в результатах сортировки. Как мы можем получить эту дополнительную информацию (кажется, что массив count уже отбрасывает эту информацию)? Ну, связанная информация хранится в исходном несортированном массиве . В несортированном массиве [(GOOG 3), (CSCO 1), (MSFT 1)] у нас есть как название акции, так и ее цена. Если мы узнаем, какая позиция (GOOG 3) должна быть в конечном отсортированном массиве, мы можем скопировать этот элемент в отсортированную позицию в отсортированном массиве.
Чтобы получить конечную позицию для каждого элемента в отсортированном массиве, в отличие от сортировки целочисленного массива, вы не используете массив count напрямую для вывода отсортированных элементов. Вместо этого сортировка подсчета имеет дополнительный шаг, который вычисляет массив накопленной суммы из массива count:
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 доллар и его элемент будет скопирован в отсортированный массив, мы уменьшим его количество в массиве count.
counts array: [0, 1, 2, 3]
(so that the second appearance of $1 price stock's position will be 1)
Таким образом, мы можем перебрать несортированный массив в обратном направлении (это важно для обеспечения стабильности), проверить его позицию в отсортированном массиве в соответствии с массивом count и скопировать его в отсортированный массив.
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)
Как вы можете видеть, после сортировки массива массив count (который равен [0, 0, 2, 2]) не становится массивом с нулем, как сортировка массива целых чисел. Массив counts не используется, чтобы указать, сколько раз целое число появляется в несортированном массиве, вместо этого он используется, чтобы указать, какой позиции должен быть элемент в конечном отсортированном массиве. И так как мы уменьшаем счетчик каждый раз, когда выводим элемент, мы, по сути, делаем элементы с конечной позицией следующего появления того же ключа меньше. Вот почему нам нужно выполнить итерацию несортированного массива в обратном направлении, чтобы обеспечить его стабильность.
Вывод:
Поскольку каждый элемент содержит не только целое число в качестве ключа, но также некоторую дополнительную информацию, даже если их ключ одинаков, вы можете сказать, что каждый элемент отличается, используя дополнительную информацию, поэтому вы сможете определить, является ли он является стабильным алгоритмом сортировки (да, это стабильный алгоритм сортировки, если он реализован надлежащим образом).
Ссылка:
Несколько хороших материалов, объясняющих счетную сортировку и ее стабильность: