不重复随机数列生成算法(1)(3)

算法就像一层窗户纸，隔着窗户纸，你永远无法知道里面是什么，一旦捅穿，又觉得非常简单。

还是上面那个例子，假设 n = 4

第一轮，我们随机获得2时，我们不将 2 从数组中移除，而是将数组的最后一个元素移动到2的位置

这时数组变成了

第二轮我们对 0-2 取随机数，这时数组可用的最后一个元素位置已经变成了2，而不是3。假设这时取到随机数为1

我们再把下标为2 的元素移动到下标1，这时数组变成了

以此类推，直到取出n个元素为止。

这个算法的优点是不需要用一个hashtable 来存储已获取的数字，不需要反复尝试，也不用像上一个算法那样删除数组元素，要做的只是每次把数组有效位置的最后一个元素移动到当前位置就可以了，这样算法的复杂度就降低为 O(n) ，速度大大提高。

经测试，在 n= 100000 时，这个算法的用时仅为7ms。

下面给出这个算法的实现代码

/// <summary>  
/// Designed by eaglet  
/// </summary>  
/// <param name="total"></param>  
/// <returns></returns>  
public static int[] GetRandomSequence2(int total)  
{  
 
    int[] sequence = new int[total];  
    int[] output = new int[total];  
 
    for (int i = 0; i < total; i++)  
    {  
        sequence[i] = i;  
    }  
 
    Random random = new Random();  
 
    int end = total - 1;  
 
    for (int i = 0; i < total; i++)  
    {  
        int num = random.Next(0, end + 1);  
        output[i] = sequence[num];  
        sequence[num] = sequence[end];  
        end--;  
    }  
 
    return output;  
}