常见的洗牌算法

算法

字数统计: 451阅读时长: 1 min

 2018/03/14   Share

学了半年多编程，多多少少也见过好几种排序方法，选择排序，插入排序，冒泡排序等等。
而洗牌算法的目的就是将有序的数组打乱。那么，怎么样洗牌才能使所有可能性概率都是一致的呢？
我认为要等概论打乱n张牌，那么就得使某一种打乱的方法出现的可能性为1/n！。
那么怎么实现呢？我的第一想法是利用伪随机数来进行打乱。例如，我们要打乱10张牌，那么从第一张牌开始打乱，从1-10的随机数中选取一个数进行交换，以后每个数字都是如此。
那么问题来了，这样是等概论吗？这种打乱使已经进行过交换的数字又可能再一次进行交换，导致重复交换，概率肯定是不确定的。
既然如此，我们已经可以基本上知道如何使概率为1/n!了。先从最后一个数n开始，选取1-n间的随机数，进行交换；而之后开始打乱第n-1个数，选取1-(n-1)的随机数进行交换。如此反复，便可以得到真正等概率的洗牌算法。

代码部分

//这里我们打乱52个数
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void shuffle(int *a,int n)
{
    int i,temp,number;
    srand((unsigned)time(NULL));
    for(i = n-1 ; i > 0 ; i--)
    {
        number = rand() % (i+1);
        temp = a[i];
        a[i] = a[number];
        a[number] = temp;
    }
}

int main(void)
{
    int a[52],i;
    int n = sizeof(a)/sizeof(int);
    for(i = 0;i < n;i++)
    {
        a[i] = i+1;
    } 
    shuffle(a,n);
    printf("洗牌后为：\n");
    for(i = 0;i < n;i++)
    {
        printf("%d\n",a[i]);
    }
}

原文作者：Zer0e

原文链接：https://re0.top/2018/03/14/shuffle/

发表日期：三月 14日 2018, 8:40:34 晚上

更新日期：April 25th 2018, 3:45:31 pm

Next Post

misc入门总结
Previous Post

CTF入门(坑)总结——web篇

CATALOG

1. 代码部分

