双向链表的归并排序C++实现（含注释，非递归）_双向链表排序归并 c++

双向链表的归并排序顾名思义是将归并排序运用到双向链表中，其与单向链表不同在需要进行两次连接，所以读者应当注意。同时也需要考虑所依靠的段前后的分段节点是否不会改变，导致算法失效。注意本实现方法中需要段前后段后的辅助接点。具体的实现代码如下，具体的实现都写有注释。同时终止条件即：下段的元素个数是否达到排序的要求也需要考虑清楚如何实现。

void __merge(Node *l, Node *mid, Node *r) {
    Node * currprev = l->prev(); //为了和前段链表连接
    Node * endnode = r->next(); //为了和后段链表连接
    auto i = l, j = mid;
    while (i != mid || j != endnode) { //当两段均到末端后退出循环
        if (i == mid) {
            currprev->next() = j; // 正向连接下一个应该连接的节点
            j = j->next();
        } //保证 i 不越界
        else if (j == endnode) {
            currprev->next() = i; // 正向连接下一个应该连接的节点
            i = i->next();
        } //保证 j 不越界
        else if (i->data() <= j->data()) {
            currprev->next() = i; // 正向连接下一个应该连接的节点
            i = i->next();
        } else {
            currprev->next() = j; // 正向连接下一个应该连接的节点
            j = j->next();
        }
        currprev->next()->prev() = currprev; // 反向连接下一个应该连接的节点
        currprev = currprev->next(); //后移一位
    }
    currprev->next() = endnode; //正向连接后段链表
    endnode->prev() = currprev; //反向连接后段链表
}

//查找item后的第n个节点，终止节点为end
Node *nthNext(Node *item, int n, Node *end) {
	if(item==nullptr) return end;
    for (int i = 0; i < n; ++i) {
        if(item == end)
            break;
        item = item->next();
    }
    return item;
}

void sort(Node *startNode, Node *endNode, int n) {
    Node * item,mid,end,nextitem;
    Node * startPrev = startNode->prev(); //用于获取开端节点
    Node * endNodeNext = endNode->next(); //用于获取末端节点
    for (int sz = 1; sz <= n; sz += sz) {
        item = startPrev->next();
        mid = nthNext(item, sz - 1, endNodeNext->prev()); //求当前段中位节点
        while (mid != endNodeNext->prev()) { //当mid之后仍然有元素时进行排序
            end = nthNext(mid, sz, endNodeNext->prev()); //求当前段末位节点
            nextitem = end != endNodeNext->prev() ? end->next() : nullptr; //得到下一段的起始节点
            if (mid->data() > mid->next()->data()) {
                __merge(item, mid->next(), end); //当前后段无序则进行归并
            }
            item = nextitem;
            mid = nthNext(item, sz - 1 , endNodeNext->prev());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56