链表如何实现 O(n log n) 排序时间？

Question

首先，我很好奇为什么 std::list 和 std::forward_list 包含排序函数作为成员函数，这与所有其他标准库容器不同。但对我来说更有趣的是，CPPReference and CPlusPlus 都声称这种排序是在 O(n log n) 时间内完成的。

我什至无法想象如何在不随机访问元素的情况下对容器进行排序。所以我拼凑了一个测试，使用 forward_list 使其尽可能困难。

#include <chrono>
#include <cstdint>
#include <deque>
#include <forward_list>
#include <iostream>
#include <random>

using std::endl;
using namespace std::chrono;

typedef nanoseconds::rep length_of_time;
constexpr int TEST_SIZE = 25000;


class Stopwatch
{
    public:
        void start_timing();
        void end_timing();
        length_of_time get_elapsed_time() const;
    private:
        time_point<high_resolution_clock> start;
        time_point<high_resolution_clock> end;
        length_of_time elapsed_time = 0;
};


void Stopwatch::start_timing()
{
    start = high_resolution_clock::now();
}


void Stopwatch::end_timing()
{
    end = high_resolution_clock::now();
    auto elapsed = end - start;
    auto elapsed_nanoseconds = duration_cast<nanoseconds>(elapsed);
    elapsed_time = elapsed_nanoseconds.count();
}


length_of_time Stopwatch::get_elapsed_time() const
{
    return elapsed_time;
}


std::mt19937_64 make_random_generator()
{
    using namespace std::chrono;
    auto random_generator = std::mt19937_64();
    auto current_time = high_resolution_clock::now();
    auto nanos = duration_cast<nanoseconds>(
            current_time.time_since_epoch()).count();
    random_generator.seed(nanos);
    return random_generator;
}


int main()
{
    Stopwatch timer;
    std::deque<length_of_time> times;
    auto generator = make_random_generator();
    for (int i = 1; i <= TEST_SIZE; i++) {
        std::forward_list<uint64_t> container;
        for (int j = 1; j <= i; j++) {
            container.push_front(generator());
        }
        timer.start_timing();
        container.sort();
        timer.end_timing();
        times.push_back(timer.get_elapsed_time());
        container.clear();
    }

    for (const auto& time: times) {
        std::cout << time << endl;
    }
}

这个程序输出的数字给出了下图：

确实看起来像 O(n log n) 增长（尽管每三分之一处的尖峰很有趣).图书馆如何做到这一点？也许复制到支持排序的容器，排序，然后复制回来？

Answer 1

Mergesort 是链表的 O(nlogn)。我不知道 C++ 的默认排序函数是什么，但我怀疑它的合并排序。

Answer 2

可以使用 Mergesort.

在 O(n log n) 中对链表进行排序

有趣的是，由于链表已经具有适当的结构，因此使用 Mergesort 对链表进行排序只需要 O(1) 额外的 space.

这需要专门针对列表结构调整的专门算法，这也是 sort 是列表的成员函数而不是单独函数的原因。

至于它是如何工作的——你所需要的只是合并操作。合并操作需要两个列表。您查看两个列表的头部，然后删除最小的头部并将其附加到结果列表中。你一直这样做，直到所有头都被合并到大列表中 - 完成。

这是 C++ 中的示例合并操作：

struct Node {
    Node* next;
    int val;
};

Node* merge(Node* a, Node* b) {
    Node fake_head(nullptr, 0);

    Node* cur = &fake_head;
    while (a && b) {
        if (a->val < b->val) { cur->next = a; a = a->next; }
        else                 { cur->next = b; b = b->next; }
        cur = cur->next;
    }

    cur->next = a ? a : b;
    return fake_head.next;
}

Answer 3

使用指向列表的指针数组的自下而上合并排序的示例代码，其中 array[i] 指向大小为 2^i 的列表（除了最后一个指针指向无限大小的列表）。 HP/Microsoft标准模板库就是这样实现的std::list::sort。

#define NUMLISTS 32                     /* number of lists */

typedef struct NODE_{
struct NODE_ * next;
int data;                               /* could be any comparable type */
}NODE;

NODE * MergeLists(NODE *, NODE *);

NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS];                 /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
    if(pList == NULL)                   /* check for empty list */
        return NULL;
    for(i = 0; i < NUMLISTS; i++)       /* zero array */
        aList[i] = NULL;
    pNode = pList;                      /* merge nodes into aList[] */
    while(pNode != NULL){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
            pNode = MergeLists(aList[i], pNode);
            aList[i] = NULL;
        }
        if(i == NUMLISTS)
            i--;
        aList[i] = pNode;
        pNode = pNext;
    }
    pNode = NULL;                       /* merge array into one list */
    for(i = 0; i < NUMLISTS; i++)
        pNode = MergeLists(aList[i], pNode);
    return pNode;
}

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    while(1){
        if(pSrc1 == NULL){
            *ppDst = pSrc2;
            break;
        }
        if(pSrc2 == NULL){
            *ppDst = pSrc1;
            break;
        }
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            continue;
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            continue;
        }
    }
    return pDst;
}

