Bucket Sort с использованием указателей и двух массивов структур

Question

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

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

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

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

Answer 1

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

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