如何在 C++ 中围绕任意值实现我所谓的“环绕排序”？

Question

给定一个整数向量，我想实现我所谓的“环绕排序”。基本上，给定一个任意值，所有大于或等于该值的值首先按升序列出，然后是所有小于该任意值的值，再次按升序列出。对于 12 的值，环绕排序数组将如下所示：

[13, 15, 18, 29, 32, 1, 3, 4, 8, 9, 11]

实现这种排序的方法是什么？我可以假设一个向量作为起点，该向量已经按升序排序而没有环绕特征，因为如果这样的假设有用的话，很容易达到该状态。

Answer 1

您可以将std::partition和组合在一起std::sort。 std::partition将围绕分区点分割向量，然后您可以std::sort用来对两半进行排序。那看起来像

int main()
{
    std::vector vec = {1,3,4,8,9,11,13,15,18,29,32};
    // all elements >= 12 come first, return value is end iterator of that set
    auto front_end = std::partition(vec.begin(), vec.end(), [](auto elm){return elm >= 12;});
    // sort first half
    std::sort(vec.begin(), front_end);
    // sort second half
    std::sort(front_end, vec.end());
    for (auto e : vec)
        std::cout << e << " ";
}

哪个输出

13 15 18 29 32 1 3 4 8 9 11 

根据PaulMcKenzie的评论，您可以通过std::stable_partition在排序向量上使用来减少代码大小。那看起来像

int main()
{
    std::vector vec = {1,3,4,8,9,11,13,15,18,29,32};
    // sort the vector
    std::sort(vec.begin(), vec.end());
    // all elements >= 12 come first in the order they had in the sorted vector
    std::stable_partition(vec.begin(), vec.end(), [](auto elm){return elm >= 12;});
    for (auto e : vec)
        std::cout << e << " ";
}

应该注意的是，std::stable_partition它确实尝试进行分配以使其尽可能高效std::partition，如果它不能这样做，则它会退回到效率较低的 O(NlogN) 算法。