std::shuffle() 算法

自 C++11 起

// (1)
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

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

参数

first last	要打乱的元素范围。
g	一个 UniformRandomBitGenerator，其结果类型可转换为 std::iterator_traits<RandomIt>::difference_type。

类型要求

RandomIt	LegacyRandomAccessIterator ValueSwappable
std::remove_reference_t<URBG>	UniformRandomBitGenerator

返回值

(无)

复杂度

与 std::distance(first, last) 成线性关系；

异常

(无)

可能的实现

shuffle (1)

template<class RandomIt>
template<class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g)
{
    using diff_t = typename std::iterator_traits<RandomIt>::difference_type;
    using distr_t = std::uniform_int_distribution<diff_t>;
    using param_t = typename distr_t::param_type;

    distr_t D;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);
    }
}

备注

请注意，标准并未规定实现，因此即使您使用完全相同或 URBG（统一随机数生成器），不同的标准库实现也可能得到不同的结果。

Main.cpp

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

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

    std::random_device rd;
    std::mt19937 g(rd());

    std::shuffle(v.begin(), v.end(), g);

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

可能的输出

5 2 1 4 6 3 7 10 9 8