另一种对列表进行合并排序但速度较慢的方法类似于 4 磁带排序（所有顺序访问）。初始列表分为两个列表。每个列表被认为是一个运行的流，其中初始运行大小为 1。在这个例子中，计数器用于跟踪运行边界，所以它有点多比指针数组方法复杂且慢。来自两个输入列表的运行被合并，在两个输出列表之间交替。每次合并通过后，运行大小加倍，合并方向改变，输出列表变成输入列表，反之亦然。当所有运行都只出现在一个输出列表中时，排序就完成了。如果不需要稳定性，则运行边界可以定义为任何节点后跟乱序节点，这将利用原始列表的自然排序。

NODE * SortList(NODE * pList)
{
NODE *pSrc0;
NODE *pSrc1;
NODE *pDst0;
NODE *pDst1;
NODE **ppDst0;
NODE **ppDst1;
int cnt;

    if(pList == NULL)                   /* check for null ptr */
        return NULL;
    if(pList->next == NULL)             /* if only one node return it */
        return pList;
    pDst0 = NULL;                       /* split list */
    pDst1 = NULL;
    ppDst0 = &pDst0;
    ppDst1 = &pDst1;
    while(1){
        *ppDst0 = pList;
        pList = *(ppDst0 = &pList->next);
        if(pList == NULL)
            break;
        *ppDst1 = pList;
        pList = *(ppDst1 = &pList->next);
        if(pList == NULL)
            break;
    }
    *ppDst0 = NULL;
    *ppDst1 = NULL;
    cnt = 1;                            /* init run size */
    while(1){
        pSrc0 = pDst0;                  /* swap merge direction */
        pSrc1 = pDst1;
        pDst0 = NULL;
        pDst1 = NULL;
        ppDst0 = &pDst0;
        ppDst1 = &pDst1;
        while(1){                       /* merge a set of runs */
            if(MergeRuns(&ppDst0, &pSrc0, &pSrc1, cnt))
                break;
            if(MergeRuns(&ppDst1, &pSrc0, &pSrc1, cnt))
                break;
        }
        cnt <<= 1;                      /* bump run size */
        if(pDst1 == NULL)               /* break if done */
            break;
    }
    return pDst0;
}       

int MergeRuns(NODE ***pppDst, NODE **ppSrc0, NODE **ppSrc1, int cnt)
{
NODE **ppDst = *pppDst;
NODE *pSrc0  = *ppSrc0;
NODE *pSrc1  = *ppSrc1;
int cnt0, cnt1;

    cnt0 = cnt;
    cnt1 = cnt;
    if(pSrc0 == NULL){                      /* if end data src0 */
        *ppDst = NULL;
        *pppDst = ppDst;
        return(1);
    }
    if(pSrc1 == NULL){                      /* if end data src1 */
        do{                                 /*   copy rest of src0 */
            *ppDst = pSrc0;
            pSrc0 = *(ppDst = &(pSrc0->next));
        }while(pSrc0);
        *ppDst = NULL;
        *pppDst = ppDst;
        return(1);
    }
    while(1){
        if(pSrc1->data < pSrc0->data){      /* if src1 < src0 */
            *ppDst = pSrc1;                 /*  move src1 */
            pSrc1 = *(ppDst = &(pSrc1->next));
            if(pSrc1 != NULL && --cnt1)     /*  if not end run1, continue */
                continue;
            do{                             /*    copy run0 */
                *ppDst = pSrc0;
                pSrc0 = *(ppDst = &(pSrc0->next));
            }while(pSrc0 != NULL && --cnt0);
            break;
        } else {                            /* else src0 <= src1 */
            *ppDst = pSrc0;                 /*  move src0 */
            pSrc0 = *(ppDst = &(pSrc0->next));
            if(pSrc0 != NULL && --cnt0)     /*  if not end run0, continue */
                continue;
            do{                             /*    copy run1 */
                *ppDst = pSrc1;
                pSrc1 = *(ppDst = &(pSrc1->next));
            }while(pSrc1 != NULL && --cnt1);
            break;
        }
    }
    *ppSrc0 = pSrc0;                        /* update ptrs, return */
    *ppSrc1 = pSrc1;
    *ppDst  = NULL;
    *pppDst = ppDst;
    return(0);
}

Answer 4

我这里没有标准，但是CPPReference说排序的复杂度是Nlog(N)比较。这意味着即使是快速排序也将是符合标准的实现，因为它将是 Nlog(N) 比较（但不是 Nlog(N) 时间）。

Answer 5

您从一个长度未知的未排序列表开始。假设元素编号为 0、1、2、3...

在第一遍中，您创建了两个链表，每个链表都包含按排序顺序排列的数字对。列表 0 从元素 0 和 1 按排序顺序开始。列表 1 从元素 2 和 3 按排序顺序开始。元素 4 和 5 按排序顺序添加到列表 0，元素 6 和 7 添加到列表 1，依此类推。显然必须注意不要超出原始列表的末尾。

在第二遍中，您将这两个列表合并以创建两个链表，每个链表由 4 个数字组成，按排序顺序排列。每次组合列表 0 中的两个元素和列表 1 中的两个元素时。下一个最小的元素显然每次都是列表前面的元素。

在第二遍中，您将这些列表合并为两个链表，每个链表由 8 个排序的数字组成，然后是 16 个，然后是 32 个，依此类推，直到结果列表包含 n 个或更多数字。如果 n = 2^k 则有 k = log2 (n) 遍，所以这需要 O (n log n)。

链表如何实现 O(n log n) 排序时间？

How could a linked list achieve O(n log n) sorting time?

c++

sorting

linked-list

time-complexity