也就是n!，这是个恐怖的数字，比如打印N个数字的全排列，它的是时间复杂度就是O(N!)，这个谁也没办法优化，因为打印这些排列情况就需要O(N!)这么多的时间，而洗牌就是保证从这些元素组成的全排列中等概率的选取一种排列。

把所有的排列情况列举出来，然后从中选择一个所需时间是O(N!)，这显然是不现实的，所以很多大神们进行了优化，出现了多种洗牌算法，下面我只列举一种比较好理解的 Knuth-Durstenfeld Shuffle 算法。

改洗牌算法可简单表述为：一个拥有n个元素的初始序列，将最后一个数和该序列的前 n 个数中的随机一个数进行交换（如果随机结果是和第n个数交换，相当于没换），然后倒数第二个数和该序列的前 n - 1 个数中的随机一个数进行交换，以此类推，直到将该序列第一个数操作完，就完成了洗牌，该算法保证了每个元素在每个位置的概率都是相等的，时间复杂度为O(N)。

举个例子就像下面这样：

初始序列是 A 、 B 、 C 、 D 、 E 、 F ，为了便于和刚才的算法思路对应描述，索引从1开始

第一轮从1-6个位置中随机一个和最后的 F 交换，假如随机到位置3，也就是和 C 交换，结果为：

A B F D E C

概率是P=1/6，也就是随机一个数字的概率

第二轮从1-5个位置中随机一个和倒数第二个元素 E 交换，假如随机到的是位置2，也就是和 B 交换，结果为：

A E F D B C

概率是P=(5/6)*(1/5)=1/6，为什么这么算呢？要想和 B 交换必须第一轮随机不到 B 才可以，所以要在前面乘以 5/6

第三轮从1-2个位置中随机一个和倒数第二个元素 D 交换，假如随机到的还是位置2，也就是和 E 交换，结果为：

A D F E B C

概率是P=(5/6)*(4/5)*(1/4)=1/6，有了第二轮这个就应该明白了吧

依次类推，直到操作完第五次随机交换，整个洗牌算法也就完成了，伪代码也就几行

for (int i = vec.size() - 1; i > 0; i--)
    std::swap(vec[i], vec[std::rand() % (i + 1)]);
std::random_shuffle
 
使用这个函数需要引用头文件 <algorithm>，共有以下几个重载函数：
 
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last ); //(deprecated in C++14)(removed in C++17)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );  //(until C++11)
                                            //(deprecated in C++14)(removed in C++17)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r ); //(since C++11)
                                            //(deprecated in C++14)(removed in C++17)
从文档来看 std::random_shuffle 这个函数的实现在C++14标准中已经不推荐使用，在C++17中已经被移除了，函数定义如下：
 
   *  @brief Randomly shuffle the elements of a sequence.
   *  @ingroup mutating_algorithms
   *  @param  __first   A forward iterator.
   *  @param  __last    A forward iterator.
   *  @return  Nothing.
   *  Reorder the elements in the range @p [__first,__last) using a random
   *  distribution, so that every possible ordering of the sequence is
   *  equally likely.
  template<typename _RandomAccessIterator>
    inline void
    random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      if (__first != __last)
      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
        // XXX rand() % N is not uniformly distributed
        _RandomAccessIterator __j = __first
                    + std::rand() % ((__i - __first) + 1);
        if (__i != __j)
          std::iter_swap(__i, __j);
   *  @brief Shuffle the elements of a sequence using a random number
   *         generator.
   *  @ingroup mutating_algorithms
   *  @param  __first   A forward iterator.
   *  @param  __last    A forward iterator.
   *  @param  __rand    The RNG functor or function.
   *  @return  Nothing.
   *  Reorders the elements in the range @p [__first,__last) using @p __rand to
   *  provide a random distribution. Calling @p __rand(N) for a positive
   *  integer @p N should return a randomly chosen integer from the
   *  range [0,N).
  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
    random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
#if __cplusplus >= 201103L
           _RandomNumberGenerator&& __rand)
#else
           _RandomNumberGenerator& __rand)
#endif
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      if (__first == __last)
        return;
      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
            _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
            if (__i != __j)
                std::iter_swap(__i, __j);
以上函数实现来源于文件 /usr/include/c++/5/bits/stl_algo.h，看源码时发现一个问题，原来标准库中的代码也是空格和Tab混用，复制过来的时候我还专门整理了一下。
 
