JAVA - сортировка связанного списка по убыванию

Question

Я пытался написать метод, который сортирует связанный список. это тренировка для меня.

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

Я пытался следовать за отладчиком, но я не могу понять, что я сделал неправильно

вот что я устал:

public IntList selectionSort()
{
    IntNode tempMax = _head;
    IntNode current = _head;
    IntNode fromHere = null;
    IntNode toHere = _head;
    IntNode prev = null;
    while(toHere != null)
    {
        current = toHere;
        tempMax = toHere;
        while (current != null)
        {
            if (current.getNext() != null && current.getNext().getValue() > tempMax.getValue())
                {
                    prev = current;
                    tempMax = current.getNext();
                    current = current.getNext();
                }
            else current = current.getNext();      
        }
        prev.setNext(prev.getNext().getNext());
        tempMax.setNext(toHere);            
        if (fromHere == null)
            _head = tempMax;
        else fromHere.setNext(tempMax);
        fromHere = tempMax;
        toHere = fromHere.getNext();
    }
    return this;
}

Answer 1

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

5 -> 1 -> 2 -> 3-> 4

prev будет нулевым, и мы потерпим крах.

Если мы сделаем с:

1 -> 4 -> 5 -> 3-> 2

на первой итерации вы получаете

5 -> 4 -> 1 -> 3-> 2

Пока все хорошо. И затем, после цикла второй итерации

5 -> 4 -> 3-> 2 // предыдущая все еще указывает на 4, 1 исчезает

5 -> 4 -> 4. // tempMax = toHere, так что tempMax-> tempMax и другие элементы пропали

Таким образом, проявление заключается в том, что prev в некотором роде недопустим.Существует быстрое исправление, например, пропуск позиции, когда toHere - максимум, но быстрые исправления - это не то, что вам нужно.Вы должны:

• Переосмыслить о некоторых особых случаях.Пустой список, один элемент, список уже отсортирован, список отсортирован в обратном порядке, в случайном порядке, (дублирующий элемент ??)
• Записать модульный тест для каждого случая
• Переписать свой алгоритм и избежать О, да, я забыл дело ... .Если вы не согласны, вам нужно всего лишь заменить первый элемент на каждом шаге на максимум, найденный на этом шаге.
• Избегайте переменных, которые имеют избыточную информацию.Например, tempMax всегда должно быть следующим за prev, поэтому достаточно только prev.В противном случае вы тратите клетки мозга, сохраняя согласованность.
• Проверьте еще раз набор.

Answer 2

Несколько советов:

• Если вы хотите наименьшее число, тогда current.getNext().getValue() > tempMax.getValue() должно иметь > вместо <

• Ваш код также потерпит неудачу, если первый элемент уже является минимальным значением, так как вы пытаетесь что-то сделать с null

• Я также вижу здесь дублированный код, current = current.getNext().Операции с указателями, как правило, трудны для кодирования, и написание более четкого кода, придерживающегося принципа «Не повторяйся сам», вероятно, поможет вам увидеть ошибки!

• Это поможет людям здесь помочь вам, если выпечатать сообщения об ошибках компилятора / среды выполнения