7

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

合并排序通常是对链表进行排序的最佳选择：在这种情况下，实现合并排序相对容易，它只需要Θ(1)额外的空间，而链表的缓慢随机访问性能使得其他一些算法（例如快速排序）表现不佳，而其他算法（例如堆排序）则完全不可能。

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

4

2 回答 2

5

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

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

于 2012-06-30T10:10:49.663 回答
1

这不知何故让我想起了我对荷兰国旗问题问题的回答。

经过一番思考，这就是我的想法，让我们看看这是否可行。我想主要问题是合并排序在O(1)额外空间中的合并步骤。

我们对链表的表示：

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

您最终完成了此合并步骤：

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

存在p和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)额外空间来移动元素。

于 2012-06-30T09:41:38.613 回答