对单链表进行排序的最佳就地排序算法是什么

Question

我一直在阅读就地排序算法来排序链表。根据维基百科

合并排序通常是对链表进行排序的最佳选择:在这种情况下，实现合并排序相对容易，只需要< code >θ(1)额外的空间，并且链表缓慢的随机访问性能使得其他一些算法(如quicksort)表现不佳，而其他一些算法(如heapsort)则完全不可能。

据我所知，合并排序算法不是一个就地排序算法，并且具有O（n）辅助的最坏情况空间复杂性。现在，考虑到这一点，我无法确定是否存在合适的算法来对具有O（1）辅助空间的单链表进行排序。

Answer 1

这在某种程度上让我想起了我对荷兰国旗问题问题的回答。

在考虑了一下这就是我想到的之后，让我们看看这是否有效。我想主要问题是合并排序在O（1）额外空间中的合并步骤。

我们对链表的表示：

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^head                      ^tail

您将完成以下合并步骤：

[ 1 ] => [ 3 ] => [ 2 ] => [ 4 ]
  ^p                ^q       ^tail

作为< code>p和< code>q我们想要合并的段的指针。

只需在＜code＞尾部＜/code＞指针之后添加节点即可。如果＜code＞*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）额外空间来移动元素。

Answer 2

正如 Fabio A. 在注释中指出的那样，以下合并和拆分实现所暗示的排序算法实际上需要堆栈帧形式的 O（log n） 额外空间来管理递归（或其显式等效项）。O（1）空间算法可以使用完全不同的自下而上方法。

这里有一个O（1）空间合并算法，它只需通过将每个列表顶部的较低项移动到新列表的末尾来构建一个新列表：

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） 空间分割算法，它只是将列表分解为 2 个大小相等的片段：

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

请注意，< code>half向前移动的次数只有< code>in的一半。在此函数返回时，最初作为< code>in传递的列表将被更改，因此它只包含第一个ceil(n/2)项，返回值是包含其余floor(n/2)项的列表。