洗牌算法

问题描述：给定序列A，输出序列A‘，要求A’中各元素的位置随机化

1.构造一个随机数组，使用该数组元素作为key排序数组A

SHUFFLE(A)
    n = length of A
    create array R[n]
    for i = 0, n-1
        R[i] = RANDOM_INT(n^3) //采用n^3是为了减少key的冲突
    SORT A with R as keys

时间复杂度：O(n+nlgn) = O(nlgn)

空间复杂度: O(n)

2.遍历序列A，将该位置元素与数组中随机位置的其他元素交换

SHUFFLE(A)
    n = length of A
    for i = 1 to n-1
    do
        swap A[i] A[RANDOM(0,i+1)]

时间复杂度：O(n)

空间复杂度：O(1)

STL中random_shuffle算法采用2的实现方式