什么是最好的排序算法来排序单链表

Question

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

合并排序通常是排序链表的最佳选择:在这种情况下,以一种只需要?(1)额外空间的方式实现合并排序相对容易,链表的慢随机访问性能使得其他算法(如quicksort)表现不佳,而其他算法(如heapsort)完全不可能.

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

Answer 1

正如 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) 项的列表。