c++ - 如何在 C++ 中围绕任意值实现我所说的 "wraparound sort"？

Question

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

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

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

Answer 1

您可以结合 std::partition 来完成此操作和 std::sort 。 std::partition 将围绕分区点分割 vector ，然后您可以使用 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 稍微减少代码大小在排序 vector 上。这看起来像

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) 算法。