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

Question

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

    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, вы можете пошагово пройти по коду, наблюдая за значениями переменных; если нет, вы можете вставить операторы печати в нескольких местах и ​​вручную проверить, что вы видите, с тем, что вы ожидали.

---

ОБНОВЛЕНИЕ I

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

ОБНОВЛЕНИЕ II

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

Answer 2

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

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();
    }
}

}

Answer 3

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

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

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

Answer 4

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

Пузырьковая сортировка не подходит для сортировки. Вы можете прочитать Для чего нужна пузырьковая сортировка? для подробностей.

Answer 5

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

попробуйте этот урок.

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

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

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

Answer 6

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

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

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