Bucket Сортировка с помощью указателей и двух массивов структур

Question

Я работаю над приложением телефонной книги, где я хочу сортировать узлы, представляющие каждую запись, в соответствии с именем клиента. Я хочу использовать алгоритм сортировки ковша, где у меня есть два массива структур связанного списка.

Уловка заключается в том, что я не хочу использовать удаление и конструкцию для перемещения узлов через ведра.

Есть ли более простой способ, используя указатели? Перемещение указателей через ведра может быть намного проще, но я не знаю, как его реализовать. Я делаю это на C, но помощь на любом другом языке приветствуется.

Я ценю вашу помощь.

Answer 1

Это действительно зависит от того, как хранятся записи. Если вы сохраняете каждую запись в ячейке связанного списка, вы можете выполнять сортировку в виде ведра с постоянным объемом памяти, просто перемещая элементы из исходного списка и в ведра. Это потребует от вас использования указателей и перекодировки указателей, но это не так сложно, как кажется. Вы просто сплайсируете ячейки из основного списка и в ведра для сортировки.

Один вопрос - есть ли причина, по которой вы хотите использовать сортировку ведра для сортировки имен? Вы можете сортировать строки, используя сортировку в виде корзины, но для этого вам почти наверняка понадобится больше двух ведер; вероятно, у вас будет один для каждой буквы алфавита, а один для «здесь нет букв». Если у вас есть связанный список, вам может потребоваться рассмотреть возможность сортировки слияния как возможность, так как это не так сложно реализовать и имеет отличные гарантии времени выполнения.