Я сейчас прохожу CRLS, и меня смущает сложность во времени операций сортировки со спутниковыми данными.
Допустим, у меня есть четыре точки данных, подобные этой:
{key: 3, satellite_data: big_array}
{key: 6, satellite_data: big_array}
{key: 2, satellite_data: big_array}
{key: 1, satellite_data: big_array}
{key: 1, satellite_data: big_array}
Iможет отсортировать эти данные в O (nlog (n)).
Но что мне делать, если я не хочу перемещать спутниковые данные во время процесса сортировки.
Опция № 1:
Перемещайте указатели на спутниковые данные только с помощью ключа.Это определенно экономит место и не увеличивает сложность времени.Но тогда я не понимаю, почему алгоритмы сортировки должны быть стабильными.Если указатель на спутниковые данные всегда привязан к клавише, то не возникнет проблем, если два ключа с одинаковым значением меняют положение.
Опция # 2:
Сначала сортируйте ключи без указателей наспутниковые данные, а затем выяснить, какой ключ переместился в какую новую позицию => создать таблицу перестановок.Затем эту таблицу перестановок можно использовать для перемещения спутниковых данных.Но создание таблицы перестановок значительно вредит сложности времени.
Форма цитирования CLRS:
Важным свойством подсчета сортировки является то, что она стабильна: числа с одинаковымизначения появляются в выходном массиве в том же порядке, что и во входном массиве.То есть он разрывает связи между двумя числами по правилу, согласно которому любое число, которое появляется первым во входном массиве, появляется первым в выходном массиве.Обычно свойство стабильности важно только тогда, когда спутниковые данные переносятся с сортируемым элементом.
Может кто-нибудь прояснить ситуацию?