排序单链表的最佳排序算法是什么？
我一直在阅读就地排序算法来排序链接列表。根据维基百科
合并排序通常是排序链接列表的最佳选择:在这种情况下，实现合并排序相对容易，因为合并排序只需要额外的
Θ(1)空间，而链接列表的缓慢随机访问性能使得其他一些算法(例如快速排序)性能较差，而其他算法(如堆排序)则完全不可能实现。
据我所知，合并排序算法不是一种就地排序算法，而且具有O(n)辅助的最坏的情况空间复杂度。现在，考虑到这一点，我无法确定是否有合适的算法来排序带有O(1)辅助空间的单链表。
回答 2
Stack Overflow用户
发布于 2012-06-30 10:10:49
正如Fabio .在注释中所指出的，以下合并和拆分实现所隐含的排序算法实际上需要O(log )堆栈帧形式的额外空间来管理递归(或它们的显式等价)。使用完全不同的自下而上方法可以使用O(1)-space算法。
下面是一个O(1)-space合并算法，它通过将较低的项从每个列表的顶部移动到新列表的末尾来构建一个新的列表：
struct node {
WHATEVER_TYPE val;
struct node* next;
};
node* merge(node* a, node* b) {
node* out;
node** p = &out; // Address of the next pointer that needs to be changed
while (a && b) {
if (a->val < b->val) {
*p = a;
a = a->next;
} else {
*p = b;
b = b->next;
}
// Next loop iter should write to final "next" pointer
p = &(*p)->next;
}
// At least one of the input lists has run out.
if (a) {
*p = a;
} else {
*p = b; // Works even if b is NULL
}
return out;
}通过将第一项添加到输出列表中，可以避免指针到指针的p，但我认为我这样做的方式更清楚。
下面是一个O(1)-space拆分算法，它简单地将一个列表分解成两个大小相等的部分：
node* split(node* in) {
if (!in) return NULL; // Have to special-case a zero-length list
node* half = in; // Invariant: half != NULL
while (in) {
in = in->next;
if (!in) break;
half = half->next;
in = in->next;
}
node* rest = half->next;
half->next = NULL;
return rest;
}请注意，half向前移动的次数仅为in的一半。在此函数返回后，最初作为in传递的列表将被更改，因此它只包含第一个单元格(n/2)项，返回值是包含其余楼层(n/2)项的列表。
Stack Overflow用户
发布于 2012-06-30 09:41:38
这让我想起了我对Dutch National Flag Problem question的回答。
经过一些思考，这就是我想出来的，让我们看看这是否可行。我认为主要的问题是合并在O(1)额外空间中的合并步骤。
我们对链接清单的陈述：
[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
^head ^tail最后，您将完成以下合并步骤：
[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
^p ^q ^tailp和q是我们要合并的段的指针。
只需在tail指针之后添加节点即可。如果*p <= *q，则在尾部添加p。
[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
^p ^pp ^q/qq ^tail ^tt否则，添加q。
[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ] => [ 1 ] => [ 2 ]
^p ^pp ^q ^qq/tail ^tt(跟踪列表q的结尾变得很棘手)
现在，如果你移动它们，你将很快失去对你所在位置的了解。您可以通过一种巧妙的方法来移动指针或将长度添加到等式中来克服这一问题。我绝对喜欢后者。办法是：
[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
^p(2) ^q(2) ^tail
[ 3 ] => [ 2 ] => [ 4 ] => [ 1 ]
^p(1) ^q(2) ^tail
[ 3 ] => [ 4 ] => [ 1 ] => [ 2 ]
^p(1) ^q(1) ^tail
[ 4 ] => [ 1 ] => [ 2 ] => [ 3 ]
^p(0)/q(1) ^tail
[ 1 ] => [ 2 ] => [ 3 ] => [ 4 ]
^q(0) ^tail现在，您可以使用O(1)额外空间来移动元素。
https://stackoverflow.com/questions/11272492
复制相似问题
腾讯云开发者
