单链表上的归并排序 C++

Question

我正在寻找某种简单的方法来学习和理解这些合并排序。我在网上查看过，发现合并排序对于单链表确实很好，但我不明白如何做到这一点。这是我找到的网站： 维基百科合并排序 和 具体链接列表

我不确定要给你什么代码。我基本上只是在我的头文件中添加了这个，并且对此很陌生，所以我非常基础。提前感谢您的帮助:)

class Node
{
public:
    int data;
    Node* next;
    Node()
    {
        next = NULL;
        data = 0;
    }
};

class SLLIntStorage
{
public:
    Node* head;
    Node* current;
    Node* tail;

    void Read(istream&);
    void Write(ostream&);
    void setReadSort(bool);
    void sortOwn();
    void print();

    bool _sortRead;
    int numberOfInts;

    SLLIntStorage(const SLLIntStorage& copying)
    {

    }

    SLLIntStorage(void);
    ~SLLIntStorage(void);
};

Answer 1

如果你从维基百科上看这一段

从概念上讲，合并排序的工作方式如下
如下

1. 如果列表的长度为 0 或 1，则它已经排序。否则：
2. 将未排序列表分成两个大小约为一半的子列表。
3. 通过重新应用合并排序对每个子列表进行递归排序。
4. 将两个子列表合并回一个已排序的列表。

这非常简洁地告诉您需要做什么以及需要什么样的操作。第 2 句和第 4 句是您需要能够执行 Split() 和 Merge() 的操作。 Split 可以在您的 Node 类上实现，

// Split: removes half of the list and returns a pointer to it
Node* Node::Split()
{
} 

类似地 Merge 可以作为一个整体来实现

// Merge: insert elements from source in order
Node::Merge(Node* source)
{
}

1,2,3,4 描述执行实际排序所需执行的操作 按顺序执行这些步骤通过使用列表操作 Merge 和 Split 来实现排序功能。

这只是Merge 和Split 的一种方式，如何实现它们将取决于您的风格、要求、C++ 知识以及各种其他因素。 （我相信您会在答案中看到其他一些解决方案）。您可能还需要一个 Node::Append(Node* val) 或类似的基本运算符。看起来您不需要 Node::Remove(Node* val) ，但实现它也可能不会有什么坏处。