-2

如何使用下面的实现在 Java 中使用 Linked List 实现“MergeSort”？这是我对链表的实现：

public class LinkedList {
    Node tail;

    public LinkedList() {
        tail = null;
    }

    public LinkedList(Object value) {
        tail = new Node(value);
        tail.setNext(tail);
    }

    public void purge() {
        tail = null;
    }

    public Object getFirst() {
        Node rigby = tail.getNext();
        return rigby.getValue();
    }

    public Object getLast() {
        return tail.getValue();
    }

    public boolean isEmpty() {
        return (tail == null);
    }

    public void assign(LinkedList list) {
        if (list.isEmpty())
            tail = null;
        else {
            this.append(list.tail.getNext().getValue());

            Node tmp = list.tail.getNext();
            while (tmp != list.tail) {
                tmp = tmp.getNext();
                this.append(tmp.getValue());
            }
        }
    }

    public void append(Object value) {
        if (this.isEmpty()) {
            tail = new Node(value);
            tail.setNext(tail);
        } else {
            Node tmp = new Node(value);
            tmp.setNext(tail.getNext());
            tail.setNext(tmp);
            tail = tmp;
        }
    }

    public void prepend(Object value) {
        if (this.isEmpty()) {
            tail = new Node(value);
            tail.setNext(tail);
        } else {
            Node tmp = new Node(value);
            tmp.setNext(tail.getNext());
            tail.setNext(tmp);
        }
    }

    public boolean equals(LinkedList list) {
        if (this != list) {
            // temp variables
            Node mordecai = tail.getNext();
            Node rigby = list.tail.getNext();
            // previouses
            Node prev = tail;
            Node prev2 = list.tail;
            while (true) {
                if (mordecai.getValue().getClass().getName() == "Node") {
                    if (!mordecai.getValue().equals(rigby.getValue()))
                        return false;
                } else {
                    if (!mordecai.getValue().toString().equals(rigby.getValue().toString()))
                        return false;
                }
                prev = mordecai;
                mordecai = mordecai.getNext();
                prev2 = rigby;
                rigby = rigby.getNext();

                if ((prev == tail) && (prev2 == list.tail))
                    return true;
                if ((prev == tail) || (prev2 == list.tail))
                    return false;
            }

        }
        return true;
    }


    public void extract(Object value) {
        if (!this.isEmpty()) {
            Node tmp = tail.getNext();
            Node prev = tail;
            while (true) {
                if (tmp.getValue().equals(value)) {
                    prev.setNext(tmp.getNext());
                    break;
                }
                prev = tmp;
                tmp = tmp.getNext();

                if (prev == tail)
                    break;
            }
        }
    }

    public String toString() {
        if (this.isEmpty()) {
            return null;
        } else {
            String str = "";
            Node tmp = tail.getNext();
            str += tmp.getValue().toString();
            while (tmp != tail) {
                str += "  ->  ";
                tmp = tmp.getNext();
                str += tmp.getValue().toString();
            }
            return str;
        }
    }


    class Node {
        Object data;
        Node next;

        public Node(Object value) {
            data = value;
        }

        public Node(Object value, Node pointer) {
            data = value;
            next = pointer;
        }

        public Object getValue() {
            return data;
        }

        public void setValue(Object value) {
            data = value;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node pointer) {
            next = pointer;
        }

        public boolean equals(Node var) {
            if (next.equals(var.next)) {
                if (data.getClass().getName() == "Node") {
                    if (data.equals(var.data))
                        return true;
                } else {
                    if (data.toString().equals(var.data.toString()))
                        return false;
                }

            }
            return false;
        }
    }
}

我不能正面或反面，分析让我偏头痛。我需要这方面的帮助。我已经搜索过，我只找到了一个 Array 实现。

4

2 回答 2

1

Collections.sort()merge sort在java中是一个

 public static <T> void sort(List<T> list,
                        Comparator<? super T> c)

Java 文档

排序算法是经过修改的合并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。该算法提供有保证的 n log(n) 性能。指定的列表必须是可修改的，但不必调整大小。这个实现将指定的列表转储到一个数组中，对数组进行排序，并遍历列表，从数组中的相应位置重置每个元素。这避免了由于尝试对链表进行排序而导致的 n2 log(n) 性能。

于 2012-09-06T08:42:30.540 回答
0

如果您从解决方案的抽象描述开始工作，您以后的课程作业会做得更好；) http://en.wikipedia.org/wiki/Merge_sort

于 2012-09-06T09:01:02.333 回答