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

Question

Я попытался написать метод сортировки связанного списка. Это тренировка Java для меня.

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

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

это то, что я устал:

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

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

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

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

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

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

Answer 2

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

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

prev будет нулевым, и мы врезаться.

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

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

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

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

до сих пор так good.And затем, после цикла второй итерации

5 -> 4 -> 3-> 2// prev все еще указывает на 4, 1 dissapears

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

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

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