Ручная сортировка связанного списка в Java (лексически)

Question

Я реализую свой собственный связанный список на Java. Класс node просто имеет поле строки, называемое «имя», и узел, называемый «ссылка». Прямо сейчас у меня есть класс тестового драйвера, который только вставляет несколько имен последовательно. Теперь я пытаюсь написать метод сортировки, чтобы упорядочить узлы в алфавитном порядке, но у меня проблемы с ним. Я нашел этот псевдокод пузырьков из чужого сообщения и попытался его реализовать, но он не полностью сортирует записи. Я не совсем уверен, почему. Любые предложения приветствуются!

private void sort() 
    { 
     //Enter loop only if there are elements in list 
     boolean swapped = (head != null); 

     // Only continue loop if a swap is made 
     while (swapped) 
     { 
      swapped = false; 

      // Maintain pointers 
      Node curr = head; 
      Node next = curr.link; 
      Node prev = null; 

      // Cannot swap last element with its next 
      while (next != null) 
      { 
       // swap if items in wrong order 
       if (curr.name.compareTo(next.name) < 0) 
       { 
        // notify loop to do one more pass 
        swapped = true; 

        // swap elements (swapping head in special case 
        if (curr == head) 
        { 
         head = next; 
         Node temp = next.link; 
         next.link = curr; 
         curr.link = temp; 
         curr = head; 
        } 
        else 
        { 
         prev.link = curr.link; 
         curr.link = next.link; 
         next.link = curr; 
         curr = next; 
        } 
       } 

       // move to next element 
       prev = curr; 
       curr = curr.link; 
       next = curr.link; 
      } 
     } 
    } 

Answer 1

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

Я бы сказал, до тех пор, пока кто-нибудь умнее или не будет более трудолюбив, вы должны попробовать отладить это самостоятельно. Если у вас есть IDE, например Eclipse, вы можете выполнить однократный код при просмотре значений переменных; если нет, вы можете вставлять заявления печати в несколько мест и вручную проверять, что вы видите, с тем, что вы ожидали.

---

UPDATE Я

Я скопировал свой код и протестировали его. Помимо того, что он сортируется в порядке убывания (что может и не быть тем, что вы намеревались), оно отлично работает для выборки из 0, 1 и 10 случайных узлов. Итак, где проблема?

ОБНОВЛЕНИЕ II

Тем не менее гадать, что могло быть в виду под «он не полностью сортировки записей.» Возможно, вы ожидаете лексикографической сортировки (т. Е. «A» до «B»), и это не выходит, как планировалось, для слов со смешанным верхним/нижним регистром. Решением в этом случае является использование метода StringcompareToIgnoreCase(String str).

Answer 2

Это не может быть решение, которое вы ищете, но это хорошо и просто. Может быть, ты ленив, как я.

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

Таким образом, вы можете свободно реализовать Bubble Sort.

Answer 3

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

try this tutorial.

В принципе, вам нужен класс элемент для реализации java.lang.Comparable, в котором вы будете просто делегировать obj.name.compareTo(other.name)

, то вы можете использовать Collections.sort(yourCollection)

в качестве альтернативы вы можете создать java.util.Comparator, который знает, как сравнить ваши объекты.

Answer 4

Для получения хорошей производительности вы можете использовать Merge Sort. Его временная сложность - O (n * log (n)) и может быть реализована без накладных расходов памяти для списков.

Пузырь сортировки не подходит для сортировки. Вы можете прочитать What is a bubble sort good for? для деталей.

Answer 5

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

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

Вы можете прочитать все узлы в том порядке, в котором они находятся, и сохранить их в массиве. Сортируйте массив, а затем повторно привяжите узлы к резервному копированию. Я думаю, что сложность Big-Oh в этом случае была бы O (n^2), поэтому на самом деле достаточно сортировки пузырьков со связанным списком

Answer 6

Я сделал сортировку слияния в единственном списке, а ниже - код.

public class SortLinkedList { 

public static Node sortLinkedList(Node node) { 

    if (node == null || node.next == null) { 
     return node; 
    } 
    Node fast = node; 
    Node mid = node; 
    Node midPrev = node; 
    while (fast != null && fast.next != null) { 
     fast = fast.next.next; 
     midPrev = mid; 
     mid = mid.next; 
    } 
    midPrev.next = null; 
    Node node1 = sortLinkedList(node); 
    Node node2 = sortLinkedList(mid); 
    Node result = mergeTwoSortedLinkedLists(node1, node2); 
    return result; 
} 

public static Node mergeTwoSortedLinkedLists(Node node1, Node node2) { 
    if (null == node1 && node2 != null) { 
     return node2; 
    } else if (null == node2 && node1 != null) { 
     return node1; 
    } else if (null == node1 && null == node2) { 
     return null; 
    } else { 

     Node result = node1.data <= node2.data ? node1 : node2; 
     Node prev1 = null; 
     while (node1 != null && node2 != null) { 
      if (node1.data <= node2.data) { 
       prev1 = node1; 
       node1 = node1.next; 
      } else { 
       Node next2 = node2.next; 
       node2.next = node1; 
       if (prev1 != null) { 
        prev1.next = node2; 
       } 
       node1 = node2; 
       node2 = next2; 
      } 
     } 
     if (node1 == null && node2 != null) { 
      prev1.next = node2; 
     } 
     return result; 
    } 
} 

public static void traverseNode(Node node) { 
    while (node != null) { 
     System.out.print(node + " "); 
     node = node.next; 
    } 
    System.out.println(); 

} 

public static void main(String[] args) { 
    MyLinkedList ll1 = new MyLinkedList(); 

    ll1.insertAtEnd(10); 
    ll1.insertAtEnd(2); 
    ll1.insertAtEnd(20); 
    ll1.insertAtEnd(4); 
    ll1.insertAtEnd(9); 
    ll1.insertAtEnd(7); 
    ll1.insertAtEnd(15); 
    ll1.insertAtEnd(-3); 
    System.out.print("list: "); 
    ll1.traverse(); 
    System.out.println(); 
    traverseNode(sortLinkedList(ll1.start)); 

} 

}

Класс Узел:

public class Node { 
int data; 
Node next; 

public Node() { 
    data = 0; 
    next = null; 
} 

public Node(int data) { 
    this.data = data; 
} 

public int getData() { 
    return this.data; 
} 

public Node getNext() { 
    return this.next; 
} 

public void setData(int data) { 
    this.data = data; 
} 

public void setNext(Node next) { 
    this.next = next; 
} 

@Override 
public String toString() { 
    return "[ " + data + " ]"; 
} 

}

MyLinkedList Класс:

public class MyLinkedList { 
Node start; 

public void insertAtEnd(int data) { 
    Node newNode = new Node(data); 
    if (start == null) { 
     start = newNode; 
     return; 
    } 
    Node traverse = start; 
    while (traverse.getNext() != null) { 
     traverse = traverse.getNext(); 
    } 
    traverse.setNext(newNode); 
} 

public void traverse() { 
    if (start == null) 
     System.out.println("List is empty"); 
    else { 
     Node tempNode = start; 
     do { 
      System.out.print(tempNode.getData() + " "); 
      tempNode = tempNode.getNext(); 
     } while (tempNode != null); 
     System.out.println(); 
    } 
} 

}