第一个仅两个参数的函数中首先验证了迭代器的类型和范围的有效性，同时使用了 std::rand() 函数来随机选择了一个需要交换的元素，而拥有三个参数的函数逻辑几乎一样，只是使用了自定义传入的随机函数来选择需要交换的元素，所以洗牌算法的核心逻辑就是这个随机函数。
 
rand 和 srand
 
这两个是C标准函数，在C++中被放在头文件 <cstdlib> 之中，搜索到的函数声明如下：
 
__BEGIN_NAMESPACE_STD
/* Return a random integer between 0 and RAND_MAX inclusive.  */
extern int rand (void) __THROW;
/* Seed the random number generator with the given number.  */
extern void srand (unsigned int __seed) __THROW;
__END_NAMESPACE_STD
其中 std::rand() 是用于返回一个介于[0, RAND_MAX] 范围的伪随机整型值，RAND_MAX 的值最小为 32767，也就是有符号short的最大值，我查到的版本库中的值是2147483647，即有符号int的最大值。
 
std::srand() 的作用是为 st::rand() 这个伪随机数生成器设置种子，如果在调用 std::srand() 之前使用了 std::rand()，种子默认为1，相当于调用了 std::srand(1)，rand通常不是线程安全的函数，依赖于具体的实现。
 
另外你可能还见过 random 和 srandom 等函数，他们通常是另一个标准（BSD）的随机函数，比如下面这段描述：
 
/* These are the functions that actually do things.  The `random', `srandom',
   `initstate' and `setstate' functions are those from BSD Unices.
   The `rand' and `srand' functions are required by the ANSI standard.
   We provide both interfaces to the same random number generator.  */
/* Return a random long integer between 0 and RAND_MAX inclusive.  */
extern long int random (void) __THROW;
/* Seed the random number generator with the given number.  */
extern void srandom (unsigned int __seed) __THROW;
如果是在 POSIX 平台你可能还会遇到 rand_r(int *seed) 函数。
 
需要注意的是， std::rand() 生成的是一个伪随机序列，如果随机种子相同，则得到的序列也是相同的，这也是 std::rand 不建议使用的原因，建议是使用C++11随机数生成工具来替换它。
 
伪随机序列也并不是“一无是处”，两个进程可以通过设置相同的随机数种子来产生相同的序列，比如可以用于服务器和客户端做帧同步时产生随机数，这样的随机数产生是同步可控的。
 
下面举个 std::rand() 使用的例子
 
#




    
include <iostream>
#include <cstdlib>
int main()
    std::srand(1);
    std::cout << std::rand() << std::endl;
    std::srand(1);
    std::cout << std::rand() << std::endl;
    std::srand(1);
    std::cout << std::rand() << std::endl;
    return 0;
运行结果如下：
 
albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
1804289383
1804289383
1804289383
我们可以看到因为随机种子相同，生成的随机数都是同一个，为了使的生成的序列更随机，通常使用当前时间戳 std::time(nullptr) 作为随机种子，然后再生成随机序列：
 
#include <iostream>
#include <cstdlib>
#include <ctime>
int main()
    std::srand(std::time(nullptr));
    std::cout << std::rand() << std::endl;
    std::srand(std::time(nullptr));
    std::cout << std::rand() << std::endl;
    std::srand(std::time(nullptr));
    std::cout << std::rand() << std::endl;
    return 0;
运行结果如下：
 
albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
1777572541
1777572541
1777572541
怎么还是相同的呢？那是因为 std::time(nullptr) 函数返回的时间戳单位是秒，在一秒中内的时间种子是相同的，所以返回的序列也是相同的，通常的使用方法是在程序启动时设置一次时间种子就可以了，并不需要每次都进行设置，而 random_shuffle 中使用了 std::rand() 函数，如果不手动设置时间种子，每次同一时间洗同一副牌，得到的结果也是相同的，所以这也是random_shuffle被后续版本移除的一个原因。
 
随机数生成器和分布器
 
random是C++11提供的一个头文件，其中包含多个随机数生成工具，可以使用生成器和分布器的组合产生随机数，其中包含随机数生成器和分布器的多个类实现，分为以下两种：
 
