合并排序数组 - 有效的解决方案

Question

这里的目标是将多个已经排序的数组合并到一个结果数组中。

我写了以下解决方案，想知道是否有办法改进该解决方案

/*
    Goal is to merge all sorted arrays
*/
void mergeAll(const vector< vector<int> >& listOfIntegers,  vector<int>& result)
{

    int totalNumbers = listOfIntegers.size();
    vector<int> curpos;
    int currow = 0 , minElement , foundMinAt = 0;
    curpos.reserve(totalNumbers);

    // Set the current position that was travered to 0 in all the array elements
    for ( int i = 0; i < totalNumbers; ++i)
    {
        curpos.push_back(0);
    }

    for ( ; ; )
    {
        /*  Find the first minimum 
            Which is basically the first element in the array that hasn't been fully traversed
        */

        for ( currow = 0 ; currow < totalNumbers ; ++currow)
        {
            if ( curpos[currow] < listOfIntegers[currow].size() )
            {
                minElement = listOfIntegers[currow][curpos[currow] ];
                foundMinAt = currow;
                break;
            }
        }
        /* If all the elements were traversed in all the arrays, then no further work needs to be done */
        if ( !(currow < totalNumbers ) )
            break;
        /* 
            Traverse each of the array and find out the first available minimum value
        */
        for ( ;currow < totalNumbers; ++currow)
        {
            if ( listOfIntegers[currow][curpos[currow] ] < minElement )
            {
                minElement = listOfIntegers[currow][curpos[currow] ];
                foundMinAt = currow;
            }
        }
        /* 
            Store the minimum into the resultant array 
            and increment the element traversed
        */
        result.push_back(minElement);
        ++curpos[foundMinAt];
    }
}

相应的主要内容如下。

int main()
{
    vector< vector<int> > myInt;
    vector<int> result;

    myInt.push_back(vector<int>() );
    myInt.push_back(vector<int>() );
    myInt.push_back(vector<int>() );

    myInt[0].push_back(10);
    myInt[0].push_back(12);
    myInt[0].push_back(15);


    myInt[1].push_back(20);
    myInt[1].push_back(21);
    myInt[1].push_back(22);

    myInt[2].push_back(14);
    myInt[2].push_back(17);
    myInt[2].push_back(30);

    mergeAll(myInt,result);

    for ( int i = 0; i < result.size() ; ++i)
    {
        cout << result[i] << endl;
    }
}

Answer 1

您可以将它们全部放入一个多重集中。这将为您处理排序。

Answer 2

如果您将很多向量合并在一起，那么您可以通过使用一种树来确定哪个向量包含最小元素来提高性能。这对于您的应用程序来说可能不是必需的，但如果需要，请发表评论，我会尽力解决。

Answer 3

您所需要的只是两个指针（或只是 int 索引计数器），检查数组 A 和 B 之间的最小值，将值复制到结果列表，并递增最小值所在数组的指针。如果一个源数组上的元素用完，请将第二个源数组的剩余部分复制到结果中，然后就完成了。

编辑：
您可以轻松地将其扩展为 N 个数组。

编辑：
不要简单地将其扩展为 N 个数组:-)。一次做两个。愚蠢的我。

Answer 4

考虑上面评论中链接的这个答案中的优先级队列实现：在 C++ 中合并 8 个排序列表，我应该使用哪种算法

这是 O(n lg m) 时间（其中 n = 项目总数，m = 列表数量）。

Answer 5

如果您想利用多线程，那么一个相当好的解决方案是一次合并 2 个列表。

即假设您有 9 个列表。

将列表 0 与 1 合并。
将列表 2 与 3 合并。
将列表 4 与 5 合并。
将列表 6 与列表 7 合并。

这些可以同时执行。

然后：

将列表 0&1 与 2&3 合并
将列表 4&5 与 6&7 合并 同样，

这些可以同时执行。

然后将列表 0,1,2&3 与列表 4,5,6&7 合并，

最后将列表 0,1,2,3,4,5,6&7 与列表 8 合并

。工作完成。

我不确定其复杂性，但这似乎是显而易见的解决方案，并且在某种程度上确实具有多线程的好处。

Answer 6

我在互联网上看到了一些合并两个排序数组的解决方案，但大多数都非常麻烦。我改变了一些逻辑以提供我能想到的最短版本：

void merge(const int list1[], int size1, const int list2[], int size2, int list3[]) {

    // Declaration & Initialization
    int index1 = 0, index2 = 0, index3 = 0;

    // Loop untill both arrays have reached their upper bound.
    while (index1 < size1 || index2 < size2) {

        // Make sure the first array hasn't reached 
        // its upper bound already and make sure we 
        // don't compare outside bounds of the second 
        // array.
        if ((list1[index1] <= list2[index2] && index1 < size1) || index2 >= size2) {
            list3[index3] = list1[index1];
            index1++;
        }
        else {
            list3[index3] = list2[index2];
            index2++;
        }
        index3++;
    }
}

Answer 7

也许我误解了这个问题......而且我觉得我误解了你的解决方案。

也就是说，也许这个答案完全没有根据并且没有帮助。

但是，特别是考虑到您已经使用的 vector 和 push_back 的数量，为什么不只使用 std::sort ？

#include <algorithm>
void mergeAll(const vector<vector<int>> &origList, vector<int> &resultList)
{
    for(int i = 0; i < origList.size(); ++i)
    {
        resultList.insert(resultList.end(), origList[i].begin(), origList[i].end());
    }
    std::sort(resultList.begin(), resultList.end());
}

如果这与您正在寻找的完全不同，我深表歉意。但这就是我理解问题和解决方案的方式。

std::sort 运行时间为 O(N log (N)) http://www.cppreference.com/wiki/stl/algorithm/sort

Answer 8

您可以推广合并排序算法并使用多个指针。最初，它们都指向每个数组的开头。您在优先级队列中维护这些指针（按它们指向的值）排序。在每个步骤中，您都会在 O(log n) 中删除堆中的最小元素（n 是数组的数量）。然后输出提取的指针所指向的元素。现在，您将该指针增加到一个位置，如果没有到达数组末尾，则以 O(log n) 重新插入优先级队列。以此类推，直到堆不为空。如果总共有 m 个元素，则复杂度为 O(m log n)。元素以这种方式按排序顺序输出。