std::random_shuffle() 算法

自 C++11 起

// (1)
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );

// (2)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );

直到 C++11

// (1)
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );

重新排列给定范围 [first; last) 中的元素，使这些元素的每种可能排列出现的概率相等。

• (1) 随机性来源是实现定义的

  ，但通常使用函数std::rand。

• (2) 随机性来源是函数对象r。

参数

first last	要打乱的元素范围。
r	函数对象，当以 r(n) 调用时，返回一个可转换为 std::iterator_traits<RandomIt>::difference_type 类型的随机选择值，范围在 [0; n) 内。

类型要求

RandomIt

LegacyRandomAccessIterator ValueSwappable

返回值

(无)

复杂度

在 std::distance(first, last) 中是线性的。

异常

(无)

可能的实现

random_shuffle (1)

template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;

    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[std::rand() % (i + 1)]);
        // rand() % (i + 1) is not actually correct, because the generated number
        // is not uniformly distributed for most values of i. A correct implementation
        // will need to essentially reimplement C++11 std::uniform_int_distribution,
        // which is beyond the scope of this example.
    }
}

random_shuffle (2)

template<class RandomIt, class RandomFunc>
void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;

    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[r(i + 1)]);
    }
}

备注

请注意，标准并未规定实现，因此即使您使用完全相同的 RandomFunc，在不同的标准库实现中，您可能会得到不同的结果。

C++17 中移除std::random_shuffle的原因是，仅迭代器版本通常依赖于std::rand，后者现在也正在讨论弃用。（std::rand应替换为<random>头文件中的类，因为std::rand被认为是有害的。）

此外，仅迭代器的std::random_shuffle版本通常依赖于全局状态。std::shuffle洗牌算法是首选替代方案，因为它使用 URBG 作为其第三个参数。

Main.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    std::random_shuffle(v.begin(), v.end());

    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

可能的输出

8 6 10 4 2 3 7 1 9 5