使用 java 的链表归并排序

Question

我想只用链表实现合并排序而不用任何数组，使用java。但是我陷入了一个逻辑错误；我的代码消除了一些输入并对剩余部分进行排序。我应用了三个 class: Divide , Merg , MergSort 如下：

public class Divide {

    List firstList = new List();
    List secondList = new List();

    public int GetLength(List list) {
        int Length = 0;
        Link temp = new Link();
        temp.next = list.head.next;
        while (temp.next != null) {
            temp.next = temp.next.next;
            Length++;
        }

        return Length;
    }

    public List rightSide(List list) {
        int Length = GetLength(list);
        Link temp = new Link();
        temp.next = list.head.next;

            for (int i = 1; i <= Math.floor(Length / 2); i++) {
                firstList.Insert(temp.next.data);
                temp.next = temp.next.next;
            }
            return firstList;
    }

    public List leftSide(List list) {
        int Length = GetLength(list);
        Link temp = new Link();
        temp.prev = list.head.prev;

            for (int i = 1; i <= Math.ceil(Length / 2); i++) {
                secondList.Insert( temp.prev.data);
                temp.prev =  temp.prev.prev;
            }
            return secondList;
        }
    }

合并：

public class Merg {

    public List MergedList = new List();
    private  List Temp = new List();

    public List Merg (List one, List two)
    {
        Link onelink = new Link();
        Link twolink = new Link();

        onelink.next = one.head.next;
        twolink.next = two.head.next;

        while (onelink.next!= null || twolink.next!= null)
        {

            if(onelink.next!= null && twolink.next != null)
            {
              if(onelink.next.data < twolink.next.data)
              {
                  Temp.Insert(onelink.next.data);
                  onelink.next = onelink.next.next;
              }
              else
              {
                  Temp.Insert(twolink.next.data);
                  twolink.next = twolink.next.next;
              }

            }

            if (onelink.next != null && twolink.next == null)
            {
                Temp.Insert(onelink.next.data);
                onelink.next = onelink.next.next;
            }
            if (twolink.next != null && onelink.next == null)
            {
                Temp.Insert(twolink.next.data);
                twolink.next = twolink.next.next;
            }

        }

        if (Temp.head.next.data > Temp.head.prev.data)
        {
            while (Temp.head.next != null)
            {
                MergedList.Insert(Temp.head.next.data);
                Temp.head.next = Temp.head.next.next;
            }
        }

        else
        {
            MergedList.head.next = Temp.head.next;
        }


        return MergedList;
    }

}

合并排序：

public class MergSort {

    public List mergSort (List list)
    {
        Divide divide = new Divide();
        Merg merg = new Merg();

        if (divide.GetLength(list) > 1) {
            return merg.Merg(mergSort(divide.leftSide(list)), mergSort(divide.rightSide(list)));
        }
        else
        {
            return list;
        }
    }
}

虽然我也写了link和list class，但是我觉得里面没有问题。（但是，如果有必要，我会提及它们）现在，当我导入一些输入时：{100,3,1,7,6} 输出为：3,6,7,100。（1 已被淘汰！）或另一个示例：{100,3,1} 输出为：1,100（3 在哪里？？）

不知道有没有人能帮帮我...

Link:

public class Link {
    public double data;
    public Link prev;
    public Link next;
}

列表：

public class List {
    public Link head = new Link();

    public void setHead(Link head) {
        this.head = head;
        head.prev = null;
        head.next = null;
    }

    public void Insert(double x)
    {
        Link link = new Link();
        link.data = x;
        if (head.next == null)
        {
            head.next = link;
            head.prev = link;
        }
        else
        {
            head.next.prev = link;
            link.next = head.next;
            head.next = link;
        }
    }

    public Link delete()
    {
        Link temp = new Link();
        temp = head;
        head = head.next;
        return temp;
    }

    public Link search(double x)
    {
        Link link = new Link();
        link.next = head;
        while (link.next.data != x)
        {
            link.next = link.next.prev;
        }

        return link.next;
    }
}

Answer 1

我已经调试了很多，但我无法理解你的Divide class。你根本不需要它。

public class MergSort {

    public List mergSort(List list) {
        Divide divide = new Divide();
        Merg merg = new Merg();
        int n = list.getLength();
        if (n > 1) {
//            return merg.Merg(mergSort(divide.leftSide(list)), mergSort(divide.rightSide(list)));
            Link cursor = list.head.next;
            List left = new List();
            List right = new List();
            // for (i = 0; ....... i will be 0 if head is not dummy
            for (int i = 1; cursor != null; i++) {
                if (i <= n/2)
                    left.Insert(cursor.data);
                else
                    right.Insert(cursor.data);
                cursor = cursor.next;
            }
            left = mergSort(left);
            right = mergSort(right);

            return merg.Merg(left, right);

        } else {
            return list;
        }
    }
}

在您的 List class 中创建一个 getLength() 方法。它应该在 List class 中，因为您需要列表的长度。

public int getLength() {
    int Length = 0;
    Link temp = head.next;
    while (temp != null) {
        temp = temp.next;
        Length++;
    }

    return Length;
}

此外，将您的 Link class 重命名为 Node。因为 Link 表示对象之间的 link 或节点之间的边。你真正想要的是 Node。令人困惑。

在您的 List class 中，您定义了 head 如下：

public Link head = new Link();

我不明白你为什么需要 dummy headed linked list。

具有虚拟头部的 linked 列表基本上是一个没有值的头部，因此是虚拟的。

因为你的假头，你从 i = 1 Divide class 开始你的 for 循环。为什么要把事情复杂化？如果你真的需要一个假人头，那就保留它或这样定义它：

public Link head;
// don't instantiate the head. It's just a reference

此外，您似乎创建了一个半圆形 linked 列表。我的意思是 head.prev 指向列表中的最后一个 link/node。如果你真的想要一个循环 linked 列表然后将你的 tail.next 指向头部。

这是循环 linked 列表的样子：

或者，如果您不想要循环列表，则不要将 head.prev 指向最后一个对象。

在 List.java 中的 Insert() 方法中：

if (head.next == null)
{
    head.next = link;
    // remove head.prev = link;
}

使用 java 的链表归并排序

Linked list merge sort using java

java

sorting

mergesort

linked-list