1

这是我对合并排序列表的实现：

public class List {

        private final Object data;
        private final List next;
        public static final List NIL = new List(null, null);

        private List(Object d, List n) {
                data = d;
                next = n;
        }

        public static List list(Object d) {
                return new List(d, List.NIL);
        }

        public List append(List that) {
                return this.isEmpty() ?
                        that :
                        this.tail().append(that).push(this.head());
        }

        public Object nth(int n) {
                return this.isEmpty() || n < 0 ? null :
                                n == 0 ? this.head() :
                                this.tail().nth(n-1);
        }

        public List sort() {
                return mergesort(0, this.length());
        }

        private List mergesort(int top, int out) {
                List l = null;
                if (top < out - 1) {
                        int mid = (top + out) / 2;
                        mergesort(top, mid);
                        mergesort(mid, out);
                        l = merge(top, mid, out);
                }
                return l;
        }

        private List merge(int top1, int top2, int out) {
                List temp = List.NIL;
                List toReturn = this;
                int i = top1;
                int j = top2;
                int k = 0;

                while (i < top2 && j < out) {
                        Comparable one = (Comparable) this.nth(i);
                        Comparable two = (Comparable) this.nth(j);
                        if (one.compareTo(two) < 0) {
                                temp = temp.append(List.list(this.nth(i++)));
                        } else {
                                temp = temp.append(List.list(this.nth(j++)));
                        }
                }

                while (i < top2) temp = temp.append(List.list(this.nth(i++)));
                while (j < out) temp = temp.append(List.list(this.nth(j++)));

                for (k = 0; k < temp.length(); k++)
                        toReturn = toReturn.append(List.list(temp.nth(k)));

                return toReturn;

        }

}

这段代码似乎正确地实现了合并排序，但是在排序时我得到了错误的结果6 5 4 3 2 1：我得到了3 2 1 6 5 4，但我不知道为什么。我不确定这是否只是我还没有看到的一些小问题，或者它是否是一些基本问题。

4

0 回答 0