0

我正在寻找一种可以学习和理解合并排序的简单方法。我在网上查看过，发现合并排序对单链表非常有用，但我不明白该怎么做。这是我找到的网站： Wikipedia Merge sort and Specific linked lists

我不确定要给你什么代码。我基本上只是在我的头文件中有这个并且是新手，所以我很基础。提前谢谢你的帮助 ：）

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

1 回答 1

2

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

从概念上讲，合并排序的工作原理如下

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

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

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

类似的合并可以实现为

// 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)，但实施它也可能没有坏处。

于 2011-04-29T15:16:02.080 回答