BubbleSort в двойном списке

Question

public Node get(int i) {  
    if (!isEmpty()) {  
        int j = 0;  
        Node element = head;  
        while (j++ < i) {  
            element = element.getNext();  
            if (element == null)  
                return null;  
        }  
        return element;  
    }  
    return null;  
}  



private void bubbleSort() {  
    for (int i = 0; i < size - 1; i++) {  
        boolean changed = false;  
        for (int j = 0; j < size - i - 1; j++) {  
            if (get(j + 1) != null) {  
                if (get(j).getValue() > get(j + 1).getValue()) {  
                    //System.out.println("Swapping: " + get(j).getValue() + " : " + get(j + 1).getValue());  
                    swap(get(j), get(j + 1));  
                    changed = true;  
                }  
            }  
        }  
        if (!changed)  
            return;  
    }  
}  

public void swap(Node first, Node mid) {  
    if (first == head)  
        head = mid;  
    if (mid == tail) {  
        tail = first;  
    }  
    first.setNext(mid.getNext());  
    mid.setPrev(first.getPrev());  
    first.setPrev(mid);  
    mid.setNext(first);  
}

Я не знаю, чего не хватает ...

Список, значение:62457После сортировки:267Вспомогательные выходы:Обмен: 6 <> 2Обмен: 6 <> 4Обмен: 6 <> 5

Пожалуйста, некоторые на помощь-я не знаю сортировать двойной связанный список .....

public void swap(Node first, Node mid) {  
    if (first == head)  
        head = mid;  
    if (mid == tail) {  
        tail = first;  
    }  
    first.setNext(mid.getNext());  
    mid.setPrev(first.getPrev());  
    first.setPrev(mid);  
    mid.setNext(first);  
}

См. Следующий код: функция подкачки.

Answer 1

Поскольку это, похоже, домашний вопрос, я не дам вам полного ответа.Я вполне уверен, что проблема заключается в вашей функции подкачки.Подумайте о том, чтобы нарисовать узлы на бумаге, пройтись по вашей функции подкачки и посмотреть, что происходит, на какие узлы указывать, куда.Рассмотрим предыдущий и следующий узлы узлов, которые вы меняете, и что вам также необходимо обновить их предыдущий / следующий!Если, конечно, ваши функции setNext и setPrev уже это делают.

Не стесняйтесь комментировать, если вам нужна дополнительная помощь.

Редактировать 1:

Кроме того, в качестве примечания,вместо того, чтобы использовать индексы (i и j) для отслеживания того, какой узел вы используете, рассмотрите возможность использования самого узла.И затем, когда вы вызываете i ++ или j ++, вместо этого вызываете node = node.getNext ().Таким образом, вы не добавляете дополнительный коэффициент n к вашей среде выполнения, и вы можете полностью исключить функцию свопинга.

Редактировать 2:

То, что я имею в виду, нарисовав это на бумаге, этозапишите каждое из значений на бумаге по порядку по горизонтали.Затем нарисуйте круг вокруг каждого и стрелку, указывающую на следующий круг и предыдущий круг в каждом случае.Нарисуй стрелки карандашом!Затем обновите стрелки, соответственно, по мере продвижения по вашей функции подкачки.Вам даже не нужно перемещать / стирать круги, просто сотрите стрелки и посмотрите, куда они указывают дальше.

Редактировать 3:

Итак, у вас есть два круга, которые вы хотите поменять местами.Эти круги имеют стрелки, идущие наружу, а их соседи имеют стрелки, идущие внутрь.Это 4 стрелки на круг (2 входа, 2 выхода, если вы не имеете дело с головой / хвостом).Поскольку вы передвигаетесь на 2 круга, это означает, что вы должны поменять всего 8 стрелок (если не имеете дело с головой / хвостом) - 4 на круг.Вы, вероятно, меняете только одну стрелку на setPrev / setNext.Это означает, что они обычно должны вызываться 8 раз в вашей функции подкачки.Вы звоните им только 4 раза.

Редактировать 4:

Вы обновляете prev / next замененных узлов, но не их соседей.Вы захотите сделать что-то вроде first.getNext (). SetPrev (second) и т. Д., Чтобы обновить ссылки / prev / next / стрелки соседей.

Редактировать 5:

Имейте в виду, что проверяются нулевые значения (вы не можете вызывать setPrev или setNext для нулевого значения, поэтому убедитесь, что когда вы устанавливаете prev / next соседа, фактический сосед существует(потому что prev не существует для головы, а next не существует для tail)).

Edit 6:

I думаю если вы говорите ты не делаешь домашнее задание ...;)

void swap(Node first, Node second) {
    Node firstPrev = first.getPrev();
    Node firstNext = first.getNext();
    Node secondPrev = second.getPrev();
    Node secondNext = second.getNext();

    if (firstPrev) {
        firstPrev.setNext(second);
    }
    if (firstNext) {
        firstNext.setPrev(second);
    }
    if (secondPrev) {
        secondPrev.setNext(first);
    }
    if (secondNext) {
        secondNext.setPrev(first);
    }

    second.setPrev(firstPrev);
    second.setNext(firstNext);
    first.setPrev(secondPrev);
    first.setNext(secondNext);
}