0

Есть двусвязный список который мне нужно отсортировать за O(n Log n) время. Я бы хотел использовать merge sort, но я никак не могу сообразить, как это реализовать путём расширения класса SplDoublyLinkedList из стандартной библиотеки PHP.

Основная проблема в том, что я не могу разделить SplDoublyLinkedList пополам без выделения дополнительной памяти. Если бы я имел объекты отдельных нод, я бы легко мог установить указатель next ноды из середины списка на null, и сохранить указатель на следующую ноду в отдельную переменную, таким образом получив уже два связных списка. Но SplDoublyLinkedList не позволяет провернуть такую операцию.

Я имею ввиду нечто подобное в Java:

node mergeSort(node h) 
    { 
        if (h == null || h.next == null) { 
            return h; 
        } 

        node middle = getMiddle(h); 
        node nextOfMiddle = middle.next; 

        middle.next = null; 

        node left = mergeSort(h); 
        node right = mergeSort(nextofmiddle); 

        node sortedlist = sortedMerge(left, right); 
        return sortedlist; 
    } 

Должен ли я действительно использовать SplDoublyLinkedList в этом случае, или мне лучше написать свою собственую реализацию связного списка?

5
  • А не проще список преобразовать в массив, отсортировать массив и преобразовать результат обратно в список?
    – tym32167
    4 июн 2019 в 6:30
  • @tym32167 нет, не проще, т.к. это требует дополнительного выделения памяти. 4 июн 2019 в 6:32
  • Требует, но без константного времени на доступ к любому элементу списка по индексу как вы хотите уложиться в nLogn?
    – tym32167
    4 июн 2019 в 6:35
  • @tym32167 так рекурсивная сортировка слиянием обеспечивает в точности это время, я же привёл пример выше. 4 июн 2019 в 6:38
  • а, ну да, логично, Log(n) операций по n, сорян, я что то тупанул
    – tym32167
    4 июн 2019 в 8:32

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.