交替大小值的稳定排序向量

Question

给定一个由 int 和字符串组成的向量，类似于这样 vector<pair<int,string>>。我需要以不同的方式对它们进行排序。

我希望第一个元素最大。第二个元素最小，依此类推。此外，如果值相同，则值必须按照它们在原始列表中出现的顺序显示。

比如说我们有这样的东西：N=5，这里有 5 对：

10 bcd
2  abc
30 def
2  xyz
50 mn

那么输出数组应该是：[mn,abc,def,xyz,bcd]

解释：首先 50 是最大的，所以第一个元素是 "mn"，然后 2 是最小的，但是由于 "abc" 高于 "xyz"，所以首先取 "abc"。然后最大值是 30，所以 "def"，然后最小值是 2，"xyz"，最后剩下 "bcd"。

如何使用 C++11 STL 完成此操作？我知道否则没那么难

Answer 1

这是一个想法：

根据整数对元素向量进行稳定排序
为每个唯一值创建多个桶
- 每个桶都针对原始向量中的那些值进行了稳定排序
从最大值的桶和最小值的桶中交替打印出桶的元素
在移动到下一个存储桶之前打印一个存储桶的全部内容。

因此您的原始列表：

10 bcd
2 abc
30 def
2 xyz
50 mn

稳定排序后：

2 abc
2 xyz
10 bcd
30 def
50 mn

创建存储桶：

2: (2, abc), (2,xyz)
10: (10, bcd)
30: (30, def)
50: (50, mn)

打印桶 50 的第一个元素：

50, mn

打印桶 2 的第一个元素：

2, abc

打印存储桶 50 的下一个元素...不存在，移至下一个最小的存储桶 30。打印桶 30 的下一个元素：

30, def

打印桶 2 的下一个元素：

2, xyz

桶 30 中没有更多元素，因此转到桶 10：

10, bcd

桶 2 中没有更多元素，所以继续到桶 10。我们已经从另一边到达桶 10，所以到此为止。

我的实现使用 std::stable_sort 和 std::map，并没有完全遵循这个逻辑，但即使在所有元素都相同的情况下它也能工作：

Live Demo

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <map>
using namespace std;


void PrintPair(const std::pair<int, std::string>& thePair)
{
    std::cout << thePair.first << ", " << thePair.second << std::endl;
}

int main() {
    // create our vector
    std::vector<std::pair<int, std::string>> myVector{
        std::make_pair(10,"bcd"),
        std::make_pair(2, "abc"),
        std::make_pair(30, "def"),
        std::make_pair(2, "xyz"),
        std::make_pair(50, "mn")
    };
    
    
    // print vector before sorting
    std::cout << "vector before sorting:\n";
    for (auto&& nextPair : myVector)
    {
        std::cout << nextPair.first << ", " << nextPair.second << std::endl;
    }
    
    // sort it on the ints in the pairs
    std::stable_sort(std::begin(myVector),std::end(myVector), [](const std::pair<int,std::string>& lhs, const std::pair<int,std::string>& rhs){return lhs.first < rhs.first;});
    
    // print vector after sorting
    std::cout << "\nvector after sorting\n";
    for (auto&& nextPair : myVector)
    {
        std::cout << nextPair.first << ", " << nextPair.second << std::endl;
    }
    
    std::map<int, decltype(myVector)> myBuckets;
    for (auto&& nextElement : myVector)
    {
        if (myBuckets.find(nextElement.first) == myBuckets.end())
            myBuckets[nextElement.first] = decltype(myVector){nextElement};
        else
            myBuckets[nextElement.first].emplace_back(nextElement);
    }
    
    //needs at least a 2 element vector to work
    cout << "\nFinal output:\n";
    // create buckets for each value, internally each bucket is stable sorted
    // the buckets are sorted on map value
    // print out each element in a bucket before moving onto the next bucket
    auto bucketsBegin = myBuckets.begin();
    auto bucketsEnd = myBuckets.end();
    --bucketsEnd;
    auto nextEndElement = bucketsEnd->second.begin();
    auto nextBeginElement = bucketsBegin->second.begin();
    while(bucketsBegin != myBuckets.end() && bucketsBegin != bucketsEnd)
    {
        if (bucketsEnd != bucketsBegin)
        {
            PrintPair(*nextEndElement);
            ++nextEndElement;
            if (nextEndElement == bucketsEnd->second.end())
            {
                bucketsEnd--;
                nextEndElement = bucketsEnd->second.begin();
            }
        }
        PrintPair(*nextBeginElement);
        ++nextBeginElement;
        if (nextBeginElement == bucketsBegin->second.end())
        {
            bucketsBegin++;
            if (bucketsBegin != myBuckets.end())
                nextBeginElement = bucketsBegin->second.begin();
        }
    }
     //print remainder
     while(nextBeginElement != bucketsBegin->second.end())
     {
        PrintPair(*nextBeginElement);
        ++nextBeginElement;
     }
    

    
    return 0;
}

输出：

vector before sorting:
10, bcd
2, abc
30, def
2, xyz
50, mn

vector after sorting
2, abc
2, xyz
10, bcd
30, def
50, mn

Final output:
50, mn
2, abc
30, def
2, xyz
10, bcd

当向量中几乎所有元素都具有相同的值时：

vector before sorting:
1, bcd
1, abc
1, def
1, xyz
2, mn

vector after sorting
1, bcd
1, abc
1, def
1, xyz
2, mn

Final output:
2, mn
1, bcd
1, abc
1, def
1, xyz

交替大小值的稳定排序向量

Stable sort vector alternating large and small values

stl

c++11