c++ - 交替排序数组的最简单方法是什么(例如 :T, T,F,F,F,T,F,T,F,F,F 到 T,F,T,F,T,F,T,F,T,T ,T)?

Question

比如我有一个 vector

vector<pair<bool,int> > v={{true,1},{true,2},{false,3},{false,4},{false,5},{true,6},{false,7},{true,8},{false,9},{false,10},{false,11}};

我想对它进行排序，以便相邻元素的 bool 值尽可能不同(int 的值不需要排序)，输出应该是这样的:

0,...
1,...
0,...
1,...
.
.
.
0,...
0,...
0,...

我试过这样的:

sort(v.begin(),v.end());
for(int i=1;i<v.size()/2;i+=2){
    iter_swap(v.begin()+i,v.end()-i);
}

但这不是我想要的输出:

0,3
1,8
0,5
1,2
0,9
0,10
0,11
1,1
0,7
1,6
0,4

有什么算法可以做到这一点吗？

Answer 1

对数组进行分区，像这样:

std::vector<std::pair<bool,int> > v={{true,1},{true,2},{false,3},{false,4},{false,5},{true,6},{false,7},{true,8},{false,9},{false,10},{false,11}};

auto p = std::partition(v.begin(), v.end(), [](const auto& p) { return !p.first; });
auto it1 = v.begin();
auto it2 = p;

while(it1 != p || it2 != v.end()) {
    if(it1 != p) {
        std::cout << it1->first << ',' << it1->second << std::endl;
        ++it1;
    }
    if(it2 != v.end()) {
        std::cout << it2->first << ',' << it2->second << std::endl;
        ++it2;
    }
}