Uniform random bit generators (URBGs)：均匀随机位生成器，也就是生成均匀分布随机数的对象，可以生成伪随机序列，也可生成真正的随机数序列
 Random number distributions：随机数分布器，用于将URBGs产生的随机数转换为某种特定数学概率分布的序列，如均匀分布、正态分布、泊松分布等
 
常见的生成器：
 
linear_congruential_engine: 线性同余生成算法，是最常用也是速度最快的，随机效果一般
mersenne_twister_engine: 梅森旋转算法，随机效果最好
subtract_with_carry_engine: 滞后Fibonacci算法
 
常见的适配器，我理解的它的作用是生成器的二次加工厂，对生成器结果进行特定操作
 
discard_block_engine: 丢弃一些数
independent_bits_engine: 将序列打包成指定位数的块
shuffle_order_engine: 调整序列顺序
 
预定义的随机数生成器，利用通用生成器和适配器组合出的流行特定生成器：
 
minstd_rand
minstd_rand0
mt19937: mt是因为这个伪随机数产生器基于Mersenne Twister算法，19937来源于产生随的机数的周期长可达到2^19937-1。
mt19937_64
ranlux24_base
ranlux48_base
ranlux24
ranlux48
knuth_b
default_random_engine: 编译器可以自行实现
 
以上随机数引擎需要一个整型参数作为种子，对于给定的随机数种子，伪随机数生成器总会生成相同的序列，这在测试的时候是相当有用的。而在实际使用时，需要设置随机树作为种子来产出不同的随机数，推荐使用 std::random_device 的值作为随机数种子。
 
std::random_device 是一个使用硬件熵源的非确定性随机数发生器，不可预测。
 
常见的分布器：
 
uniform_int_distribution: 均匀离散分布
uniform_real_distribution: 均匀实数分布
bernoulli_distribution: 伯努利分布
binomial_distribution: 二项式分布
geometric_distribution: 几何分布
negative_binomial_distribution: 负二项式分布
poisson_distribution: 泊松分布
exponential_distribution: 指数分布
gamma_distribution: 伽玛分布
weibull_distribution: 威布尔分布
extreme_value_distribution: 极值分配
normal_distribution: 正态分布
lognormal_distribution: 对数正态分布
chi_squared_distribution: 卡方分布
cauchy_distribution: 柯西分布
fisher_f_distribution: Fisher F分布
student_t_distribution: 学生T分布
discrete_distribution: 离散分布
piecewise_constant_distribution: 分段常数分布
piecewise_linear_distribution: 分段线性分布
 
下面举个生成器和分布器组合生成随机常用例子，以下为模拟掷骰子生成点数的实现：
 
#include <iostream>
#include <random>
int main()
    std::mt19937 gen(std::random_device{}());
    std::uniform_int_distribution<> dist(1, 6);
    for (int i = 0; i < 10; ++i)
        std::cout << dist(gen) << std::endl;
    return 0;
编译运行结果如下：
 
albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
std::shuffle
 
终于又转回来了，去随机数那一块儿溜了半天，终于回到了洗牌函数，这个函数是C++11版本才加入的，函数定义如下：
 
   *  @brief Shuffle the elements of a sequence using a uniform random
   *         number generator.
   *  @ingroup mutating_algorithms
   *  @param  __first   A forward iterator.
   *  @param  __last    A forward iterator.
   *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
   *  @return  Nothing.
   *  Reorders the elements in the range @p [__first,__last) using @p __g to
   *  provide random numbers.
  template<typename _RandomAccessIterator,
       typename _UniformRandomNumberGenerator>
    shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _UniformRandomNumberGenerator&& __g)
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      if (__first == __last)
    return;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    _DistanceType;
      typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
      typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
      typedef typename __distr_type::param_type __p_type;
      __distr_type __d;
      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
    std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
这种实现和之前 std::random_shuffle 函数实现很类似，只是随机数部分有些不同，它的第3个参数需要的是一个均匀随机数生成器URBGs，一个常见的使用方法如下：
 
#include <iostream>
#include <algorithm>
#include <iterator>
#include <random>
#include <vector>
int main()
    std::vector<int> vec{1, 2, 3, 4, 5, 6};
    std::mt19937 gen(std::random_device{}());
    std::shuffle(vec.begin(), vec.end(), gen);
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    return 0;
编译后运行结果如下：
 
albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
3 5 1 2 6 4
randint
 
