单向链表的归并排序

Question

我的 C++ 归并排序代码有问题。我不知道为什么，但是当我从 Merge_Sort 调用这些函数时，它们无法正常工作。他们分开工作。

当我输入这样一个列表时：H->1->2->8->4->7->6->33->NULL

作为排序列表，我得到如下内容：H->33->4->6->NULL。

void Split(node *&H, node *&h1, node *&h2)
{
    if (H != NULL)
    {
        node *P = H;
        bool check = 0;
        while (H != NULL)
        {
            P = H;
            H = H->next;
            if (check) {
                AddLastNode(h2,P);
            }
            else
            {
                AddLastNode(h1, P);
            }
            check=!check;
        }
    }
}

void Merge(node *&H, node *&h1, node *&h2)
{
    node *p1=h1, *p2=h2;
    node *temp = H;
    while (h1!=NULL && h2!=NULL)
    {       
        p1 = h1;
        p2 = h2;
        if (p1->val < p2->val)
        {
            h1 = h1->next;
            temp = p1;  
        }
        else
        {
            h2 = h2->next;
            temp = p2;
        }
        temp->next = H;
        H = temp;
    }
    if (h1 == NULL)
    {
        temp = h2;
        temp->next = H;
        H = temp;
    }
    else if (h2 == NULL)
    {
        temp = h1;
        temp->next = H;
        H = temp;
    }
}

void Merge_Sort(node *&H)
{
    node *h1, *h2;
    if (H && H->next)
    {
        h1 = h2 = NULL;
        Split(H, h1, h2);
        Merge_Sort(h1);
        Merge_Sort(h2);
        Merge(H, h1, h2);
    }
}

Answer 1

递归调用有问题Merge_Sort。你用指针引用来调用它，所以最后它们变成了 1 个长度，其他数据丢失了。我认为这是糟糕的算法。您可以使用 STL 容器和算法更轻松地做到这一点。使用 std::list 作为容器，将其分开。然后在分离的容器上使用列表方法 sort 并在新容器或 h1、h2 之一上使用 merge。这是我的合并算法代码：

#include <iostream>
#include <string>
#include <algorithm>
#include <list>

void TraceList( const std::list<int32_t>& lst, const std::string& title = "" )
{
    if ( !title.empty() )
    {
        std::cout << title << std::endl;
    }
    std::copy(lst.begin(), lst.end(), std::ostream_iterator<int16_t>(std::cout, ","));
    std::cout << std::endl;
}

int main()
{
    //Input test data. You can use here your input code
    const uint32_t SIZE_START = 10;
    int16_t ArrInputData[SIZE_START] = {4, 45, 12, 78, 11, 17, 2, 58, 79, 10 };
    std::list<int32_t> StartList;
    std::copy(ArrInputData, ArrInputData + SIZE_START, std::back_inserter(StartList));

    //Separate input data on parts
    std::list<int> h1;
    std::list<int> h2;
    bool CounterFlag = true;
    std::for_each(StartList.begin(), StartList.end(), [&CounterFlag, &h1, &h2]( int16_t val )
                  {
                      CounterFlag ? h1.push_back(val) : h2.push_back(val);
                      CounterFlag = !CounterFlag;
                  });

    //Sort separated parts
    h1.sort();
    h2.sort();
    TraceList(h1, "H1 list:");
    TraceList(h2, "H2 list:");

    //Merge separated
    std::list<int32_t> FinalMergedList = h1; //Copy one of separated to new list
    FinalMergedList.merge(h2);
    TraceList(FinalMergedList, "MergeFinal list:");

    return 0;
}

结果是：

H1 list:
2,4,11,12,79,
H2 list:
10,17,45,58,78,
MergeFinal list:
2,4,10,11,12,17,45,58,78,79,
Program ended with exit code: 0

如果您喜欢我的 std::list 解决方案，那么您也应该考虑其他容器。 std::list 在tail 和head 之间插入时很好，但不适合排序。可能您应该使用任何具有随机访问权限的容器，它们的排序速度更快，例如 std::vector.

单向链表的归并排序

Merge Sort on singly linked list

c++

mergesort

singly-linked-list