什么是最好的就地排序算法来对单链表进行排序 [英] What is the best in place sorting algorithm to sort a singly linked list

问题描述

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

I've been reading on in place sorting algorithm to sort linked lists. As per Wikipedia

合并排序通常是对链表进行排序的最佳选择:在这种情况下，以仅需Θ(1)额外空间以及较慢的随机访问性能的方式实现合并排序相对容易.链表会导致其他一些算法(例如quicksort)的性能较差，而另一些算法(例如堆排序)则完全不可能.

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

据我所知，合并排序算法不是就地排序算法，而是具有最差情况的辅助空间c1.现在，考虑到这一点，我无法确定是否存在合适的算法来对带有O(1)辅助空间的单链接列表进行排序.

To my knowledge, the merge sort algorithm is not an in place sorting algorithm, and has a worst case space complexity of O(n) auxiliary. Now, with this taken into consideration, I am unable to decide if there exists a suitable algorithm to sort a singly linked list with O(1) auxiliary space.

推荐答案

正如Fabio A.在评论中指出的那样，以下合并和拆分实现所隐含的排序算法实际上需要O(log n )以堆栈框架形式的额外空间来管理递归(或它们的显式等效项).使用完全不同的自底向上方法可以实现O(1)空间算法.

这是O(1)-空间合并算法，只需将下面的项从每个列表的顶部移到新列表的末尾，即可简单地建立一个新列表:

Here's an O(1)-space merge algorithm that simply builds up a new list by moving the lower item from the top of each list to the end of the new list:

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，但是我认为这样做的方法更加清晰.

It's possible to avoid the pointer-to-pointer p by special-casing the first item to be added to the output list, but I think the way I've done it is clearer.

这是一种O(1)-空间拆分算法，可以将列表简单地分成2个相等大小的片段:

Here is an O(1)-space split algorithm that simply breaks a list into 2 equal-sized pieces:

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)项的列表.

Notice that half is only moved forward half as many times as in is. Upon this function's return, the list originally passed as in will have been changed so that it contains just the first ceil(n/2) items, and the return value is the list containing the remaining floor(n/2) items.

这篇关于什么是最好的就地排序算法来对单链表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！