c++ - 制作一个用指针排序的有效算法

Question

考虑一个简单的结构:

struct Node{
 int val;
 Node *next;
 Node *freeNode;
};

现在我必须仅使用 freeNode 对给定的链表进行排序，并且该方法必须高效。我不能制作另一个列表并在那里使用某种排序插入。也不能使用基因组或冒泡排序。列表中任何元素的指针 freeNode 可以指向列表中的任何元素。

现在我想到了两个想法:

1. 使用 freeNode 做一个双向链表。

   然后进行配对比较，即将第 i 个元素与第 (i+1) 个元素进行比较。当我发现需要交换两个元素时，我交换它们，然后再次从 List 的头部开始。

   这个算法会超过 O(n)(不确定只是猜测)。这将花费很多时间。

2. 另一种方法是我的 freeNode 指向比它小的 elem。

   例如如果我有 30->6->14->56>Tail，那么

   56->freeNode->14
   30->freeNode->14
   14->freeNode->6
   6->freeNode->NULL.
   

   但同样，这并没有多大帮助，因为当我插入 45 或 20 时，我将不得不重新安排我的 freeNode 指针。而且，这也不是一种非常有效的方法。

对此有什么建议吗？如何使用 freeNode 实现更好、更高效的排序方法。伪代码可以工作，实际上我更喜欢它而不是真实代码。

编辑:您不能使用数组、 vector 或其他任何东西。只是 freeNode 指针。以任何你想要的方式使用它。保持它为 NULL 或让它指向您选择的元素。

Answer 1

你可以做一个二叉树。使用 next 作为您的右子指针，使用 freeNode 作为您的左子指针。 使您应该对根进行排序的第一个节点。 然后，获取其余节点并将它们“插入”到新的二叉树中。

编辑:像这样:

你的类型定义:

typedef struct Node{
 int val;
 struct Node *next;
 struct Node *freeNode;
} NodeT;

一些定义使这段代码更容易阅读:

// Conversions to make this code easier to read.
#define pRight freeNode
#define pLeft  next

递归二叉树插入:

static void BinTreeInsert( NodeT *pRootNode, NodeT *pChildNode );

编辑 2:当明显这是家庭作业时，解决方案被删除。弄清楚伙计!

这个解决方案是 O(n log n) 最佳/平均情况，但 O(n2) 最坏情况......如果传入列表已经排序。

http://en.m.wikipedia.org/wiki/Tree_sort#section_1