结尾了顺便说一下偶然看到的一个实验性函数 std::experimental::randint，用于生成指定范围内的一个随机数，目前还没有进入标准，不过看起来使用很方便了，后续有可能被纳入标准吧，贴一下 cppreference 上的例子 std::experimental::randint 如下：
 
#include <iostream>
#include <experimental/random>
int main()
    int random_number = std::experimental::randint(100, 999);
    std::cout << "random 3-digit number: " << random_number << '\n';
std::random_shuffle 可以只传递一个待洗牌的区间，函数内会使用默认的 std::rand 函数来完成随机元素的选择，依赖全局状态
std::random_shuffle 也可以传入自定义的随机函数，不过这个函数在C++14表中已经不建议时使用了，在C++17标准中已经被移除
std::shuffle 是C++11标准添加的，也是推荐使用的洗牌函数，它的第三个参数需要传递一个均匀随机数生成器对象
C++11中的<random>头文件中提供了很多生成随机数的工具，需要搭配生成器和分布器来使用
mt19937 名字看起来有点怪，但它是常用的生成器，mt表示它基于Mersenne Twister算法，19937源于产生随的机数的周期长可达到2^19937-1
 
  ==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==  
 
当被误解时，解释或者争论都是没有用的，有些事情就解释不清楚，或者根本无法解释，甚至没有人会听你解释，想一想，真的什么也做不了，就像一句名言说的，你永远叫不醒一个装睡的人，那个故意误解你的人又怎会听你解释~
 
                                    std::shuffle 重排序给定范围 [first, last) 中的元素，使得这些元素的每个排列拥有相等的出现概率。
函数原型
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
first, last	-	要随机打乱的元素范围
g	-	均匀随机位生成器 (UniformRandomBitGenerator) ，其结果类型可隐式
                                    函数生成的随机数并不是真正的随机数，而是一个伪随机数，其生成的随机数序列可以被预测和重现。注意：qsrand用来设置一个种子，该种子为qrand生成随机数的起始值。上面的代码中，我们使用系统时间的毫秒数作为随机数种子。上面的代码中，我们使用当前时间作为随机数种子。类生成0到99之间的随机数分布，最后使用。在C++中生成随机数可以使用标准库中的。在C语言中生成随机数可以使用标准库中的。方法生成0到99之间的随机数。函数生成随机数之前，需要使用。生成0到99之间的随机数。生成0到99之间的随机数。
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
可能的实现：
template<class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG
                                    重排序给定范围 [first, last) 中的元素，使得这些元素的每个排列拥有相等的出现概率。
1) 随机数生成器是实现定义的，但经常使用函数 std::rand 。
2) 随机数生成器为函数对象 r 。
3) 随机数生成器为函数对象 g 。
                                    shuffle可随机打乱数组
使用场景，例如常见的快速排序，当数组元素很对且基本有序时，时间复杂度会退化成o(n2)。优化方式有很多种，这里结合c++11特性shuffle()函数， 来优化快排时间复杂度
    #include <iostream>
    #include <algorithm>
    #include <random>
    using namespace std;
    vector<int> sortArray(vec
                                    1、c++自带的shuffle()函数
在Python中我们会经常看到shuffle的随机排列函数，其可以将列表中的内容进行随机排列，但在C++中却需要自己去实现这样功能的函数（c++0x之前）。在c++0x之后这样的功能函数在标准库中已有对应的提供——std::shuffle。下面就对该函数做具体的介绍：
template <class RandomAccessIterator, class URNG>
void shuffle (RandomAccessIterator first, 
                                    参考 http://www.cplusplus.com/reference/algorithm/random_shuffle/
template &lt;class RandomAccessIterator, class RandomNumberGenerator&gt;
  void random_shuffle (RandomAccessIterator first, RandomAcc...
                                    **要求：**在经过洗牌函数后，如果能够保证每一个数据出现在所有位置的概率是相等的，那么这种算法是符合要求的。在这个前提下，尽量降低时间复杂度和空间复杂度就能得到好的算法。
法一：每次随机抽出两张牌交换，重复交换一定次数次后结束
简单的计算，交换m次后，具体某张牌始终没有被抽到的概率为((n-2)/n)^m，如果我们要求这个概率小于1/1000,那么 m>-3*ln(10)/ln(1-2/n),对于52张牌，这个数大约是176次，需要注意的是，这是满足“具体某张牌”始终没有被抽到的概率，如果需要满足“